主题：Ｊａｖａ数据结构问题
junfeilai
[专家分：0] 发布于 2007-09-20 23:54:00
设一棵完全二叉树共有699个结点，则在该二叉树中的叶子结点数为______。(b)
a. 349
b. 350
c. 255
d. 351
知道怎么解的大侠能不能给我个清楚一点的答案，谢了
最后更新于：2007-09-21 00:20:00
回复列表 （共6个回复）
沙发
wxpool [专家分：0] 发布于 2007-09-21 17:19:00
350
板凳
guofei_gf [专家分：180] 发布于 2007-09-23 01:35:00
完全二叉树的结点数与叶子结点数之间有一定的数学关系，你找一本数据结构的书看看吧
3 楼
lalar [专家分：150] 发布于 2007-09-28 15:35:00
在任意-棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n0=n2+1。
证明：因为二叉树中所有结点的度数均不大于2，所以结点总数(记为n)应等于0度结点数(n0)、1度结点(记为n1)和2度结点数(n2)之和：
n=n0+n1+n2 (式子1)
另一方面，1度结点有一个孩子，2度结点有两个孩子，故二叉树中孩子结点总数是：
nl+2n2
树中只有根结点不是任何结点的孩子，故二叉树中的结点总数又可表示为：
n=n1+2n2+1 (式子2)
由式子1和式子2得到：
n0=n2+1
完全二叉树(Complete BinaryTree)
若一棵二叉树至多只有最下面的两层上结点的度数可以小于2，并且最下一层上的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树
对于完全二叉树来说，只存在叶子(0度)和2度节点，故n=699=n0+n1+n2=2n0-1
n0=350
4 楼
yuru_1012 [专家分：580] 发布于 2007-09-28 16:11:00
(699+1)/2就可以了。完全二叉数叶结点个数就是(n+1)/2（n为总结点数）
5 楼
junfeilai [专家分：0] 发布于 2007-12-06 00:29:00
[quote](699+1)/2就可以了。完全二叉数叶结点个数就是(n+1)/2（n为总结点数）[/quote]
嗯，方法很好，很简单，很好记.........谢谢你呀
6 楼
行者买刀 [专家分：550] 发布于 2007-12-07 16:34:00
要知道个为什么，记是很难记住的哦．．．我们可以假设完全二叉树的深度为3．那么他总共有７个点
其中叶子为4．比非叶子多了１个．
我来回复
您所在位置：