#include <iostream> #include <queue> using namespace std; typedef struct tr* ptree; typedef struct tr { struct tr *lchild; struct tr *rchild; int date; }tree; //前序中序创建二叉树 ptree premid(int pre[],int mid[],int size) { if(size<=0) { return NULL; } int i; for(i=0;i<size;i++) { if(mid[i]==pre[0]) { //cout<<i<<endl; break; } } tree * t=new tree; t->date = pre[0]; t->lchild = premid(pre+1,mid,i ); t->rchild = premid(pre+i+1,mid+i+1,size-i-1); return t; } //后序中序创建二叉树 ptree postmid(int post[],int mid[],int size) { if(size<=0) { return NULL; } int i; for( i=0;i<size;i++) { if(mid[i]==post[size-1]) { //cout<<i<<' '; break; } } //int x=i; tree* t=new tree; t->date = post[size-1]; //cout<<x<<' '; t->lchild =postmid(post,mid,i); t->rchild = postmid(post+i,mid+i+1,size-i-1); return t; } //后序遍历 void postround(ptree t) { if(t==NULL) return; postround(t->lchild ); postround(t->rchild ); cout<<t->date <<' '; } void midround(ptree t) { if(t==NULL) return; postround(t->lchild ); cout<<t->date <<' '; postround(t->rchild ); } //前序遍历 void preround(ptree t) { if(t==NULL) return; cout<<t->date<<' ' ; preround(t->lchild ); preround(t->rchild ); } //层序遍历 void floorprint(ptree t) { queue <ptree> q; if(t!=NULL) { q.push(t); } while(q.empty()==false) { ptree node=q.front() ; cout<< node->date <<' '; if(node->lchild !=NULL) { q.push(node->lchild ); } if(node->rchild !=NULL) { q.push(node->rchild ); } q.pop() ; } } int main() { int pre[1000]={0},mid[1000]={0},post[1000]={0},n; cin>>n; for(int i=0;i<n;i++) { cin>>post[i]; } for(int i=0;i<n;i++) { cin>>mid[i]; } ptree head=postmid(post,mid,n); floorprint(head); }