题6

题6

题目

Q:设森林 对应的二叉树是一棵具有 16 个结点的完全二叉树,则森林 中树的数目和结点最多的树的结点数分别是 ( ).
A. 2 和 8
B. 2 和 9
C. 4 和 8
D. 4 和 9

分析

A:
怎么把树还原成森林，不太熟悉

二叉树转换为树、森林

二叉树转换为普通树本质上就是之前的逆过程，步骤也就是反过来做而已，判断一棵二叉树能够转换成一棵树还是森林，标准很简单，那就是『只要看这棵二叉树的根结点有没有右孩子，有的话就是森林，没有的话就是一棵树』，如下，是一个二叉树

第一步，若结点 x 是其双亲 y 的左孩子，则把 x 的右孩子，右孩子的右孩子等等等等，依次都与 y 用连连连接起来，如下

第二步，去掉所有双亲到右孩子之间到连线（也就是之前到逆向）

最后老规矩，调整一下，就变成了我们之前的森林

Link to original

解

D
森林转换为二叉树后, 二叉树的根结点及其左子树由第 1 棵树转换得到, 二叉树的根结点的右子树由剩余的森林转换得到,以此类推,可以划分出第 棵树的结点。具有 16 个结点的完全二叉树的形态如下图所示, 沿二叉树的根结点往右下遍历, 共有 4 个结点, 可知森林中有 4 棵树, 其中第 1 棵树的结点数最多, 有 9 个。