目录
若只给出一棵二叉树的前/中/后/层 序遍历序列的一种,不能唯一确定一棵二叉树
前序遍历 + 中序遍历序列
前序遍历:根结点、前序遍历左子树,前序遍历右子树
中序遍历:中序遍历左子树,根结点,中序遍历右子树
例子:
(图有问题,绿色的点应该是c)
我们分析前序遍历第一个出现的结点一定为根结点,所以A为根结点,而中序遍历左边一定为左子树遍历的序列即BDC,右边右子树为E。
而同样的道理看BDC的话,由前序排列知D为根结点,由中序遍历知左子树为B,右子树为E。
后序+中序遍历序列
后序遍历: 前序遍历左子树 、 前序遍历右子树、根节点
中序遍历:中序遍历左子树,根结点,中序遍历右子树
例子
我们看这个题目后序遍历最右边为根结点,由中序遍历 可分为 左:EAF 右:HCBGI
看左边的序列 EAF ,而在后序遍历那为EFA,可知A为“根结点”,左:E 右:F
看右边的序列HCBGI,前序遍历那为HCIGB,可知B为“根结点”,左:HC 右:GI
最后可知 H在左,C在右,G在左 ,I 在右
层序遍历+中序遍历序列
开始时知道D在层序序列为第一个遍历所以,D为根结点,左子树:EAF,右子树:HCBGI
之后由中序遍历层序遍历知A为左子树的根结点,B为右子树的根结点,然后不难知A的左孩子为 E,右孩子为F。
由层序遍历知,EF后面为CG所以它俩在中间,C 和 G 分别在中间,在看中序遍历序列
C的左边挂H,G的右边挂I