PAT1020

二叉树构建以及层次遍历

注意对递归边界的把握

之前的博客有错误，改正一下：

T->lchild = createBiTree(pos, in, index);
T->rchild = createBiTree(pos+index, in+index+1, len-index-1);

https://www.cnblogs.com/JCcodeblgos/p/11401423.html

 1 #include <iostream>
 2 #include <queue>
 3 
 4 using namespace std;
 5 
 6 const int maxn = 30+5;
 7 string post_order[maxn], in_order[maxn], ans[maxn];
 8 
 9 typedef struct BiTNode
10 {
11     string data;
12     struct BiTNode *lchild, *rchild;
13 }BiTNode, *BiTree;
14 
15 BiTree createBiTree(string *pos, string *in, int len){
16     // cout << pos << " " << in << " " << len << endl;
17     if(len == 0)
18         return NULL;
19     
20     string root = pos[len-1];
21     int index = 0;
22     while (in[index]!=root)
23     {
24         index++;
25     }
26     // cout << index << endl;
27     BiTree T = new BiTNode;
28     T->data = root;
29     T->lchild = createBiTree(pos, in, index);
30     T->rchild = createBiTree(pos+index, in+index+1, len-index-1);
31     return T;
32 }
33 
34 void leveltraverse(BiTree T){
35     BiTree p;
36     queue<BiTree> Q;
37     Q.push(T);
38     int index = 0;
39     while (!Q.empty())
40     {
41         p = Q.front();
42         Q.pop();
43         ans[index++] =  p->data;
44         if(p->lchild)
45             Q.push(p->lchild);
46         if(p->rchild)
47             Q.push(p->rchild);
48     }
49 }
50 
51 int main(){
52     // freopen("test.txt", "r", stdin);
53     int n;
54     cin >> n;
55     for(int i=0; i<n; i++)
56         cin >> post_order[i];
57     for(int i=0; i<n; i++)
58         cin >> in_order[i];
59 //    for(int i=0; i<n; i++)
60 //        cout << post_order[i] << " ";
61 //    cout << endl;
62 //    for(int i=0; i<n; i++)
63 //        cout << in_order[i] << " ";
64 //    cout << endl;
65     BiTree T = createBiTree(post_order, in_order, n);
66     leveltraverse(T);
67     for(int i=0; i<n; i++){
68         if(i != 0)
69             cout << " ";
70         cout << ans[i];
71     }
72 }