#include<iostream>
#include<queue>
#include<algorithm>
#include<stdio.h>
using namespace std;
struct node
{
int data;
node* lchild;
node* rchild;
};
const int maxn=50;
int n,pre[maxn],post[maxn],in[maxn];
node* create(int postl,int postr,int inl,int inr) //建树
{
if(postl>postr)
return NULL;//NULL与nullptr等效
node* root=new node;
root->data=post[postr];
int k;
for(k=inl;k<=inr;k++)
{
if(in[k]==post[postr])
break;
}
int numleft=k-inl;
root->lchild=create(postl,postl+numleft-1,inl,k-1); //会出现的情况:当后序序列已经不存在时,即numleft=0时,postl》postr
root->rchild=create(postl+numleft,postr-1,k+1,inr);
return root;
}
int num=0;
void BFS(node* root)
{
queue<node*> q;
q.push(root);
while(!q.empty())
{
node* now=q.front();
q.pop();
cout<<now->data;
num++;
if(num<n) cout<<' ';
if(now->lchild!=NULL) q.push(now->lchild);
if(now->rchild!=NULL) q.push(now->rchild);
}
}
int main()
{
cin>>n;
for(int i=0;i<n;i++)
cin>>post[i];
for(int i=0;i<n;i++)
cin>>in[i];
node* root=create(0,n-1,0,n-1);
BFS(root);
return 0;
}
必须注意,如果create的参数错误会导致段错误
root->lchild=create(postl,postl+numleft-1,inl,k-1);
root->rchild=create(postl+numleft,postr-1,k+1,inr);