设一棵完全二叉树共有700个结点,则在该二叉树中有多少叶子结点
1个回答
展开全部
解法一:
根据二叉树的性质3可知:叶子结点数n0=n2+1,
根据完全二叉树的概念可知,度为1的结点数要么为1,要么为0,
二叉树总结点数N=n0+n1+n2=2n0+n1-1,
得出n0=(N+1-n1)/2=N/2向上取整,
所以本题答案是350个叶子结点.
解法二:
易求出总层数和末层叶子数.总层数k=log2N向上取整 =10;
且前9层总结点数为2^9-1=511 (完全二叉树的前k-1层肯定是满的)
所以末层叶子数为700-511=189个.
请注意叶子结点总数≠末层叶子数!
还应当加上第k-1层(靠右边)的0度结点个数.
末层的189个叶子只占据了上层的95个结点(189/2 ),上层(k=9)右边的0度结点数还有2^(9-1)-95=161个.
所以,全部叶子数=189(末层)+161(k-1层)=350个.
ymdtpzge 2014-11-25
根据二叉树的性质3可知:叶子结点数n0=n2+1,
根据完全二叉树的概念可知,度为1的结点数要么为1,要么为0,
二叉树总结点数N=n0+n1+n2=2n0+n1-1,
得出n0=(N+1-n1)/2=N/2向上取整,
所以本题答案是350个叶子结点.
解法二:
易求出总层数和末层叶子数.总层数k=log2N向上取整 =10;
且前9层总结点数为2^9-1=511 (完全二叉树的前k-1层肯定是满的)
所以末层叶子数为700-511=189个.
请注意叶子结点总数≠末层叶子数!
还应当加上第k-1层(靠右边)的0度结点个数.
末层的189个叶子只占据了上层的95个结点(189/2 ),上层(k=9)右边的0度结点数还有2^(9-1)-95=161个.
所以,全部叶子数=189(末层)+161(k-1层)=350个.
ymdtpzge 2014-11-25
本回答被提问者和网友采纳
已赞过
已踩过<
评论
收起
你对这个回答的评价是?
推荐律师服务:
若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询