问题
单项选择题
一个具有767个节点的完全二叉树,其叶子节点个数为()。
A.383
B.384
C.385
D.386
答案
参考答案:B
解析:
设二叉树中总节点数,以及度为0、度为1和度为2的节点数分别为n,n0,n1和n2,依据二叉树的性质可得到下列等式:
n=n0+n1+n2
n=768
n-1=n1+2n2
通过化简可得到
769=2n0+n1
在完全二叉树中,度为1的节点要么没有,要么有1个。上面等式左边为一个奇数,等式右边2n0是一个偶数,要使等式成立,n1只能为奇数,即是1,所以叶子节点个数n0=384。