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

 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 }