试题-将森林F转换为对应的二叉树T，F中叶结点的个数等于（）

题目

将森林F转换为对应的二叉树T，F中叶结点的个数等于（）

A.T中叶结点的个数

B.T中度为1的结点个数

C.T中左孩子指针为空的结点个数

D.T中右孩子指针为空的结点个数

解答

正确答案是 C

在二叉树中，节点的左指针指向其孩子，节点的右指针指向其兄弟。所以在一颗二叉树中，如果某个节点的左指针为NULL，就说明这个节点在原来的森林中没有孩子，是叶子几点，如果某个节点的右指针为NULL，就说明这个节点在原来的森林中没有兄弟。

所以森林中的叶子节点=二叉树中左指针为NULL的个数

C 4条回复评论

人生赢家

森林变成二叉树：森林中每棵树都变成二叉树，然后再合起来。

而树变成二叉树：所有非叶节点，其第一个孩子会变为二叉树中的左孩子。

因此反过来说，二叉树中没有左孩子的节点，在原来的森林中一定是叶子节点。

发表于 2018-11-01 15:46:27

窦先生

二叉树变森林方法为右孩子A变兄弟节点。若该孩子节点A有左孩子，则带着左孩子一起分离形成独立的树。若无左孩子，则成为孤立节点。

因此选C

发表于 2018-11-01 15:46:03

心意

森林转换成二叉树的步骤：

1.先把森林中的每棵树转换成二叉树

2.第一颗二叉树不动，从第二颗二叉树开始，依次把后一颗二叉树的根结点作为前一颗二叉树的根结点的右孩子结点，用线连起来。当所有的二叉树连接起来后得到的二叉树就是由森林转换得到的二叉树。

发表于 2018-11-01 15:45:51

粽子

森林是由若干棵树组成，可以将森林中的每棵树的根结点看作是兄弟，由于每棵树都可以转换为二叉树，所以森林也可以转换为二叉树。

将森林转换为二叉树的步骤是：
（1）先把每棵树转换为二叉树；

（2）第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子结点，用线连接起来。当所有的二叉树连接起来后得到的二叉树就是由森林转换得到的二叉树。

发表于 2018-11-01 15:45:42