问题 单项选择题

一个具有767个结点的完全二叉树,其叶子结点个数为()。

A.383

B.384

C.385

D.386

答案

参考答案:B

解析:

假设n0为度为0的结点总数(即叶子结点数),n1为度为1的结点总数,n2为度为 2的结点总数,由二叉树的性质可知:

n=n0+n1+n2 (1)

其中n为完全二叉树的结点总数。又根据二叉树的定义,有:

n=n1+2×n2+1 (2)

由公式(1)和(2)可得:

n2=n0-1 (3)

把(3)式代入(1)式,可得:

n=2n0+n1-1 (4)

根据本题的条件,有767=2n0+n1-1,即768-n1=2n0。现在我们只需确定n1就能求得n0了。根据完全二叉树的定义,一棵k层的完全二叉树,上面的k-1层为满二叉树,最后一层的结点都靠左边,又因为满二叉树中只有度为0和度为2的结点,没有度为1的结点,这也就意味着在完全二叉树中,只有倒数第二层,才可能有度为1的结点,这就限制了完全二叉树只可能有0个或1个度为1的结点,对于768-n1=2n0,n1显然为0 (因为等式的右边为偶数),所以n0=768/2=384。

填空题
填空题