已知二叉树的前序/后序遍历和中序遍历，求后序/前序遍历
博客分类： 
∙算法与数据结构
CC++C#
首先，我们看看前序、中序、后序遍历的特性： 
前序遍历： 
    1.访问根节点 
    2.前序遍历左子树 
    3.前序遍历右子树 
中序遍历： 
    1.中序遍历左子树 
    2.访问根节点 
    3.中序遍历右子树 
后序遍历： 
    1.后序遍历左子树 
    2.后序遍历右子树 
    3.访问根节点 

好了，先说说用前序遍历和中序遍历求后序遍历 
假设前序遍历为 adbgcefh, 中序遍历为 dgbaechf 
前序遍历是先访问根节点，然后再访问子树的，而中序遍历则先访问左子树再访问根节点 
那么把前序的 a 取出来，然后查 a 在中序遍历中的位置就得到 dgb a echf 
那么我们就知道 dgb 是左子树 echf 是右子树，因为数量要吻合 
所以前序中相应的 dbg 是左子树 cefh 是右子树 
然后就变成了一个递归的过程，具体代码如下： 
C++代码 
1.#include <iostream> 
2.#include <string> 
3.using namespace std; 
4. 
5.int find(const string &str, char c) 
6.{ 
7.    for (int i = 0; i < str.size(); ++ i) 
8.        if (c == str[i]) 
9.            return i; 
10.    return -1; 
11.} 
12. 
13.bool PreMid(const string &pre, const string &mid) 
14.{ 
15.    if (pre.size() == 0) 
16.        return false; 
17.    if (pre.size() == 1) 
18.    { 
19.        cout << pre; 
20.        return true; 
21.    } 
22.     
23.    //根节点是第一个元素 
24.    int k = find(mid, pre[0]); 
25.     
26.    string pretmp = pre.substr(1, k); 
27.    string midtmp = mid.substr(0, k); 
28.    PreMid(pretmp, midtmp); 
29.     
30.    pretmp = pre.substr(k + 1, pre.size() - k - 1); 
31.    midtmp = mid.substr(k + 1, mid.size() - k - 1); 
32.    PreMid(pretmp, midtmp); 
33.     
34.    //变成后序遍历要最后输出节点的值 
35.    cout << pre[0]; 
36.} 
37. 
38.int main() 
39.{ 
40.    string pre, mid; 
41.    while (cin >> pre >> mid) 
42.    { 
43.        PreMid(pre, mid); 
44.        cout << endl; 
45.    } 
46.} 

而已知后序遍历和中序遍历求前序遍历的过程差不多，但由于后序遍历是最后才访问根节点的 
所以要从后开始搜索，例如上面的例子，后序遍历为 gbdehfca，中序遍历为 dgbaechf 
后序遍历中的最后一个元素是根节点，a，然后查中序中a的位置 
把中序遍历分成 dgb a echf，而因为节点个数要对应 
后序遍历分为 gbd ehfc a，gbd为左子树，ehfc为右子树，这样又可以递归计算了 
其他一些附带的代码上面已经有，这里就不重复贴了，具体代码如下： 
C++代码 
1.bool BackMid(const string &back, const string &mid) 
2.{ 
3.    if (back.size() == 0) 
4.        return false; 
5.     
6.    if (back.size() == 1) 
7.    { 
8.        cout << back;  先序中序后序遍历二叉树
9.        return true; 
10.    } 
11.     
12.    //根节点是最后一个元素 
13.    int k = find(mid, back[back.size() - 1]); 
14.     
15.    //变成前序遍历要先输出节点的值 
16.    cout << back[back.size() - 1]; 
17.     
18.    string backTmp = back.substr(0, k); 
19.    string midTmp = mid.substr(0, k); 
20.    BackMid(backTmp, midTmp); 
21.     
22.    backTmp = back.substr(k, back.size() - k - 1); 
23.    midTmp = mid.substr(k + 1, mid.size() - k - 1); 
24.    BackMid(backTmp, midTmp); 
25.} 

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。