Skip to content

2017年 408 数据结构 第 4 题

数据结构2017年选择题2分

题目

要使一棵非空二叉树的先序序列与中序序列相同,其所有非叶节点须满足的条件是( )。

错因

A

把方向想反了。如果只有左子树,先序是 根, 左,中序是 左, 根——根的位置一前一后,序列必然不同。这种错往往出在没动笔画一个最小例子(一个父节点 + 一个左孩子)就直接选了。

C

度均为 1 的二叉树是一条"链",但链可以朝左也可以朝右:朝左不行,朝右才行。C 没区分方向,条件不充分——所以即使度都是 1,先序中序也未必相同。

D

度均为 2 意味着每个非叶节点同时有左孩子和右孩子。先序 根, 左子树, 右子树 永远会先访问根再访问左子树,而中序 左子树, 根, 右子树 必先访问左子树——两个序列首位元素不同,绝不可能相等。

总解析

把先序和中序写在一起对比:

顺序访问规则
先序 → 左 → 右
中序左 → → 右

两者的差异点全在"根"和"左"的相对位置:先序先根后左,中序先左后根。要让它们逐位相同,唯一办法是让"左"消失——即每个非叶节点的左子树为空,只剩右子树。

这时两个序列都退化为:根 → 右 → 右 → ...,自然完全相同。

反过来:只要哪怕有一个节点存在左子树,那段子树就会让两个序列从此分叉。

最终答案是 B(只有右子树)

直观例子:右斜链 1 → 2 → 3(1 的右是 2,2 的右是 3),先序 1, 2, 3,中序也是 1, 2, 3。换成左斜链立刻反例:先序 1, 2, 3,中序 3, 2, 1

最后更新:

🎬 可视化演示
加载中...

提示:可在可视化区直接操作播放、步进、修改参数