题42

题42

题目

[!question]+
【2022 统考真题】若结点 与 在二叉树 的中序遍历序列中相邻,且 在 之前,则下列 与 的关系中,不可能的是 ( ).
I. 是 的双亲
II. 是 的右孩子
III. 是 的右兄弟
IV. 是 的双亲的双亲
A. 仅 I
B. 仅 III
C. 仅 II、III
D. 仅 II、IV

分析

[!NOTE]+
中序遍历中相邻，因为中序是左根右
左根右左根右
看上面这个字符串组合，两个相邻，要么是兄弟，要么是父子
p在q之前
也就是p是左，q是根
或者p是根，q是右
再或者，p是右，q是左，但是此时两者不是同一颗树，而q这颗树应该更在上面的，也就是高度比较小，p这颗树更深，也就是对应的第四个选项
如果是右兄弟，说明是同级别，也就是说，要到兄弟，必然和根相邻

解

[!done]+
B
对于此类题,每种情况只需举出一个反例即可。如图 1 所示, 是 的双亲,中序遍历序列为 ,选项 I 可能。
如图 2 所示, 是 的右孩子,中序遍历序列为 ,选项 II 可能。如图 4 所示, 是 的双亲的双亲,中序遍历序列为 ,选项 IV 可能。
如图 3 所示, 是 的右兄弟, 是 和 的父结点,中序遍历要求先遍历左子树,再访问根结点,最后遍历右子树, 因此一定先访问 ,再访问 ,最后访问 和 不可能相邻出现,选项 III 不可能。

图 1

图 2

图 3

图 4