题12

题12

题目

Q:设 是树 中的一个非根结点, 是 所对应的二叉树. 在 中, 是其双亲结点的右孩子, 下列结论中正确的是 ( ).
A. 在树 中, 是其双亲结点的第一个孩子
B. 在树 中, 一定无右边兄弟
C. 在树 中, 一定是叶结点
D. 在树 中, 一定有左边兄弟

分析

A:T是一个普通树，B是T转化得到的二叉树
方法是，兄弟连线去掉次子

普通树转换为二叉树

我们借助图片来进行了解，首先下图是一颗普通的树，它有三个结点，所以明显不是二叉树

如果将其转换成相应的二叉树分为两个步骤

• 在树中所有的兄弟结点之间加一连线
• 对每个结点，除了保留与其长子的连线外，去掉该结点与其他孩子的连线

所以我们首先执行『在兄弟结点之间添加连线』

然后在去除『非长子外』的连线

最后，我们在稍微调整一下位置，就可以得出我们想要的二叉树

总结一下，基本的步骤如下

• 加线，在所有兄弟结点之间加一条连线
• 去线，对树中每个结点，只保留它与第一孩子结点的连线，删除它与其他孩子结点之间的连线
• 层次调整，以树的根结点为轴心，将整棵树顺时针旋转一定的角度，使之结构层次分明

Link to original

解

D
在二叉树 中, 是其双亲的右孩子,因此在树 中, 必是其双亲结点的右兄弟,换句话说, 在树中必有左兄弟。