C语言数据机构：由中序遍历和层次遍历能不能唯一确定一颗二叉树？为什么说法不一致哪？

amario · 2018-4-30 01:53:11

由中序遍历和层次遍历能够唯一确定一颗二叉树。从下面的算法可知，每一步构造得到的二叉树结果是唯一的。
以下构造部分的答案来自百度知道：
假定树的层次遍历ABCDEFG HIJ中序遍历DBGEHJACIF
两种遍历顺序要结合着分析，才能画出这颗树的图

比如，层次遍历，先访问到A节点，说明A是树的根节点
那么在中序遍历结果里看：
DBGEHJ在A前面，说明这些节点，都在A左子树上
CIF在A的后面，说这些节点，都在A的右子树上
那么，树可以先这样画：
__________A________
________/____\_____
_____DBGEHJ__CIF___

再看层次遍历，A后面是B，说明B是A左子树的根节点
从上图中的先序遍历顺序DBGEHJ中看到：
D在B的前面，说明D在B的左子树上
GEHJ在B的后面，说明它们在B的右子树上
那么，树又可以画成：
_________A________
_______/____\_____
_____B________CIF__
____/__\____________
___D__GEHJ_________

如此循环，直到将整个树都画完全
结果如下：

_____________A_______________
___________/____\_____________
________B_________C__________
______/___\_________\_________
_____D_____E_________F_______
__________/__\_________\______
_________G____H_________I____
_______________\______________
_________________J____________

wang433 · 2018-4-30 01:53:12

结论：唯一
例：
层次：ABC　构成二叉树（设B与C或为A的子树，或为A的结点）
  A       A       A          A                A
/       /          /  \          \                \
B       B       B C          B                B
/          \                            \             /
C       C                            C       C
对应的中序序列:
（1）CBA （2） BCA （3） BAC       （4） ABC    （5） ACB

证明：
　　由于层次遍历的第一个元素一定为根（A），所以，我们分别证明以上五种情况在层次遍历的约束下，一定只能构造一棵树。
　　(1)由于A为根，所以CB一定为A的子孙。根据层次序列BC的顺序BC或为兄弟，或为父子关系。i)如果BC为兄弟，则其中序顺序一定是B*C，因此与（1）矛盾；ii)如果BC为父子关系，则B一定为父，C一定为子。再根据中序的顺序CB可以确定C为B的左孩子，因此。CBA与ABC一定能唯一确定一棵二叉树，即第一棵二叉树。
   （2）同理可以证明其它情况一定是唯一对应。

到底谁负了谁丶 · 2018-4-30 01:53:13

I是F的左子树

C语言数据机构：由中序遍历和层次遍历能不能唯一确定一颗二叉树？为什么说法不一致哪？

3 个回复