2. 考研
  3. 下列说法中，正确的是( )。 Ⅰ．具有10个叶子结点的二叉树中有9个度为2的结点 Ⅱ．设高度为5的二叉树上只有度为0和度为2的结点，则该二叉树中所包含的结点数至少为9 Ⅲ．一棵完全二叉树上有1001个结点，则可知叶子结点的个

下列说法中，正确的是( )。 Ⅰ．具有10个叶子结点的二叉树中有9个度为2的结点 Ⅱ．设高度为5的二叉树上只有度为0和度为2的结点，则该二叉树中所包含的结点数至少为9 Ⅲ．一棵完全二叉树上有1001个结点，则可知叶子结点的个

admin2014-04-17  25
问题 下列说法中，正确的是(    )。
    Ⅰ．具有10个叶子结点的二叉树中有9个度为2的结点
    Ⅱ．设高度为5的二叉树上只有度为0和度为2的结点，则该二叉树中所包含的结点数至少为9
    Ⅲ．一棵完全二叉树上有1001个结点，则可知叶子结点的个数为501个
    Ⅳ．高度为h的完全二叉树最少有2h个结点
选项 A、仅Ⅰ、Ⅱ
B、仅Ⅱ、Ⅲ、Ⅳ
C、仅Ⅰ、Ⅲ、Ⅳ
D、仅Ⅰ、Ⅱ、Ⅲ
答案D
解析 Ⅰ：二叉树叶子结点的个数比度为2的结点的个数多1，故Ⅰ正确。
    总结：这个性质在选择题中常有体现(见下面的补充例题)，并且需要灵活运用。比如题目可能问，二叉树中总的结点数为n，则树中空指针的个数是多少?可以将所有空指针看做叶子结点，则图6-6中原有的所有结点都成了双分支结点。因此，可得空指针域的个数为树中所有结点个数加1，即n+1个。
    这个性质还可以扩展，即在一棵度为m的树中，度为1的结点数为n1，度为2的结点数为n2，…，度为m的结点数为nm，则叶子结点数n0=1+n2+2n3+…+(m一1)nm。推导过程如下：
    总结点=n0+n1+n2+n3+…+nm……………………………①    总分支数=1×n1+2×n2+…+m×nm(度为m的结点引出m条分支)………………………②    总分支数=总结点数一1………………………………………………………………………③    将式①和式②代入式③并化简得    n0=1+n2+2n3+…+(m一1)nm    Ⅱ：最少结点的情况应该是除根结点层只有1个结点外，其余4层都有2个结点，因此结点总数为2×(5—1)+1=9，如图6-6所示，故Ⅱ正确。

    总结：设高度为h的二叉树只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为2h—1。
    Ⅲ：由二叉树的性质可知：n0=n2+1，且完全二叉树度为1的结点个数要么为0，要么为1。又因为二叉树的总结点个数n=n0+n1+n2。将n0=n2+1代入，可得n=2n0+n1-1：由n=1 001，得到2n0=1002+n1。  ①当n1=1时，无解。  ②当n1=0时，可解得n0=501。  故Ⅲ正确。
    Ⅳ：高度为h的完全二叉树中，第1层～第h一1层构成一个高度为h—1的满二叉树，结点个数为2h-1-1。第h层至少有一个结点，所以最少的结点个数=(2h-1-1)+1=2h-1，故Ⅳ错误。
转载请注明原文地址:https://kaotiyun.com/show/1Yxi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)