L2-006. 樹的遍歷

輸入格式：

輸入第一行給出一個正整數N（<=30），是二叉樹中結點的個數。第二行給出其後序遍歷序列。第三行給出其中序遍歷序列。數字間以空格分隔。

輸出格式：

在一行中輸出該樹的層序遍歷的序列。數字間以1個空格分隔，行首尾不得有多餘空格。

7
2 3 1 5 7 6 4
1 2 3 4 5 6 7

4 1 6 3 5 7 2

思路：

 根據二叉樹的性質可以知道：

1. 後序遍歷，左子樹肯定先出現，然後是右子樹，最後一個肯定是本樹的根節點。
2. 中序遍歷中，左子樹上的節點都出現在根節點前，右子樹上的節點都出現在根節點後。

　可以根據這個規律，在中序遍歷中找到根節點，再在後序遍歷中利用根節點的位置得到左右子樹各自的後序遍歷以及長度。再根據他們各自的長度從中序遍歷中分解得到左右子樹各自的中序遍歷。

比如樣例中，中序遍歷2 3 1 5 7 6 4的根節點就是4，然後在後序遍歷1 2 3 4 5 6 7中根據根節點4的位置分得左子樹的後序遍歷1 2 3左子樹長度為3，可在右子樹的後序遍歷5 6 7右子樹長度為3。根據左右子樹長度以及規律1可得到左右子樹的中序遍歷分別為2 3 1和5 7 6。以此類推就可將其全部分解。

 1 #include <iostream>
 2 #include <queue>
 3 using namespace std;
 4 struct tree//表示一棵樹，記錄他的中後序遍曆數組和長路
 5 {
 6     int *h,*z,length;//h指向後序遍歷的數組，z指向中序遍歷的數組，length代表長度
 7     tree(int *h,int *z,int length)
 8     {
 9         this->h=h;
10         this->z=z;
11         this->length=length;
12     }
13     tree(){};
14 };
15 
16 queue<tree> Queue;//
17 int l;
18 int H[40];//儲存後序遍歷結果
19 int Z[40];//儲存中序遍歷結果
20 
21 void dis(tree T)
22 {
23     tree w;
24     int i;
25     int t;
26     Queue.push(T);
27     while(!Queue.empty())
28     {
29         w=Queue.front();
30         Queue.pop();
31         if(w.length>0)
32         {
33             t =w.h[w.length-1];//後序遍歷的最後一個是根節點
34             cout << t;
35             int l = 0;
36             while(w.z[l]!=t)l++;//得到左子樹長度
37             if(l>0)//如果左子樹存在就入隊
38                             Queue.push(tree(w.h,w.z,l));
39             if(w.length-l-1)//如果右子樹存在就入隊，除了左子樹和根節點剩下的就是右子樹的長度
40                             Queue.push(tree(w.h+l,w.z+l+1,w.length-l-1));
41             if(!Queue.empty())cout << " ";//如果這時候隊不為空說明後面還會輸出節點，就要輸出一個空格
42         }
43     }
44 }
45 
46 int main()
47 {
48     cin >> l;
49     int i;
50     i = 0;
51     while(i < l)
52     {
53         cin >> H[i];
54         i++;
55     }
56     i = 0;
57     while(i < l)
58     {
59         cin >> Z[i];
60         i++;
61     }
62     dis(tree(H,Z,l));
63     return 0;
64 }
65