C语言数据机构：由中序遍历和层次遍历能不能唯一确定一颗二叉树
- 培训职业
- 2025-05-30 16:18:19
由中序遍历和层次遍历能够唯一确定一颗二叉树。从下面的算法可知，每一步构造得到的二叉树结果是唯一的。
以下构造部分的答案来自百度知道：
假定树的层次遍历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____________
多重随机标签