将森林转换为对应的二叉树，若在二叉树中，结点u是结点v的父结点的父结点，则在原来的森林中，u和v可能具有的关系是_______。 Ⅰ．父子关系Ⅱ．兄弟关系Ⅲ．u的父结点与v的父结点是兄弟关系

admin2015-12-30 16

问题将森林转换为对应的二叉树，若在二叉树中，结点u是结点v的父结点的父结点，则在原来的森林中，u和v可能具有的关系是_______。
Ⅰ．父子关系Ⅱ．兄弟关系Ⅲ．u的父结点与v的父结点是兄弟关系

选项 A、只有Ⅱ
B、Ⅰ和Ⅱ
C、Ⅰ和Ⅲ
D、Ⅰ、Ⅱ和Ⅲ

答案B

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