二叉树由两种遍历推出整棵树-蒲公英云

二叉树由两种遍历推出整棵树

r囧r小猫 2022-01-21 10:39 233阅读 0赞

二叉树由两种遍历推出整棵树

二叉树的先序，中序，后序遍历中，任意知道两种就可以推出整棵树长什么样。思路都是一样的，这里以先序和中序为例。

以下这个过程涉及到逆向推导，请读者准备个草稿纸XD

例如：已知先序遍历和中序遍历，求整棵树的形状？
先序：A B D E H C F I J G
中序：D B H E A F J I C G

解：
先序遍历的第一个元素是根节点，所以A为根节点，通过中序遍历中的A的位置，我们可以将中序遍历的左子树和右子树分出来：
D B H E A F J I C G
左子树 … … 右子树
所以可以画出这样一个草图:

在这里插入图片描述

接下来我们再对左子树BDEH进行分析:
先序：A B D E H C F I J G
中序：D B H E A F J I C G
所以对左子树来说，先序和中序分别是：
先序：B D E H
中序：D B H E
所以同理B为根节点，分出左右子树:
中序：D B H E
其左子树为D右子树为HE
进一步细化这个图得到：
在这里插入图片描述
然后接着上面的继续：
先序：B D E H
中序：D B H E
所以对右子树来说，先序和中序分别是：
先序：E H
中序：H E
所以同理E为根节点，H为左子树。
进一步细化这个图得到：

现在的话，整个左边已经全部划分清楚了，现在来看右边部分：
总的排序：
先序：A B D E H C F I J G
中序：D B H E A F J I C G
所以对右子树来说，先序和中序分别是：
先序：C F I J G
中序：F J I C G
所以同理C为根节点，分出左右子树:
中序：F J I C G
得到左子树FJI和右子树G，细分之后画图：
在这里插入图片描述
现在再来分析FJI这棵树:
先序：F I J
中序：F J I
所以自然而然，根节点F。但这里注意以下，中序也是F在第一个位置，所以左子树为空，右子树为JI，所以右子树也像上面那样再划分一次，最后得到完整的树：
在这里插入图片描述