선순과 중순에 따라 출력 후순을 두루 다니다
1110 단어 GPLT2019 - 교내 - 시뮬레이션 문제
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;
}