3.3 森林的基本概念与性质

3.3 森林的基本概念与性质

　　考试大纲涉及本节的知识点有：树的存储结构、森林转换二叉树的方法和树转换为二叉树的方法。

1．选择题题目部分

　　 ● 设在某树中，节点M、N是节点P上的第i、i+1个孩子，则在此树的二叉树表示中，节点M与N的关系是 （1） 。
　　 （1）A．M、N具有同一双亲 B．M是N的左孩子
　　 C．N是M的左孩子 D．N是M的右孩子
　　 ● 设F是一个森林，B是由F变换得到的二叉树。若F中有n个非终端节点，则B中右指针域为空的节点有 （2） 。
　　 （2）A．2n B．n-1 C．n+1 D．n
　　 ● 若一个具有n个节点、k条边的非连通无向图是一个森林（n＞k），则该森林中必有 （3） 棵树。
　　 （3）A．k B．n C．n-k D．n+k
　　 ● 任一棵树均可唯一地转换成与它对应的二叉树。由树转换成的二叉树中，节点 N 的左子女是N在原树里对应节点的 （4） ，而N的右子女是原树里对应节点的 （5） 。
　　 在图3-9所示二叉树中，图3-9（a）为 （6） ，图3-9（b）为 （7） ，图3-9（c）为 （8） 。

图3-9 二叉树

　　（4）A．最左子节点 B．最右子节点
　　 C．最邻近的右兄弟 D．最邻近的左兄弟
　　 （5）A．最左的兄弟 B．最右的兄弟
　　 C．最邻近的右兄弟 D．最邻近的左兄弟
　　 （6）A．查找树 B．满二叉树
　　 C．平衡树但不是满二叉树 D．B+树
　　 （7）A．查找树 B．满二叉树
　　 C．平衡树但不是满二叉树 D．B+树
　　 （8）A．查找树 B．满二叉树
　　 C．平衡树但不是满二叉树 D．B+树

2．选择题练习答案与分析

　　 题号（1）答案 D
　　 习题分析：
　　 由题可知，N是M的右兄弟，由树与二叉树的转换法则可知，在二叉树表示中，N为M的右孩子。
　　 题号（2）答案 C
　　 习题分析：
　　 把森林F中的n个非终端节点分为两类：度为1的节点和度大于1的节点。度为1的节点只有一个孩子，这个孩子在得到的二叉树B中必定没有右指针域；而度大于1的节点有两个或更多孩子，则最后一个孩子必定在B中没有右指针域；
　　 另外，森林中的根节点在组成二叉树时，其右指针域为空的节点是必定会出现一个，所以答案是n+1。
　　 对于这种类型的题目，若不能直接推导出结论，用特例的方法来解决是最好的。如图3-10所示为森林转换成二叉树。
　　 图3-10中左边的非终端节点有4个，转换成二叉树后右指针域为空的节点有5个。通过这个特例可以看到，本题的答案为C。
　　 题号（3）答案 C
　　  

　　习题分析：
　　假设该森林中有s棵树：T1，T2，…，TS，且每个Ti有ni个节点，ki条边（i=1,2,…,S），由树的等价条件可知：ki=ni-1，则k=k1+k2+…+ks=（n1-1）+（n2-1）+…+（ns-1）=n-s，故s=n-k，所以该森林中必有n-k棵树。
　　另外，还可以这样考虑，首先，把n个单独的节点看成n棵树，然后再逐条加入边。显然，每加入一条边，则树的棵数就减1（把两棵树合并成一棵树），而题目告诉我们，总共有k条边，所以，树的总数为n–k。

　　习题分析：
　　根据树到二叉树的转化规则，我们会发现：任一棵树均可唯一地转换成与它对应的二叉树。由树转换成的二叉树中，节点N的左子女是N 在原树里对应节点的最左子节点，而 N 的右子女是原树里对应节点的最邻近的右兄弟。
　　平衡二叉树又称为AVL树，是指树中任一节点的左右子树的高度大致相同。如果任一节点的左右子树的高度均相同（如满二叉树），则该二叉树就是完全平衡的。
　　二叉查找树是具有以下特性的二叉树：如果左子树非空，则左子树上所有节点的值都小于根节点；如果右子树非空，则右子树上所有节点的值都大于根节点；左、右子树本身也是一棵二叉排序树。
　　一棵深度为k且有2k-1（k≥1）个节点的二叉树就称为满二叉树，如果深度为k、有n个节点的二叉树中各节点能够与深度k的顺序编号的满二叉树从1到n标号的节点相对应，则称这样的二叉树为完全二叉树。
　　显然图3-9（a）满足平衡二叉树的定义，图3-9（b）满足查找树的定义，图3-9（c）满足满二叉树的定义。
　　3．训练自测表（如表3-4所示）

表3-4 选择题练习自测表