선순과 중순에 따라 출력 후순을 두루 다니다

다음 순서를 입력합니다.
7
4 1 3 2 6 5 7
1 2 3 4 5 6 7

출력 후 시퀀스:

2 3 1 5 7 6 4

코드:
 
#include
using namespace std;
struct node{
	char data;
	node* lchild;
	node* rchild;
};
int pre[55],in[55];
node* buildtree(int prel,int prer,int inl,int inr)
{
	if(inl>inr) return NULL;
	node* root=new node;
	root->data=pre[prel];
	int i;
	for(i=inl;i<=inr;i++)
	{
		if(in[i]==pre[prel])
		   break;
	}
	int num=i-inl;
	root->lchild=buildtree(prel+1,prel+num,inl,i-1);
	root->rchild=buildtree(prel+num+1,prer,i+1,inr);
}
int flag=0;
void print(node* root)
{
	if(root==NULL)
	  return;
	print(root->lchild);
	print(root->rchild);
	if(flag==0)
    {
    	printf("%d",root->data);
    	flag=1;
	}
	else
	{
		printf(" %d",root->data);
	}
}
int main()
{
	int n,i;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	   scanf("%d",&pre[i]);
	for(int i=1;i<=n;i++)
	   scanf("%d",&in[i]);
	node*root=buildtree(1,n,1,n);
	print(root);
	return 0;
}

 

좋은 웹페이지 즐겨찾기