回 帖 发 新 帖 刷新版面

主题:一棵完全二叉树上有1001个结点,其中叶子结点的个数是

一棵完全二叉树上有1001个结点,其中叶子结点的个数是(    )
A. 250   B. 500    C.254     D.505      E.以上答案都不对 

帮我看一下,按叶结点数*2-1=总结点数,那该是500吧,但那是对满二叉树而言的吧 
小弟我不太懂

回复列表 (共4个回复)

沙发

帮我看看呀

板凳

我找到规律了
若总结点数为奇数,则有叶结点数*2-1=总结点数 即叶结点数=(总结点数+1)/2
若总结点数为偶数,则有叶结点数*2=总结点数 即叶结点数=总结点数+1/2
如若总结点数为11,则有叶结点数*2-1=11     即叶结点数=(11+1)/2=6
如若总结点数为18,则有叶结点数*2=18     即叶结点数=(18)/2=9
那,这道题就是1001+1然后除以2得501了,我这样想对吗?

3 楼


对于满二叉树来讲,高度为9得总结点数是511个,高度为10得总结点数是1023个。
这样题目中要求的完全二叉树应是高度为10的完全二叉树,完全二叉树的叶结点在最
下面两层,本题中就是在第9、第10两层出现。
第10层叶结点数目是:1001-511=490(即总结点数-前9层结点的总数目)。
第9层叶结点数目是:对于满二叉树,第10层的结点数应该是512个,而现在的完全
二叉树的第10层有490个结点,相对于完全二叉树少了22个结点,少的这22个结点将
导致第9层出现22/2=11个叶结点。
所以这棵完全二叉树得总的叶子结点数是:490+11=501。

4 楼


501=490+11


1001-511=490
第8层可有512个叶子
(512-490)/2=11第八层的叶子数
第9层的叶子数=490
490+11=501
按完全二叉树的定义算

我来回复

您尚未登录,请登录后再回复。点此登录或注册