题目

若结点 p 与 q 在二叉树 T 的中序遍历序列中相邻，且 p 在 q 之前，则下列 p 与 q 的关系中，不可能的是( )。

I. q 是 p 的双亲

II. q 是 p 的右孩子

III. q 是 p 的右兄弟

IV. q 是 p 的双亲的双亲

错因

A

误认为"q 是 p 的双亲"不可能。其实只要 p 是 q 的左子树中最右下的结点（即 p 没有右孩子，且 p 处在 q 左子树的最右路径末端），中序遍历就会从 p 直接走到 q。例如最简单情况：p 是 q 的左孩子且 p 没有右子树，p 紧接着输出 q。所以 I 是可能的。

C

II 被错排除了。若 q 是 p 的右孩子且 q 没有左子树，中序"左→根→右"在访问完 p（根）后，下一步进入 p 的右子树，第一个访问的就是 q（因为 q 没有左子树）。所以 II 是可能的。选 C 的人可能想"右孩子之前要先遍历右子树的左子树"，没考虑到 q 没有左子树这一情形。

D

IV 被错排除了。"q 是 p 的双亲的双亲"——p 在 q 的左子树里，且 p 是 q 整个左子树中按中序遍历的最后一个结点。具体地，设 q 的左孩子是 x，p 位于 x 的右子树最右下位置（p 与 x 不直接相连，但 p 的某个祖先是 x，q 是 p 父亲的父亲）。中序走完 q 的左子树最后一个就是 p，然后 q 输出。例如：q 的左孩子 x 有右孩子 p（且 p 无右子树），此时 p 的双亲是 x、x 的双亲是 q——q 正是 p 的双亲的双亲。所以 IV 可能。

总解析

思路：中序遍历的递归定义 = 左子树 → 根 → 右子树。p 在 q 之前且相邻意味着两者间没有任何其他结点被访问。

逐项分析：

• I（q 是 p 的双亲）✓ 可能：p 是 q 的左子树最右下结点（最简形态：p 是 q 的左孩子且 p 无右子树）。
• II（q 是 p 的右孩子）✓ 可能：q 没有左子树时，p 输出后立刻进入右子树访问 q。
• III（q 是 p 的右兄弟）✗ 不可能：设它们的共同双亲是 f。中序顺序是「f 的左子树 → f → f 的右子树」。p 在 f 的左子树里、q 在 f 的右子树里，两者之间一定要先访问 f，p 与 q 不可能相邻。
• IV（q 是 p 的双亲的双亲）✓ 可能：p 是 q 左子树中按中序遍历的最末一个结点。例如 q 的左孩子 x 有右孩子 p（p 无右子树），中序顺序里 …→x→p→q→…，p 与 q 相邻。

只有 III 不可能。

最终答案是 B（仅 III）。