模拟卷 数据结构 二叉树的遍历 选择题
第 5 题

由某种序列可以唯一地确定一棵二叉树,不能唯一地确定一棵二叉树是( )。

A. 先序序列和中序序列 B. 后序序列和中序序列 C. 中序序列和层序序列 D. 先序序列和层序序列

二叉树的遍历

[tag_link]

正确答案:D

在二叉树的遍历序列中,不同的序列组合对二叉树结构的确定能力不同。

已知先序序列和中序序列可以唯一确定一棵二叉树,因为先序序列提供根节点信息,中序序列区分左右子树; 同样,后序序列和中序序列也可以唯一确定二叉树,原理类似。

中序序列和层序序列也能唯一确定二叉树,因为层序序列给出层次顺序,结合中序序列的左右子树信息,可以通过递归方式重建二叉树。

然而,先序序列和层序序列不能唯一确定二叉树。 例如,考虑只有两个节点A和B的二叉树:若B是A的左子节点,先序序列为A、B,层序序列为A、B; 若B是A的右子节点,先序序列同样为A、B,层序序列也为A、B。 这两个不同的二叉树产生了相同的先序和层序序列,因此无法唯一确定结构。

因此,不能唯一确定二叉树的选项是D。