主题:一棵完全二叉树上有1001个结点,其中叶子结点的个数是
南月
[专家分:590] 发布于 2007-09-26 10:01:00
一棵完全二叉树上有1001个结点,其中叶子结点的个数是( )
A. 250 B. 500 C.254 D.505 E.以上答案都不对
帮我看一下,按叶结点数*2-1=总结点数,那该是500吧,但那是对满二叉树而言的吧
小弟我不太懂
回复列表 (共4个回复)
沙发
南月 [专家分:590] 发布于 2007-09-26 17:25:00
帮我看看呀
板凳
南月 [专家分:590] 发布于 2007-09-26 19:51:00
我找到规律了
若总结点数为奇数,则有叶结点数*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 楼
rainsunneau [专家分:60] 发布于 2007-09-30 11:25:00
对于满二叉树来讲,高度为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 楼
langxve [专家分:80] 发布于 2007-10-01 11:51:00
501=490+11
1001-511=490
第8层可有512个叶子
(512-490)/2=11第八层的叶子数
第9层的叶子数=490
490+11=501
按完全二叉树的定义算
我来回复