층차에서 2차원 트리 출력 순서 재구성

제목:
두 갈래 나무의 중서층 순서로 두 갈래 나무를 재건하다
기한:
1000 ms
메모리 제한:
10000 K
총 기한:
3000 ms
설명:
두 갈래 나무의 중순과 층순 출력을 정하여 이 나무를 생성하고 선순과 후순으로 출력합니다
여기서 트리 구조의 결점 정보는 정수입니다.
입력:
트리 결점 개수
레이어 출력 시퀀스
중간 순서 입력 시퀀스
출력:
차례차례 두루 다니다
뒤돌아 다니다
샘플 입력:
육
1 2 3 5 6 7
2 5 1 6 3 7
내보내기 예제:
1 2 5 3 6 7
5 2 6 7 3 1

// G++
#include <stdio.h>
#include <stdlib.h>
//////////////TreeNode///////////////////////////////////////////
typedef struct _TreeNode
{
	//char key;
	int key;
	struct _TreeNode *Lc;
	struct _TreeNode *Rc;
}TreeNode;

////Queue//////////////////////////////////////////////////////////////////
// 
typedef struct _QElement
{
	int lvl;// 
	int l,h;// 、 
	TreeNode *f;// 
	int lr;//  ，0: ,1： ，2： 
}QElement;

// 
typedef struct _QNode
{
	QElement data;
	struct _QNode *next;
}QNode;


// 
typedef struct _Queue
{
	QNode *front;
	QNode *rear;
}Queue;

void InitQueue(Queue &Q)
{
	Q.front=Q.rear=(QNode*)malloc(sizeof(QNode));
	if(!Q.front) exit(0);
	Q.front->next=NULL;
	//Q.front->next=Q.rear->next=NULL;
	//Q.front=NULL;
	//Q.rear=NULL;
}

bool isemptyQ(Queue &Q)
{
	//if(Q.front==NULL)
	if(Q.front==Q.rear)
		return 1;
	return 0;
}

void EnQueue(Queue &Q,QElement e)
{
	QNode *p;
	p=(QNode*)malloc(sizeof(QNode));
	if(!p) exit(0);
	p->data=e;
	p->next=NULL;
	Q.rear->next=p;
	Q.rear=p;
}


void DeQueue(Queue &Q,QElement &e)
{
	QNode* p;
	if(Q.front==Q.rear)
		exit(0);
	p=Q.front->next;
	e=p->data;
	Q.front->next=p->next;
	if(Q.rear==p)
		Q.rear=Q.front;
	free(p);
}
int RepreOrder(TreeNode *T)
{
	//TreeNode *p=T;
	if(T)
	{
		printf("%d ",T->key);
		RepreOrder(T->Lc);
		RepreOrder(T->Rc);
	}
	return 0;
}

int RePostOrder(TreeNode *T)
{
	if(T)
	{
		RePostOrder(T->Lc);
		RePostOrder(T->Rc);
		printf("%d ",T->key);
	}
	return 0;
}

// http://www.cnblogs.com/xiaofengkang/archive/2011/05/22/2053493.html
TreeNode* CreatFromLevelIn(int *level,int *in, int n)
{
	int r=-1,low,high,lr,i,j;
	TreeNode *root=NULL,*p,*father;
	int ch;
	QElement s;
	Queue Q;
	InitQueue(Q);
	s.lvl=level[++r];
	s.l=0;
	s.h=n-1;
	s.f=NULL;
	s.lr=0;
	EnQueue(Q,s);
	while(!isemptyQ(Q))
	{
		DeQueue(Q,s);
		ch=s.lvl;
		low=s.l;
		high=s.h;
		father=s.f;
		lr=s.lr;
		for(j=low;j<=high;j++)
		{
			if(in[j]==ch)
			{
				i=j;
				//printf("i=%d
",i);//system("pause");
				break;
			}
		}//for
			p=(TreeNode*)malloc(sizeof(TreeNode));
			p->key=ch;
			p->Lc=p->Rc=NULL;
			if(lr==0) root=p;
			else if(lr==1) father->Lc=p;
			else father->Rc=p;
			if(low==high) continue;// for 
			if(i==low)// 
			{
				s.l=low+1;
				s.lr=2;
				s.lvl=level[++r];
				s.f=p;
				EnQueue(Q,s);
			}
			else if(i==high)// 
			{
				s.h=high-1;
				s.lr=1;
				s.lvl=level[++r];
				s.f=p;
				EnQueue(Q,s);
			}
			else
			{
				s.h=i-1;
				s.l=low;
				s.lr=1;
				s.lvl=level[++r];
				s.f=p;
				EnQueue(Q,s);

				s.l=i+1;
				s.h=high;
				s.lr=2;
				s.lvl=level[++r];
				s.f=p;
				EnQueue(Q,s);
			}//else
	}//while
	return root;
}//CreatFromLevelIn

int main()
{
	int len;
	scanf("%d",&len);
	int *level=(int*)malloc(sizeof(int)*len);
	int *in=(int*)malloc(sizeof(int)*len);
	int i;

	for(i=0;i<len;i++)
	{
		scanf("%d",level+i);
	}
	for(i=0;i<len;i++)
	{
		scanf("%d",in+i);
	}

	TreeNode *newnode=(TreeNode*)malloc(sizeof(TreeNode));
	newnode=CreatFromLevelIn(level,in,len);
	RepreOrder(newnode);
	printf("
");
	RePostOrder(newnode);
	return 0;
}