将森林转换为对应的二叉树，若在二叉树中，结点 u 是结点 v 的父结点的父结点，则在原来的森林中， u 和 v 可 能 具 有 的 关 系 是 ( ) 。

I. 父子关系

Ⅱ.兄弟关系

Ⅲ.u 的父结点与 v 的父结点是兄弟关系

A. 只有Ⅱ

B. I 和 Ⅱ

C. I 和 Ⅲ

D. I 、Ⅱ 和 Ⅲ

[tag_link]

正确答案：B

森林与二叉树的 转换规则 为“左孩子右兄弟”。在最后生成的二叉树中，父子关系在对应森林关系中可能是兄弟关系或原本就是父子关系。情形 I：若结点 V 是结点 u 的第二个孩子结点，在转换时，结点 V 就变成结点 u 第一个孩子的右孩子，符合要求。 情形 II：结点 u 和 V 是兄弟结点的关系，但二者之中还有一个兄弟结点 k, 则转换后，结点 V 就变为结点 k 的右孩子，而结点 k 则是结点 u 的右孩子，符合要求。 情形 III: 若结点 u 的父结点与 v 的父结点是兄弟关系，则转换后，结点 u 和 v 分别在两者最左父结点的两棵子树中，不可能出现在同 一条路径中。

【逆向法】由题意可知 u 是 v 的父结点的父结点，如下图所示有 4 种情况：

根据树与二叉树的转换规则，将这 4 种情况转换成树种结点的关系。(1) 在原来的树中 u 是 v 的父结点的父结点；(2) 在树中 u 是 v 的父结点；(3) 在树中 u 是 v 的父结点的兄弟；(4) 在树中 u 与 v 是兄弟关系。由此可知 I 和 II 正确。