树的遍历（根据后序遍历中序遍历推出层序遍历）

对于二叉树的遍历，分为深度优先遍历与广度优先遍历，广度优先遍历有时又称作层序遍历。而深度优先遍历又分为前序遍历，中序遍历和后序遍历。三者之间的区别主要在于根结点的遍历顺序。前序遍历的顺序是根结点->左子树->右子树，中序遍历顺序是左子树->根结点->右子树，后序遍历顺序是左子树->右子树->根结点。现在给出树的后序遍历与中序遍历，要求写出该树的层序遍历。以下是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，意味空值，因此最终搭建的树只需按顺序遍历所有有值部分即可。以下是代码：

#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;  
}

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