第 6 题
由 4 棵树组成的森林中，第一、第二、第三和第四棵树中的结点数分别为 30、10、20、5，当把森林转换成二叉树后，对应二叉树中根结点的右子树的左子树的结点数为（ ）。
A. 29 B. 9 C. 25 D. 19
[tag_link]
正确答案：B
将森林转换成二叉树时，采用“左孩子右兄弟”的表示法。
对于由多棵树组成的森林，转换规则为：取第一棵树的根作为二叉树的根，根的左子树由第一棵树中根的子树森林转换而成，根的右子树由剩余树组成的森林转换而成。
给定森林中四棵树的结点数分别为 30、10、20、5。 转换后二叉树的结构如下：
- 二叉树的根对应第一棵树的根。 >
- 根的左子树由第一棵树中除根外的 29 个结点转换而成，结点数为 29。 >
- 根的右子树由第二、三、四棵树（结点数共 10+20+5=35）转换而成。 >
根的右子树本身也是一棵二叉树，其根对应第二棵树的根。 > 该右子树的左子树由第二棵树中除根外的子树森林转换而成，第二棵树有 10 个结点，除根外有 9 个结点，因此该左子树的结点数为 9。 >
故根结点的右子树的左子树的结点数为 9。 >