//給定二叉樹(shù)的先序序列和中序序列，求二叉樹(shù)的層序遍歷序列
//輸入；
//7
//1 2 3 4 6 7 5
//2 1 6 4 7 3 5
//1 2 3 4 5 6 7
//輸出
#include<cstdio>
#include<queue>
using namespace std;
int n;//二叉樹(shù)的節(jié)點(diǎn)數(shù)
int x[10];//存放先序序列
int z[10];//存放中序序列
struct TreeNode
{
? ?int data;//節(jié)點(diǎn)信息
? ?TreeNode * leftchild;
? ?TreeNode * rightchild;
};
TreeNode* creat(int preL,int preR,int inL , int inR)//preL為先序做區(qū)間因由此類(lèi)推
{
? ?if(preL>preR)
? ?{
? ? ? ?return NULL;
? ?}
? ?TreeNode * root = new TreeNode;
? ?root -> data = x[preL];//先序的第一個(gè)元素就是根
? ?int k;//查找和先序第一個(gè)元素相同的元素于后序序列中下標(biāo)用k保存
? ?for(int i=inL;i<=inR;i++)
? ?{
? ? ? ?if(z[i] == x[preL])
? ? ? ?{
? ? ? ? ? ?k=i;
? ? ? ? ? ?break;//找到則退出循環(huán)
? ? ? ?}
? ?}
? ?int numleft = k -inL;//左子樹(shù)的節(jié)點(diǎn)個(gè)數(shù)
? ?//左子樹(shù)的先序區(qū)間為{preL+1,preL+numleft},中序區(qū)間為{inL,k-1}遞歸調(diào)用返回作為左子樹(shù)
? ?root -> leftchild = creat(preL+1,preL+numleft,inL,k-1);
? ?//右子樹(shù)的先序區(qū)間為{preL+numleft+1,preR},中序區(qū)間為{k+1,inR}
? ?root -> rightchild = creat(preL+numleft+1,preR,k+1,inR);
? ?//返回根節(jié)點(diǎn)的位置
? ?return root;
}
void levelTraverse(TreeNode * root)
{
? ?queue<TreeNode *> myqueue;
? ?myqueue.push(root);
? ?while(myqueue.empty() == false)//隊(duì)列為空是假的即隊(duì)列不空
? ?{
? ? ? ?TreeNode * Queuefront = myqueue.front();
? ? ? ?myqueue.pop();
? ? ? ?printf("%d ",Queuefront->data);
? ? ? ?if(Queuefront -> leftchild != NULL)
? ? ? ?{
? ? ? ? ? ?myqueue.push(Queuefront -> leftchild);
? ? ? ?}
? ? ? ?if(Queuefront -> rightchild != NULL)
? ? ? ?{
? ? ? ? ? ?myqueue.push(Queuefront -> rightchild);
? ? ? ?}
? ?}

}

int main()
{
? ?scanf("%d",&n);
? ?for(int i=1;i<=n;i++)
? ?{
? ? ? ?scanf("%d ",&x[i]);
? ?}
? ?for(int i=1;i<=n;i++)
? ?{
? ? ? ?scanf("%d ",&z[i]);
? ?}
? ?//用最終的根接受返回的根節(jié)點(diǎn)
? ?TreeNode * root = creat(1,n,1,n);
? ?//二叉樹(shù)的層序遍歷
? ?levelTraverse(root);
}