5.3_3由遍历序列构造二叉树

不同二叉树的中序、前序、后序、层次遍历序列可能相同：

一个二叉树对应的中序、前序、后序、层次遍历是唯一的，但是一个中序、前序、后序、层次序列对应的二叉树形态不是唯一的，即不能由某一种序列推出唯一二叉树形态

 由遍历序列构造二叉树：

如下必须有中序遍历才能构造二叉树

前序+中序序列构造二叉树：

例子1，第2、3张图例子：

由前序遍历(根左右)可知A是根节点，由中序遍历(左根右)知BDC是A的左子树、E是A的右子树，即可得到第2张概括图，再去拆分BDC左子树，由左子树的前序遍历序列长度=左子树的中序遍历序列长度得前序遍历序列中的DBC是A的左子树，由前序序列可知D是根节点，再由中序遍历BDC顺序知B是D的左子树、C是B的右子树，最终得到第3张图。

即由前序序列得到根节点和各子树的根节点，再由中序遍历得到根节点的左右子树节点

例子2：

由前序遍历知D是根节点，由中序遍历知EAF是D的左子树节点，HCBGI是D的右子树节点，再由前序序列知在前序序列中AEF是D的左子树，由前序序列知A是根节点，由中序序列知E和F分别是A的左右子树，再看A的右子树，由前序序列知BCHGI中B是根节点，由中序序列知HC是B的左子树、GI是B的右子树，再去拆分HC，再由前序序列CH知C是根节点，由中序序列知H是C的左子树，C后边除了B没有其他节点，即C没有右子树，再去拆分GI，由前序序列知GI中的G是根节点，由中序序列知G作为根节点右边是I左边除B之外无其他节点，则I是G的右子树G没有左子树

 后序+中序序列构造二叉树：

原理上同由后序遍历序列确定根节点，由中序序列确定各个根节点的左右节点

例子3：

如下由后序序列(左右根)知最后一个节点D是根节点，由中序序列知D的左边EAF是D的左子树，D的右边HCBGI是D的右子树，先看D的左子树，由左子树后序序列长度=左子树中序序列长度知在后序序列中EFA是左子树，且由后序序列左右根知A是根节点，由中序序列知A的左边是E为A的左子树，A的右边是F即F为A的右子树，再看D的右子树HCBGI，由相同长度后序序列HCIGB知B是根节点，由中序序列知HC是B的左子树、GI是B的右子树，再看HC，由后序序列知C是根节点，由中序序列知H是C的左子树，C的右边除了B之外无其他节点即C无右子树，再看GI，由后序序列IG知G是根节点，由中序序列知I是G的右子树，G的左边除B之外无其他节点即G无左子树

 

  层序+中序序列构造二叉树：

原理同上，通过层序遍历找根节点，由中序序列确定各个根节点的左右节点

如下例4：

层序遍历一层层的，第一个出现的是根节点即D，由中序序列知EAF是D的左子树、HCBGI是D的右子树，先看D的左子树，由层序遍历知第2、3节点为D的左子树和右子树的根节点，分别是A、B，再通过中序遍历知E、F分别是A的左子树，HC和GI分别是B的左子树、右子树，再通过层序遍历知E、F的后边是C和G则C和G为根节点(或者说C在H前边所以C是H的根节点，G在I前边G是I的根节点？)，再由中序遍历知H在C的左边即H是C的左子树，C无右子树，I是G的右子树，G无左子树

例5：

如下由层序序列知第一个节点A是根节点，由中序序列知A的左边无其他节点即A无左子树，则右边右子树是CBED序列，再去看层序序列知A后边跟着的B是右子树的根节点，由中序序列知C是B的左子树，ED是B的右子树，再由层序序列知先排C，C的后边是D即C和D一层D是根节点，由中序序列知E在D的左边E是D的左子树，D的右边无其他节点即D没有右子树

知识回顾：

 

如果两两组合中没有中序遍历构造不成唯一的二叉树：

 

。。。。。。。。。。。。。。