【程序设计训练】二叉树遍历，从前序、中序到后序

小咪咪 2022-12-01 15:58 73阅读 0赞

> 原文链接：[35.二叉树遍历，从前序、中序到后序][35.]  
> 个人思路仅供参考，如有不足欢迎交流。

## 【问题描述】 ##

二叉树是一种非常重要的数据结构，非常多其他数据结构都是基于二叉树的基础演变而来的。对于二叉树，深度遍历有前序、中序以及后序三种遍历方法。

三种基本的遍历思想为：

前序遍历：根结点 —> 左子树 —> 右子树

中序遍历：左子树—> 根结点 —> 右子树

后序遍历：左子树 —> 右子树 —> 根结点

比如，求以下二叉树的各种遍历  
![二叉树][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ5Nzc3Mjk1_size_16_color_FFFFFF_t_70_pic_center]  
前序遍历：1 2 4 5 7 8 3 6

中序遍历：4 2 7 5 8 1 3 6

后序遍历：4 7 8 5 2 6 3 1

需要你编写程序解决的问题是：已知一个二叉树的前序遍历和中序遍历的结果，给出该二叉树的后序遍历的结果。

## 【输入形式】 ##

有多组测试数据，每组测试数据三行，每组测试数据第一行只有一个正整数n，表示二叉树节点的数目，n=0意味着输入结束并且不需要处理。

每组测试数据第二行是二叉树的前序遍历的结果，是一个长度为n的字符串，每个节点由一个字符表示，字符是大小写英文字母及10个数字,不同的节点用不同的字符表示，也即无论前序遍历和中序遍历的字符串中没有重复的字符。

每组测试数据第二行是二叉树的中序遍历的结果，也是一个长度为n的字符串。

40%的测试数据1 ≤ n≤ 10；

30%的测试数据1 ≤ n≤ 20；

20%的测试数据1 ≤ n≤ 40；

10%的测试数据1 ≤ n≤ 62；

## 【输出形式】 ##

对于每组测试数据，输出一行，是一个长度为n的字符串，表示二叉树后序遍历的结果。

## 【样例输入】 ##

8
    12457836
    42758136
    4
    abcd
    abcd
    4
    abcd
    dcba
    0

## 【样例输出】 ##

47852631
    dcba
    dcba

## 【思路和做法】 ##

*  前序遍历的开头一定是根结点；
 *  在中序遍历中，根节点左侧一定是左子树，根节点右侧一定是右子树；
 *  后序遍历的顺序是左子树->右子树->根结点；
 *  提交代码（10/10分，C++）：

//35.二叉树遍历，从前序、中序到后序
    #include <iostream>
    using namespace std;
    
    void getHou(string qian, string zhong)
    {
        
        if (qian.length() < 1) //限制
        {
        
            return;
        }
        string data = qian.substr(0, 1);               //前序遍历的开头一定是根结点
        string::size_type findData = zhong.find(data); //在中序遍历中找到根结点的位置
        int posi = findData;                           //位置
        //后序遍历：左子树->右子树->根结点
        getHou(qian.substr(1, posi), zhong.substr(0, posi));   //遍历左子树
        getHou(qian.substr(posi + 1), zhong.substr(posi + 1)); //遍历右子树
        cout << data;                                          //根结点
    }
    
    int main()
    {
        
        int n;
        string qian, zhong;
        while (cin >> n && n != 0)
        {
        
            cin >> qian >> zhong; //输入前序遍历、中序遍历
            getHou(qian, zhong);  //得到后序遍历的结果
            cout << endl;
        }
        return 0;
    }

[35.]: https://afool.top/learning/35_traversing_binary_tree/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ5Nzc3Mjk1_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/9439c68ec0914b63a8f5690d07580a99.png