问题
单项选择题
一个具有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。