二叉树系列（二）：已知中序遍历序列和后序遍历序列，求先序遍历序列

悠悠 2022-08-13 00:38 156阅读 0赞

前面已经介绍过三种遍历方法的规则，为了大家看着方便，这里我们在重新介绍一遍：

**1.先序遍历**

(1)访问根结点；

(2)先序遍历左子树；

(3)先序遍历右子树。

** 2.中序遍历**

(1)中序遍历左子树；

(2)访问根结点；

(3)中序遍历右子树。

**3.后序遍历**

(1)后序遍历左子树；

(2)后序遍历右子树；

(3)访问根结点。

知道了二叉树的三种遍历规则，只要有中序遍历序列和前后任一种遍历序列，我们就可以求出第三种遍历序列，今天我们研究的是已知中序和后序遍历序列，求先序遍历序列。

已知该二叉树的中序遍历序列为：D-B-G-E-A-C-F，后序遍历序列为：D-G-E-B-F-C-A。

接下来我们就可以求出该二叉树的先序遍历序列，具体步骤如下：

第一步：还是先求root根节点，根据后序遍历规则我们可知root为后序遍历序列的最后一个节点，因此该二叉树的root节点为A。

第二步：求root的左子树和右子树，这点我们还是从中序遍历序列中找出，位于root节点A左侧的D-B-G-E为root的左子树，位于A右侧的C-F为右子树。

第三步：求root的左孩子leftchild和右孩子rightchild，leftchild为左子树的根节点，rightchild为右子树的根节点。我们可以找到左子树D-B-E-G在后序遍历序列中的排列顺序为D-G-E-B，由于后序遍历最后访问根节点，所以B为左子树的根节点，即B为root的leftchild；同理root的rightchild为C。

第四步：我们可以根据上面的步骤找到B的左子树和右子树，以及C的左子树和右子树，然后分别求出左右子树的根节点。以此类推，只要求出根节点及其leftchild和rightchild，剩下的过程都是递归的，最后我们就可以还原整个二叉树。

根据以上步骤我们求出的二叉树如下图所示：

![SouthEast][]

最后我们直接可以根据先序遍历的遍历规则得出该二叉树的先序遍历序列为：A-B-D-E-G-C-F。

通过和上一篇博客联系，我们可以看出，不管是知道中序序列和先序序列还是知道中序序列和后序序列求另外一种序列的方法都大同小异，但是从求root的左右子树可以看出，中序序列必须为已知条件。目前以自己的水平还不能根据先序和后序来求出中序，在此不敢妄加断言能或者不能，哪位大神知道结果还希望不吝赐教。

[SouthEast]: /images/20220810/866489cc20af4bdd8ddde7aceff0eefd.png

发表评论取消回复

表情：

评论列表（有 0 条评论，156人围观）

还没有评论，来说两句吧...

相关阅读

相关层序遍历序列和中序遍历序列构建二叉树

输入节点个数后两行分别输入层次遍历序列、中序遍历序列使用build()函数建立二叉树，先找到根节点，再划分左右子树，分别构建两棵子树。并将左右节点分别保存至lch、

ゝ一世哀愁。/ 2023年07月21日 05:56/ 0 赞/ 14 阅读

相关二叉树的遍历——先序遍历、中序遍历、后序遍历

遍历二叉树（本文的二叉树均使用指针方式构建）先序遍历操作定义：若二叉树为空，则空操作；否则： 1. 访问根节点； 2. 先序遍历左子树； 3

淡淡的烟草味﹌/ 2022年12月01日 15:44/ 0 赞/ 269 阅读

相关二叉树系列（二）：已知中序遍历序列和后序遍历序列，求先序遍历序列

前面已经介绍过三种遍历方法的规则，为了大家看着方便，这里我们在重新介绍一遍： 1.先序遍历 (1)访问根结点； (2)先序遍历左子树； (3)先序遍历

悠悠/ 2022年08月13日 00:38/ 0 赞/ 157 阅读

相关二叉树系列（一）：已知先序遍历序列和中序遍历序列，求后序遍历序列

首先介绍一下三种遍历顺序的操作方法： 1.先序遍历 (1)访问根结点； (2)先序遍历左子树； (3)先序遍历右子树。 2.中序遍历

今天药忘吃喽~/ 2022年08月13日 00:38/ 0 赞/ 166 阅读

相关已知二叉树先序遍历中序遍历求其后序遍历、重建二叉树

已知二叉树先序遍历中序遍历求其后序遍历 (注：已知中序遍历序列和剩下两种遍历序列中的一种都可以确定二叉树，即可得到另一种遍历序列，但是已知前序遍历和后

水深无声/ 2022年08月09日 01:53/ 0 赞/ 195 阅读

相关根据前序遍历序列和中序遍历序列重建二叉树

问题描述: > 输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列\{1,2,4,7,3

柔光的暖阳◎/ 2022年07月16日 03:40/ 0 赞/ 208 阅读

相关根据前序遍历序列和中序遍历序列创建二叉树

一个前序遍历序列和一个中序遍历序列可以确定一颗唯一的二叉树。根据前序遍历的特点, 知前序序列(PreSequence)的首个元素(PreSequ

矫情吗；*/ 2022年07月15日 01:15/ 0 赞/ 216 阅读

相关二叉树遍历（已知中序、先序求后序）

二叉树的遍历 Time Limit: 1000ms Memory Limit: 32768KB This problem will be judged on HRBU

灰太狼/ 2022年06月09日 10:38/ 0 赞/ 214 阅读

相关二叉树遍历（已知先序、中序求后序）

【例3-4】求后序遍历时间限制: 1000 ms 内存限制: 65536 KB 提交数: 11 通过数: 9 【题目描述】输入一棵二叉树的先

柔情只为你懂/ 2022年06月09日 10:30/ 0 赞/ 224 阅读

相关二叉树(先序遍历，中序遍历，后序遍历)

二叉树定义每个节点的子节点数(度)不能大于2 先序遍历定义：从二叉树的根结点出发，当第一次到达结点时就输出结点数据，按照先向左在向右的方向访问。

悠悠/ 2021年10月01日 09:18/ 0 赞/ 482 阅读