PAT L2-006. 树的遍历

L2-006. 树的遍历

时间限制	内存限制	代码长度限制	判题程序	作者
400 ms	65536 kB	8000 B	Standard	陈越

 

给定一棵二叉树的后序遍历和中序遍历，请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。

输入格式：

输入第一行给出一个正整数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