通过层序和中序遍历序列重建二叉树

来源：cnblogs　　作者：the_sky314　　时间：2019/3/29 9:01:03　　对本文有异议

　　在学二叉树的重建时，在《算法笔记》上学到了如何通过先序（或后序）遍历序列和中序遍历序列重建二叉树，它也提出了一个问题：如何通过层序和中序遍历序列重建二叉树？我一开始按照先序和中序重建的思路思考，发现做不到。我无法确定一个点后面的点属于它的左子树还是右子树或者兄弟节点。于是我在网上查找，发现这方面的话题不多，其中还有一些不是用C++实现的。不过幸好还是找到了。于是在学习之后在这把它记录下来。

 1 #include <cstdio>
 2 #include <queue>
 3 using namespace std;
 4 
 5 int ceng[100];
 6 int zhon[100];
 7 
 8 
 9 struct node
10 {
11     int data;
12     node* left;
13     node* right;
14  };
15 
16 node* create(int cengl,int cengr,int zhonl,int zhonr)  //当我给你一个二叉树的中序遍历时 
17 {                                                    //这个中序遍历遍历一定有一个根节点 
18     if(zhonl>zhonr)                                  //体现在层序遍历上时它一定先出现 
19     {                                                //所以顺序遍历层序遍历，一定可以先发现二叉树的根节点 
20         return NULL;      
21     }
22     node* root=new node;
23     int i,j;
24     int flag;
25     for(i=0;i<=(cengr-cengl);i++)
26     {
27         flag=false;
28         for(j=0;j<=(zhonr-zhonl);j++)
29         {
30             if(ceng[i+cengl]==zhon[j+zhonl])
31             {
32                 flag=true;
33                 break;
34             }
35         }
36         if(flag) break;
37     }
38     root->data=zhon[j+zhonl];                          
39     root->left=create(cengl+i+1,cengr,zhonl,zhonl+j-1);
40     root->right=create(cengl+i+1,cengr,zhonl+j+1,zhonr);  
41     return root;
42 }
43 
44 void cengxu(node* root)
45 {
46     queue<node*> q;
47     q.push(root);
48     while(!q.empty())
49     {
50         node* top=q.front();
51         q.pop();
52         if(top!=root) printf(" ");
53         printf("%d",top->data);
54         if(top->left) q.push(top->left); 
55         if(top->right) q.push(top->right);
56     }
57 }
58 
59 
60 int main()
61 {
62     int n;
63     scanf("%d",&n);
64     for(int i=0;i<n;i++) scanf("%d",&ceng[i]);
65     for(int i=0;i<n;i++) scanf("%d",&zhon[i]);
66     node* root=create(0,n-1,0,n-1);
67     cengxu(root);
68     return 0;
69 }