树的遍历(根据后序遍历中序遍历推出层序遍历)

对于二叉树的遍历,分为深度优先遍历与广度优先遍历,广度优先遍历有时又称作层序遍历。而深度优先遍历又分为前序遍历,中序遍历和后序遍历。三者之间的区别主要在于根结点的遍历顺序。前序遍历的顺序是根结点->左子树->右子树,中序遍历顺序是左子树->根结点->右子树,后序遍历顺序是左子树->右子树->根结点。现在给出树的后序遍历与中序遍历,要求写出该树的层序遍历。以下是pat上的例题:

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

输入格式:

输入第一行给出一个正整数N(<=30),是二叉树中结点的个数。第二行给出其后序遍历序列。第三行给出其中序遍历序列。数字间以空格分隔。

输出格式:

在一行中输出该树的层序遍历的序列。数字间以1个空格分隔,行首尾不得有多余空格。

输入样例:

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

输出样例:

1
4 1 6 3 5 7 2

分析:

树的后序遍历特点是最后一个遍历的永远是根结点,由样例很容易看到4即为该树的根结点。而中序遍历的特点是根结点的左边永远是根结点的左子树部分,右边永远是根结点的右子树部分。而树的每一个子树都可以作为新的根。因此二者结合起来很容易将整个树构建出来。以样例为例,首先可以从后序遍历确定4为根结点,然后对照着中序遍历找到4的中序位置为第4位,然后以4为界将树分为以左子树为根的树和以右子树为根的树。现在可以确定根的左子树与右子树的个数分别为m,n,而后序遍历先遍历左子树部分,因此可以确定左子树部分为第1~m位,右子树部分为m+1~m+n位,最后一位为根结点。而左子树部分最后一位即第n位为左子树部分的根即左子树,同理右子树也一样。由此我们只需建立一个树遍历的函数ergodic(int root, int start, int end, int index)即可。其中root为根结点,start与end为由该根结点所衍生出的所有子树的范围,index记录该树的位置。由后序遍历可知end即为根结点的位置,有start开始遍历中序,直到找到根结点在中序遍历中的位置i,在以i为界划分为(start,i-1)与(i+1,end)两部分,而root则为后序遍历中(start,end)中的end位置,即为root-end+i-1的位置。我们初始树的所有结点为-1,意味空值,因此最终搭建的树只需按顺序遍历所有有值部分即可。以下是代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<iostream>  
#include<vector>
using namespace std;
vector<int>post, in, level(100000, -1);
int N;
void ergodic(int root, int start, int end, int index) {
int i = start;
if (start > end)
return;
while (i < end&&in[i] != post[root])
i++;
level[index] = post[root];
//cout << root << start << end << i << endl;
ergodic(root - 1 - end + i, start, i - 1, 2 * index + 1);
ergodic(root - 1, i + 1, end, 2 * index + 2);
}
int main() {
cin >> N;
post.resize(N);
in.resize(N);
for (int i = 0; i < N; i++)
cin >> post[i];
for (int i = 0; i < N; i++)
cin >> in[i];
ergodic(N - 1, 0, N - 1, 0);
for (int i = 0, cnt = 0; i < level.size(); i++) {
if (level[i] != -1) {
cout << level[i];
cnt != N - 1 ? cout << ' ' : cout << endl;
cnt++;
}
}
return 0;
}

对于前序遍历也一样,因为前序遍历的特点和后序遍历的特点刚好相反,前序遍历第第一位总是根结点。根据两种遍历即可推出整棵树的结构,搭建完树的结构,任何遍历都会很方便。


纸短情长啊文章结束了但我们的故事还在继续
坚持原创技术分享,您的支持将鼓励我继续创作!