【二叉树】根据中序遍历和后序遍历的结果重建二叉树,并给出BFS的顺序
作者:
Alier
,
2020-02-22 21:42:19
,
所有人可见
,
阅读 833
#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
const int MAXN=50;
int in[MAXN],post[MAXN];
int n;
struct node{
int data;
node* lchild;
node* rchild;
};
node* create(int postl,int postr,int inl,int inr){
if(postl>postr) return NULL;
node* root= new node;
root->data=post[postr];
int x=post[postr];
int k;
for(k=inl;k<=inr;k++){
if(in[k]==x) break;
}
int numl=k-inl;
root->lchild=create(postl,postl+numl-1,inl,k-1);
root->rchild=create(postl+numl,postr-1,k+1,inr);
return root;
}
int num=0;
void BFS(node* root){
queue<node*> q;
q.push(root);
while(q.size()){
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;
}