若一棵完全二叉树有768个结点,则该二叉树中叶结点的个数是()
A.257
B.258
C.384
D.385
解答:C。叶结点数为n,则度为2的...
用户登录可进行刷题及查看答案
解答:C。叶结点数为n,则度为2的结点数为n-1,度为1的结点数为0或1,本题中为1(总结点数为偶数),故而即2n=768。
方法一:构造
设完全二叉树高度为 h ,有不等式 2h−1≤768≤2h−1 ,解得 h=10 ,倒数第二层结点数为 28=256 ,倒数第一层结点数为 768−(29−1)=257 ,需要占用倒数第二层 ⌈257⌉=129 个结点作为父结点,叶结点只会出现在倒数第二层和倒数第一层,所以该二叉树中叶结点的个数是 257+(256−129)=384 。
方法二:性质
叶结点个数为 n0 ,度为 2 的非叶结点数为 n2=n0−1 ,该树为完全二叉树, 。
又 n0+n1+n2=768 ,解得 n0=384 。
登录后提交答案
暂无评论,来抢沙发