深圳幻海软件技术有限公司 欢迎您!

根据二叉树的先序、中序、后序遍历构建二叉树-图文详解

2023-06-30

引言:根据一颗二叉树,可以得出他的先序、中序、后序三种遍历方式,那么如果我们知道了他的前序、中序、后序遍历,如何绘制出这颗二叉树呢?1、二叉树三种遍历方式的特性特性A,对于前序遍历,第⼀个肯定是根节点;特性B,对于后序遍历,最后⼀个肯定是根节点;特性C,利⽤前序或后序遍历,确定根节点,在中序遍历中,

引言:根据一颗二叉树,可以得出他的先序、中序、后序三种遍历方式,那么如果我们知道了他的前序、中序、后序遍历,如何绘制出这颗二叉树呢?

1、二叉树三种遍历方式的特性

  1. 特性A,对于前序遍历,第⼀个肯定是根节点;
  2. 特性B,对于后序遍历,最后⼀个肯定是根节点;
  3. 特性C,利⽤前序或后序遍历,确定根节点,在中序遍历中,根节点的两边就可以分出左⼦树和右⼦树;
  4. 特性D,对左⼦树和右⼦树分别做前⾯3点的分析和拆分,相当于做递归,我们就可以重建出完整的⼆叉树;

2、根据二叉树的先序、中序遍历构建二叉树

例:已知一颗二叉树的前序遍历和中序遍历的顺序如下,请绘制出这颗二叉树
前序遍历的顺序是: CABGHEDF
中序遍历的顺序是: GHBACDEF

步骤:
1、第⼀步,我们根据特性A,可以得知根节点是C,然后,根据特性C,我们知道左⼦树是:GHBA,右⼦树是:DEF

2、第⼆步,取出左⼦树,左⼦树的前序遍历是:ABGH,中序遍历是:GHBA,根据特性A和C,得出左⼦树的⽗节点是A,并且A没有右⼦树。

3、第三步,使⽤同样的⽅法,前序是BGH,中序是GHB,得出⽗节点是B,GH是左⼦树,没有右⼦树

4、第四步,前序是GH, 中序是GH, 所以 G是⽗节点, H是右⼦树, 没有左⼦树

5、第五步,回到右⼦树,它的前序是EDF,中序是DEF,依然根据特性A和C,得出⽗节点是E,左右节点是D和F。到此,我们得到了这颗完整的二叉树,如下图所示。

3、根据二叉树的中序、后序遍历构建二叉树

例:已知一颗二叉树的中序遍历和后序遍历的顺序如下,请绘制出这颗二叉树
中序遍历的顺序是: GHBACDEF
后序遍历的顺序是: HGBADFEC

步骤:
1、第⼀步,我们根据特性B,可以得知根节点是C,然后,根据特性C,我们知道左⼦树是:GHBA,右⼦树是:DEF

2、第⼆步,取出左⼦树,左⼦树的后序遍历是:HGBA,中序遍历是:GHBA,根据特性B和C,得出左⼦树的⽗节点是A,并且A没有右⼦树。

3、第三步,使⽤同样的⽅法,后序是HGB,中序是GHB,得出⽗节点是B,GH是左⼦树,没有右⼦树

4、第四步,后序是HG, 中序是GH, 所以 G是⽗节点, H是右⼦树, 没有左⼦树

5、第五步,回到右⼦树,它的后序是DFE,中序是DEF,依然根据特性B和C,得出⽗节点是E,左右节点是D和F。到此,我们得到了这颗完整的二叉树,如下图所示。

文章知识点与官方知识档案匹配,可进一步学习相关知识
算法技能树首页概览48594 人正在系统学习中