题14

题14

题目

Q:【2009 统考真题】将森林转换为对应的二叉树,若在二叉树中,结点 是结点 的父结点的父结点,则在原来的森林中, 和 可能具有的关系是 ( ).
I. 父子关系
II. 兄弟关系
III. 的父结点与 的父结点是兄弟关系
A. 只有 II
B. I 和 II
C. I 和 III
D. I、II 和 III

分析

A:第一步，连兄弟，留左子，然后根相连
肯定有3
居然没有3，选的居然是B
这个问题的关键还是普通树转换成二叉树这一步
关于普通树转成二叉树的考点
题12
题9
题13

解

B
森林与二叉树的转换规则为 “左孩子右兄弟”。在最后生成的二叉树中, 父子关系在对应森林关系中可能是兄弟关系或者原本就是父子关系。
情形 I: 若结点 是结点 的第二个孩子结点,转换时,结点 就变成结点 第一个孩子的右孩子,符合要求。
情形 II: 结点 和 是兄弟结点的关系,但二者之中还有一个兄弟结点 , 则转换后结点 就变为结点 的右孩子,而结点 则是结点 的右孩子,符合要求。

图 I

图 II
情形 III: 若结点 的父结点与 的父结点是兄弟关系,则转换后,结点 和 分别在两者最左父结点的两棵子树中, 不可能出现在同一条路径中。

图 III
【另解】由题意可知 是 的父结点的父结点,如下图所示,有四种情况:




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