#include<cstdio>
#include<stdlib.h>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<set>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<string>
using namespace std;
const int maxn=31;
int n;
int pre[maxn];//先序
int post[maxn];//后序
int inorder[maxn];//中序
int layer[maxn];//层次
//使用指针二叉链表
struct node{
int data;
node* lchild;
node* rchild;
int layer;
};
//层次遍历输出
void LayerOrder(node* root){
queue<node*> q;
q.push(root);
root->layer=1;
while(!q.empty()){
node* now=q.front();
q.pop();
if(now->layer!=1){
printf(" ");
}
printf("%d",now->data);
if(now->lchild!=NULL)
{
now->lchild->layer=now->layer+1;
q.push(now->lchild);
}
if(now->rchild!=NULL){
now->rchild->layer=now->layer+1;
q.push(now->rchild);
}
}
}
//后序和中序序列构建二叉树（递归）
node* createBypostIn(int postL,int postR,int inL,int inR){
//出口
if(postL>postR){
return NULL;
}
//后序序列最后一个数是根节点
node* root=new node;
int data= post[postR];
root->data=data;
int k;
//在中序序列中找到根节点
for(k=inL;k<=inR;k++){
if(inorder[k]==data){
break;
}
}
//重新确定递归区间
//计算右子树的节点个数
int rightNum=inR-k;
int leftNum=k-inL;
//递归左子树
root->lchild=createBypostIn(postL,postL+leftNum-1,inL,k-1);
//递归右子树
root->rchild=createBypostIn(postR-rightNum,postR-1,k+1,inR);
//返回结果
return root;
}
//先序和中序序列构建二叉树（递归）
node* createByPreIn(int preL,int preR,int inL,int inR){
if(preL>preR){
return NULL;
}
node* root=new node;
int data=pre[preL];
root->data=data;
int k;
for(k=inL;k<=inR;k++){
if(inorder[k]==data){
break;
}
}
int leftNum=k-inL;//左子树的长度
root->lchild= createByPreIn(preL+1,preL+leftNum,inL,k-1);
root->rchild=createByPreIn(preL+leftNum+1,preR,k+1,inR);
return root;
}
//层次和中序序列构建二叉树：边输入数据边插入节点
void creat(node* &root,int val){
if(!root){
root=new node;
root->data=val;
root->lchild=root->rchild=NULL;
return;
}
//找到层次遍历该值在中序序列里的位置k
int k;
for(k=0;k<n;k++){
if(inorder[k]==val) break;
}
//找到根节点在中序序列里的位置
int u;
for(u=0;u<n;u++){
if(inorder[u]==root->data) break;
}
//要插入的节点是在根节点的右侧（右子树插入）
if(u<k) creat(root->rchild,val);
else creat(root->lchild,val);//左侧插入
}
int main()
{
scanf("%d",&n);
//4 1 3 2 6 5 7 先序
for(int i=0;i<n;i++){
scanf("%d",&pre[i]);
}
//1 2 3 4 5 6 7 中序
for(int i=0;i<n;i++){
scanf("%d",&inorder[i]);
}
//2 3 1 5 7 6 4 后序
for(int i=0;i<n;i++){
scanf("%d",&post[i]);
}
//4 1 6 3 5 7 2 层次
for(int i=0;i<n;i++){
scanf("%d",&layer[i]);
}
printf("-------------\n");
node* root1=createBypostIn(0,n-1,0,n-1);
LayerOrder(root1);
printf("\n");
node* root2= createByPreIn(0,n-1,0,n-1);
LayerOrder(root2);
printf("\n");
node* root3=NULL;
for(int i=0;i<n;i++){
creat(root3,layer[i]);
}
LayerOrder(root3);
return 0;
}
