Question

一棵完全二叉树共有个节点，该二叉树有多少叶子节点？怎么算，谢谢

Answer 1

满意答案望远镜8级2010-03-22完全二叉树看是几层的，比如3层完全二叉树，就有7个结点，结点总数是（2的3次方）减1个；叶子结点数是2的（3减1次方）个，就是4个。如果是n层完全二叉树，结点总数是（2的n次方）减1个；叶子结点数是2的（n减1次方）个；会了就非常简单。这回你明白了吗？
追问：
如果完全二叉树700个结点，有多少叶子结点
回答：
所谓完全二叉树，是不可能有700个结点的，完全二叉树的第N层，都会是2的N-1次幂个结点，而上一层，则是N-2次幂个结点，所以总节点数应该是2N次幂减1，700不是一个这样的数，所以不会有700个结点。如果是两层，那应该是4－1＝3个结点，三层，是8－1＝7个结点四层，是16－1＝15个结点五层，是32－1＝31个结点六层，是64－1＝63个结点七层，是128－1＝127个结点八层，是256－1＝255个结点九层，是512－1＝511个结点十层，是1024－1＝1023个结点。。。。因此，不会出现700个结点的完全二叉树。
追问：
可是我做到这个题了啊！
回答：
你确定是完全二叉树吗？
有“完全”二字吗？
追问：
题目中确实有啊，答案是350
回答：
正好是总结点数的一半！
那这个好记了

Answer 2

一楼的答案是对的，但解释严重有问题。“完全二叉数中，没有度为1的结点。”这句话是错误的。
完全二叉树定义：
若设二叉树的高度为h，除第
h
层外，其它各层
(1～h-1)
的结点数都达到最大个数，第
h
层从右向左连续缺若干结点，这就是完全二叉树。
完全二叉树叶子结点的算法：
如果一棵具有n个结点的深度为k的二叉树，它的每一个结点都与深度为k的满二叉树中编号为1~n的结点一一对应，这棵二叉树称为完全二叉树。
可以根据公式进行推导，假设n0是度为0的结点总数（即叶子结点数），n1是度为1的结点总数，n2是度为2的结点总数，由二叉树的性质可知：n0＝n2＋1，则n=
n0＋n1＋n2（其中n为完全二叉树的结点总数），由上述公式把n2消去得：n=
2n0+n1－1，由于完全二叉树中度为1的结点数只有两种可能0或1，由此得到n0＝（n＋1）/2或n0＝n/2，合并成一个公式：n0＝（n＋1）/2
，就可根据完全二叉树的结点总数计算出叶子结点数。
因此叶子结点数是(699+1)/2=350