3.3 森林的基本概念与性质

3.3 森林的基本概念与性质


3.3 森林的基本概念与性质
  考试大纲涉及本节的知识点有:树的存储结构、森林转换二叉树的方法和树转换为二叉树的方…

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。

题号 (4) (5) (6) (7) (8)
答案 A C C A B

  习题分析:
  根据树到二叉树的转化规则,我们会发现:任一棵树均可唯一地转换成与它对应的二叉树。由树转换成的二叉树中,节点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 选择题练习自测表

题    号 考  查  点 得    分
(1) 树转换成二叉树  
(2) 森林转换成二叉树  
(3) 森林和树的概念  
(4)~(8) 树转换成二叉树、查找树、平衡树、B+的概念  
3.3 森林的基本概念与性质

    关于作者: admin

    这里可以再内容模板定义一些文字和说明,也可以调用对应作者的简介!或者做一些网站的描述之类的文字活着HTML!

    为您推荐

    发表评论

    电子邮件地址不会被公开。 必填项已用*标注

    评论列表 人参与

    联系我们

    联系我们

    8888-88888888

    在线咨询: QQ交谈

    邮箱: email@admin.com

    工作时间:周一至周五,9:00-17:30,节假日休息

    关注微信
    微信扫一扫关注我们

    微信扫一扫关注我们

    关注微博
    返回顶部