【计算机基础题目】二叉树的前序中序后续遍历之间相互转换 详细例子

创作日志： 笔试题目，掌握了技巧之后这道题就是 so easy~

一、

1、已知二叉树的 前序和中序，可以求出后序
2、已知二叉树的 中序和后序，可以求出前序
3、已知二叉树的 前序和后序，无法求出唯一的中序

二、求法

求法是共通的。总结如下：

1、前序+中序 -> 后序

核心：用前序序列的第一个节点确定当前子树的根节点，用中序序列确定根节点的左子树和右子树

2、中序+后序 -> 前序

核心：用后序序列的最后一个节点确定当前子树的根节点，用中序序列确定根节点的左子树和右子树

发现区别了吗？唯一的区别就是确定根节点时，一个用第一个节点，一个用最后一个节点，别的步骤都一样。

三、举例计算

1、前序+中序 -> 后序

核心：用前序序列的第一个节点确定当前子树的根节点，用中序序列确定根节点的左子树和右子树

前序序列为：ABCDGEIHFJK
中序序列为：DCBGEAHFIJK

1）根据前序序列的第一个节点，首先确定了根节点A；

2）分割左右子树：
根据中序序列 DCBGEAHFIJK，A的左边肯定都是其左子树的值（DCBGE），右边都是其右子树的值（HFIJK）。因为前序遍历肯定先遍历完A的左子树，再去右子树，所以也可以根据这两个元素集合把前序序列划分成两部分：（BCDGE）与（IHFJK），则两个集合的第一个元素B、I 分别是A的左、右孩子（根据前序遍历原则）；

3）处理左子树：
左：前序（BCDGE），中序（DCBGE）。根据中序，B 的左边是左子树（DC），右边是右子树（GE）。根据前序，左子树（CD），右子树（GE）。

套娃处理左子树，前序（CD），中序（DC）：此子树的根节点一定是前序的第一个节点C，那么根据中序，D就是C的左孩子因为序列中它在C的左边。

套娃处理右子树，前序（GE），中序（GE）：同理，判断出根节点是G，E是G的右孩子。

4）处理右子树：
右：前序（IHFJK），中序（HFIJK）。根据中序，I 的左边是左子树（HF），右边是右子树（JK）。根据前序，左子树（HF），右子树（JK）。

套娃处理左子树，前序（HF），中序（HF）：根节点H，F是H的右孩子。

套娃处理右子树，前序（JK），中序（JK）：根节点J，K是J的右孩子。

细心的人就会发现所谓的“嵌套”处理就是递归的过程，不断地去找左右子树的根节点以及左右子树，直至序列为空。可以写成一个程序。

那么最后读一下上面那棵树的后序遍历顺序：DCEGBFHKJIA

2、中序+后序 -> 前序

核心：用后序序列的最后一个节点确定当前子树的根节点，用中序序列确定根节点的左子树和右子树

还是用刚刚的例子
后序：DCEGBFHKJIA
中序：DCBGEAHFIJK

1）根据后序序列的最后一个节点，确定了根节点A；
2）分割左右子树： 一样地根据中序序列，以A为分割点进行分割；
3）处理左子树： 后序：DCEGB，可以确定根节点是B；中序：DCBGE，可以确定左子树DC，右子树GE。
套娃左子树：后序DC，说明根节点是C，中序DC，说明D是C的左孩子。
套娃右子树：后序EG，说明根节点是G，中序GE，说明E是G的右孩子。
4）处理右子树： 后序：FHKJI，可以确定根节点是I，中序：HFIJK，可以确定左子树HF，右子树JK。
套娃左子树：后序FH，说明根节点是H，中序HF，说明F是H的右孩子。
套娃右子树：后序KJ，说明根节点是J，中序JK，说明K是J的右孩子。