청 화 데이터 구조 진 이 진 트 리 재 구축 AC 100

이 문제 의 난점 은 어느 쪽 이 왼쪽 나무 이 고 어느 쪽 이 오른쪽 나무 인지 어떻게 판단 하 느 냐 에 있다.
우선 순위 가 a [maxn] 이 고, 후 순위 가 b [maxn] 이 라 고 가정 합 니 다.
유사 한 데이터
131 2 4 6 10 9 12 13 7 11 8 5 310 12 13 9 6 11 8 7 4 5 2 3 1
왼쪽 나무 에 대해 b [j] = 9, b [i] = 12.ij | | j = = 0 을 볼 수 있 습 니 다.오른쪽 트 리 의 좌 표 는 항상 왼쪽 트 리 뒤에 있 기 때문에 (뒷 순 서 는 옮 겨 다 니 고 왼쪽 과 오른쪽) 왼쪽 트 리 일수 록 먼저 읽 히 기 때문에 좌표 값 이 작 습 니 다.그러면 더 작은 좌표 값 이 존재 할 때 왼쪽으로 도 된다 는 뜻 이다.그렇지 않 으 면 오른쪽 트 리 를 만 들 었 다 는 뜻 입 니 다.
오른쪽 하위 트 리 에 대해 서 는 멈 추 려 면 생 성 완료 후 j - i = 1.따라서 오른쪽 트 리 가 생 성 을 중단 하 는 조건 은 j - i < = 1 입 니 다.
100 점 코드 는 다음 과 같 습 니 다.

#pragma warning(disable:4996)
#include
using namespace std;
#define maxn 4000000
int a[maxn], b[maxn], c[maxn], d[maxn],n;
struct binnode {
	int data;
	binnode*lc, *rc, *parent;
	binnode() :data(0), lc(NULL), rc(NULL), parent(NULL) {}
	binnode(int e, binnode*p3 = NULL, binnode*p1 = NULL, binnode*p2 = NULL) :data(e), parent(p3), lc(p1), rc(p2) {}
};
class bintree {
private:
	binnode * _root;
	int _size;
public:
	bintree() :_size(0), _root(NULL) {}
	int size() { return _size; }
	binnode*root() { return _root; }
	binnode*insertaslc(binnode*p, int const&e);
	binnode*insertasrc(binnode*p, int const&e);
	binnode*insertasroot(int const&e);
};
binnode* bintree::insertaslc(binnode*p, int const&e)
{
	binnode*p1 = new binnode(e, p);
	p->lc = p1;
	_size++;
	return p1;
}
binnode* bintree::insertasrc(binnode*p, int const&e)
{
	binnode*p1 = new binnode(e);
	p->rc = p1;
	_size++;
	return p1;
}
binnode* bintree::insertasroot(int const&e)
{
	_root = new binnode(e);
	_size = 1;
	return _root;
}
bintree tree;
void creatright_tree(binnode*p, int lo3, int lo);
//lo2,lo3      
void creatleft_tree(binnode*p, int lo2)
{

	auto t = tree.insertaslc(p, a[lo2]);
	auto lo3 = c[a[lo2]];
	if (lo3>0&&c[a[lo2]]>c[a[lo2+1]])//  a[lo2+1]    
	{
		creatleft_tree(t, ++lo2);
		creatright_tree(t, --lo3,lo2);
	}
}
void creatright_tree(binnode*p, int lo3,int lo)
{
	auto t = tree.insertasrc(p, b[lo3]);
	auto lo2 = d[b[lo3]];
	if (lo3-c[a[lo]]>1)
	{
		creatleft_tree(t, ++lo2);
		creatright_tree(t, --lo3,lo2);
	}
}
void midtral(binnode*p)
{
	if (!p)return;
	midtral(p->lc);
	if(p->data!=a[n-1])printf("%d ", p->data);
	else printf("%d
",p->data);
	midtral(p->rc);
}
int main()
{
	int lo1 = 0, lo2 = 0, lo3 = 0;//lo1     ，lo2       ，lo3       
#ifndef _OJ_
	freopen("createtree.txt", "r", stdin);
	// freopen("trainout.txt", "w", stdout);
#endif
	scanf("%d", &n);
	for (auto i = 0; i