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

admin2014-04-17  48

问题 下列说法中,正确的是(    )。
    Ⅰ.具有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
0

最新回复(0)