已知一棵二叉树序列口诀的中序遍历序列和后序遍历序列。如何画出这棵二叉树序列口诀，并将其转换为森林？

来源：蜘蛛抓取(WebSpider) 时间：2023-12-10 16:35 标签： 二叉树序列口诀
其实，只要知道其中任意两种遍历的顺序，我们就可以推断出剩下的一种遍历方式的顺序，这里我们只是以：知道前序遍历和中序遍历，推断后序遍历作为例子，其他组合方式原理是一样的。要完成这个任务，我们首先要利用以下几个特性：特性A，对于前序遍历，第一个肯定是根节点；特性B，对于后序遍历，最后一个肯定是根节点；特性C，利用前序或后序遍历，确定根节点，在中序遍历中，根节点的两边就可以分出左子树和右子树；特性D，对左子树和右子树分别做前面3点的分析和拆分，相当于做递归，我们就可以重建出完整的二叉树；我们以一个例子做一下这个过程，假设：前序遍历的顺序是: CABGHEDF中序遍历的顺序是: GHBACDEF第一步，我们根据特性A，可以得知根节点是C，然后，根据特性C，我们知道左子树是：GHBA，右子树是：DEF。C/ GHBA DEF第二步，取出左子树，左子树的前序遍历是：ABGH，中序遍历是：GHBA，根据特性A和C，得出左子树的父节点是A，并且A没有右子树。C/ A DEF/GBH第三步，使用同样的方法，前序是BGH，中序是GHB，得出父节点是B，GH是左子树,没有右子树。C/ A DEF/B/GH第四步,前序是GH, 中序是GH, 所以 G是父节点, H是右子树, 没有左子树.
C
/
\
A
DEF
/
B
/
G
\
H
第四步，回到右子树，它的前序是EDF，中序是DEF，依然根据特性A和C，得出父节点是E，左右节点是D和F。C/ A E/ / B D F/G
\
H
到此，我们得到了这棵完整的二叉树，因此，它的后序遍历就是 : HGBADFEC

我要回帖

更多关于 二叉树序列口诀 的文章

 

随机推荐