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

这篇具有很好参考价值的文章主要介绍了根据二叉树的先序、中序、后序遍历构建二叉树-图文详解。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

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

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

特性A，对于前序遍历，第⼀个肯定是根节点；
特性B，对于后序遍历，最后⼀个肯定是根节点；
特性C，利⽤前序或后序遍历，确定根节点，在中序遍历中，根节点的两边就可以分出左⼦树和右⼦树；
特性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。到此，我们得到了这颗完整的二叉树，如下图所示。
根据二叉树的先序、中序、后序遍历构建二叉树-图文详解文章来源地址https://www.toymoban.com/news/detail-455988.html

到了这里，关于根据二叉树的先序、中序、后序遍历构建二叉树-图文详解的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！