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

今天药忘吃喽~ 2022-08-13 00:38 150阅读 0赞

首先介绍一下三种遍历顺序的操作方法：

**1.先序遍历**

(1)访问根结点；

(2)先序遍历左子树；

(3)先序遍历右子树。

** 2.中序遍历**

(1)中序遍历左子树；

(2)访问根结点；

(3)中序遍历右子树。

**3.后序遍历**

(1)后序遍历左子树；

(2)后序遍历右子树；

(3)访问根结点。

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

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

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

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

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

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

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

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

![SouthEast][]

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

另一种情况为已知中序和后序遍历序列求先序遍历序列，我们将分别在后面的博客中介绍。

————————未完，待续。。。————————

[SouthEast]: /images/20220810/a5b81efe6b12453c937ce5ec74b369d1.png

发表评论取消回复

表情：

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

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

相关阅读

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

两种特殊的二叉树完全二叉树: 完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满

快来打我*/ 2023年01月10日 14:39/ 0 赞/ 261 阅读

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

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

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

相关先序遍历和中序遍历求后序遍历

//由先序遍历和中序遍历得到后序遍历 //算法思想 //首先由先序遍历的到根节点 //然后分成左子树和右子树 //把先序遍历的第一个给后序遍历的最后一个 \

青旅半醒/ 2022年09月19日 10:39/ 0 赞/ 219 阅读

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

悠悠/ 2022年07月15日 01:15/ 0 赞/ 162 阅读

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

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

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