前序遍历和后续遍历

《前序遍历和后续遍历》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、首先明确：一颗二叉树的前序遍历=根节点+左子树前序遍历+右子树前序遍历一颗二叉树的中序遍历=左子树中序遍历+根节点+右子树中序遍历那么从前序遍历中取第一个点，就是根节点，知道了根节点，就可以找到中序遍历中跟节点的位置，那么就可以在中序遍历中找到左子树和右子树。首先，我们看看前序、中序、后序遍历的特性： 前序遍历：    1.访问根节点    2.前序遍历左子树    3.前序遍历右子树 中序遍历：    1.中序遍历左子树    2.访问根节点    3.中序遍历右子树 后序遍历：    1.后序遍历左子树    2.后序遍历右子树    3.访问根节点 好了，先说说

2、用前序遍历和中序遍历求后序遍历 假设前序遍历为adbgcefh,中序遍历为dgbaechf 前序遍历是先访问根节点，然后再访问子树的，而中序遍历则先访问左子树再访问根节点 那么把前序的a取出来，然后查找a在中序遍历中的位置就得到dgbaechf 那么我们就知道dgb是左子树echf是右子树，因为数量要吻合 所以前序中相应的dbg是左子树cefh是右子树 然后就变成了一个递归的过程，具体代码如下： C++代码  1.#include   2.#include   3.using namespace std;  4.  5.int fi

3、nd(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.{  1.    if (pre.size() == 0)  2.        return false;  3.    if (

4、pre.size() == 1)  4.    {  5.        cout << pre;  6.        return true;  7.    }  8.     9.    //根节点是第一个元素  10.    int k = find(mid, pre[0]);  11.      12.    string pretmp = pre.substr(1, k);  13.    string midtmp = mid.substr(0, k);  14.    PreMid(pretmp, midtmp);  15.      16.    p

5、retmp = pre.substr(k + 1, pre.size() - k - 1);  17.    midtmp = mid.substr(k + 1, mid.size() - k - 1);  18.    PreMid(pretmp, midtmp);  19.      20.    //变成后序遍历要最后输出节点的值  21.    cout << pre[0];  22.}  23.  24.int main()  25.{  26.    string pre, mid;  27.    while (cin >> pre >> mid)  2

6、8.    {  29.        PreMid(pre, mid);  30.        cout << endl;  31.    }  32.}  而已知后序遍历和中序遍历求前序遍历的过程差不多，但由于后序遍历是最后才访问根节点的 所以要从后开始搜索，例如上面的例子，后序遍历为gbdehfca，中序遍历为dgbaechf 后序遍历中的最后一个元素是根节点，a，然后查找中序中a的位置 把中序遍历分成dgbaechf，而因为节点个数要对应 后序遍历分为gbdehfca，gbd为左子树，ehfc为右子树，这样又可以递归计算了 其他一些附带的代码上面已经有，这里

7、就不重复贴了，具体代码如下： C++代码  1.bool BackMid(const string &back, const string &mid)  2.{  3.    if (back.size() == 0)  4.        return false;  1.      2.    if (back.size() == 1)  3.    {  4.        cout << back;  5.        return true;  6.    }  7.      8.    //根节点是最后一个元素  9.    int