问题 单项选择题

一个具有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。

问答题 简答题
单项选择题