设一颗完全二叉树共有700个结点 ,则该二叉树中有------个叶子结点。

论坛 期权论坛 期权     
z84616995z   2018-4-26 13:58   3347   2
答案我有  我需要解题关键过程!
分享到 :
0 人收藏

2 个回复

倒序浏览
2#
cn#upQpQuQGG  1级新秀 | 2018-4-30 01:56:30 发帖IP地址来自
解法一:根据二叉树的性质3可知:叶子结点数n0=n2+1,根据完全二叉树的概念可知,度为1的结点数要么为1,要么为0,二叉树总结点数N=n0+n1+n2=2n0+n1-1,得出n0=(N+1-n1)/2=N/2向上取整,所以本题答案是350个叶子结点。解法二:易求出总层数和末层叶子数。总层数k=飪玪og2N向上取整 =10;且前9层总结点数为2^9-1=511 (完全二叉树的前k-1层肯定是满的)所以末层叶子数为700-511=189个。请注意叶子结点总数≠末层叶子数!还应当加上第k-1层(靠右边)的0度结点个数。末层的189个叶子只占据了上层的95个结点(飪
3#
shaoqi08110820  1级新秀 | 2018-4-30 01:56:31 发帖IP地址来自
因为700 是偶数,所以n1=1  n0=n2+1
所以
n0+1+n0-1=700
n0=350
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

积分:
帖子:
精华:
期权论坛 期权论坛
发布
内容

下载期权论坛手机APP