25版王道数据结构课后习题详细分析第五章树与二叉树 5.4 树、森林

一、单项选择题

————————————————————

解析：

正确答案：D

————————————————————

解析：森林与二叉树具有对应关系，因此，我们存储森林时应先将森林转换成二叉树，转换的方法就是“左孩子右兄弟”，与树不同的是，若存在第二棵树，则二叉链表的根结点的右指针指向的是森林中的第二棵树的根结点。若此森林只有一棵树，则根结点的右指针为空。因此，右指针可能为空也可能不为空。

正确答案：D

————————————————————

解析：与树转换为二叉树不同，森林中的每棵树是独立的，因此先要将每棵树的根结点全部视为兄弟结点的关系。森林转换为二叉树后，树2作为树1的根结点的右子树，树3作为树2的根结点的右子树，因此森林F对应的二叉树根结点的右子树上的结点个数是M2+M3。

正确答案：D

————————————————————

解析：森林转换为二叉树后，二叉树的根结点为第Ⅰ棵树的根结点，二叉树的根结点的左子树包含第Ⅰ棵树的所有孩子，因此森林F对应的二叉树的根结点的左子树上的结点数是a-1。

正确答案：C

————————————————————

解析：森林转换成二叉树时采用孩子兄弟表示法，根结点及其左子树为森林中的第一棵树。右子树为其他剩余的树。所以,第一棵树的结点个数为m-n。

正确答案：A

————————————————————

解析：

正确答案：D

————————————————————

解析：将森林中每棵树的根结点视为兄弟结点的关系，再按照“左孩子右兄弟”的规则来进行转化。

正确答案：B

————————————————————

解析：根据森林与二叉树转换规则“左孩子右兄弟”。二叉树B中右指针域为空代表该结点没有兄弟结点。森林中每棵树的根结点从第二个开始依次连接到前一棵树的根的右孩子，因此最后一棵树的根结点的右指针为空。另外，每个非终端结点，其所有孩子结点在转换之后，最后一个孩子的右指针也为空，所以树B中右指针域为空的结点有n+1个。

正确答案：C

————————————————————

解析：在树的孩子兄弟表示法中，若一个结点没有孩子（即叶结点)，则表现为该结点的左指针域为空，因此本题答案为“6”。至于“5个结点的左、右指针域都为空"，表示树中有5个结点既没有孩子又没有兄弟，约束条件比题中的“求叶结点的个数”要求更严格。

正确答案：B

————————————————————

解析：

正确答案：B

————————————————————

解析：

正确答案：C

————————————————————

解析：在二叉树B中，X是其双亲的右孩子，因此在树T中，X必是其双亲结点的右兄弟，换句话说，X在树中必有左兄弟。

正确答案：D

————————————————————

解析：在森林的二叉树表示中，当M和N的父结点是二叉树根结点时，M和N在不同的树上。因此M和N可能无公共祖先。

正确答案：B

————————————————————

解析：

正确答案：B

————————————————————

解析：

正确答案：D

————————————————————

解析：将森林转化为二叉树相当于用孩子兄弟表示法来表示森林。在变化过程中，原森林某结点的第一个孩子结点作为它的左子树，它的兄弟作为它的右子树。森林中的叶结点由于没有孩子结点，转化为二叉树时，该结点就没有左结点，因此F中叶结点的个数等于T中左孩子指针为空的结点个数,。此题还可通过一些特例来排除A、B和D。

正确答案：C

————————————————————