由遍历序列构造二叉树--王道

目录

前序遍历 + 中序遍历序列

后序+中序遍历序列

层序遍历+中序遍历序列

---

若只给出一棵二叉树的前/中/后/层 序遍历序列的一种，不能唯一确定一棵二叉树

 

前序遍历 + 中序遍历序列

 前序遍历：根结点、前序遍历左子树，前序遍历右子树

 中序遍历：中序遍历左子树，根结点，中序遍历右子树

 例子：

（图有问题，绿色的点应该是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