【PAT A1020】 Tree Traversals

//给定二叉树的先序序列和中序序列，求二叉树的层序遍历序列
//输入；
//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;//二叉树的节点数
int x[10];//存放先序序列
int z[10];//存放中序序列
struct TreeNode
{
   int data;//节点信息
   TreeNode * leftchild;
   TreeNode * rightchild;
};
TreeNode* creat(int preL,int preR,int inL , int inR)//preL为先序做区间因由此类推
{
   if(preL>preR)
   {
       return NULL;
   }
   TreeNode * root = new TreeNode;
   root -> data = x[preL];//先序的第一个元素就是根
   int k;//查找和先序第一个元素相同的元素于后序序列中下标用k保存
   for(int i=inL;i<=inR;i++)
   {
       if(z[i] == x[preL])
       {
           k=i;
           break;//找到则退出循环
       }
   }
   int numleft = k -inL;//左子树的节点个数
   //左子树的先序区间为{preL+1,preL+numleft},中序区间为{inL,k-1}递归调用返回作为左子树
   root -> leftchild = creat(preL+1,preL+numleft,inL,k-1);
   //右子树的先序区间为{preL+numleft+1,preR},中序区间为{k+1,inR}
   root -> rightchild = creat(preL+numleft+1,preR,k+1,inR);
   //返回根节点的位置
   return root;
}
void levelTraverse(TreeNode * root)
{
   queue<TreeNode *> myqueue;
   myqueue.push(root);
   while(myqueue.empty() == false)//队列为空是假的即队列不空
   {
       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]);
   }
   //用最终的根接受返回的根节点
   TreeNode * root = creat(1,n,1,n);
   //二叉树的层序遍历
   levelTraverse(root);
}