设一棵完全二叉树共有699个结点，则在该二叉树中的叶子结点数为？
叶子结点数是(699+1)/2=350 。
解题过程：
一、假设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
扩展资料：
一、完全二叉树的定义：
是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。
二、完全二叉树的性质：
如果一棵具有n个结点的深度为k的二叉树，它的每一个结点都与深度为k的满二叉树中编号为1~n的结点一一对应，这棵二叉树称为完全二叉树。
可以根据公式进行推导，假设n0是度为0的结点总数（即叶子结点数），n1是度为1的结点总数，n2是度为2的结点总数，则 ：
①n= n0+n1+n2 （其中n为完全二叉树的结点总数）；又因为一个度为2的结点会有2个子结点，一个度为1的结点会有1个子结点，除根结点外其他结点都有父结点。
②n= 1+n1+2*n2 ；由①、②两式把n2消去得：n= 2*n0+n1-1，由于完全二叉树中度为1的结点数只有两种可能0或1，由此得到n0=n/2 或 n0=(n+1)/2。
简便来算，就是 n0=n/2，其中n为奇数时（n1=0）向上取整；n为偶数时（n1=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
度为2，度为1，度为0。即这个结点有两个孩子结点，有一个孩子结点，没有孩子结点（叶结点）。
结点总数＝度为2的结点＋度为1的结点＋度为0的结点
在任意二叉树中，度为2的结点的数目比度为0的结点(叶结点)数目少一个。
例如，只有三个结点的二叉树，其度为2的结点数目为1（根结点），度为0的结点（叶结点）有两个。
0
／ \
0 0
完全二叉数中，没有度为1的结点。所以
结点总数＝度为2的结点＋度为0的结点
699＝N＋（N－1）
即N=（699+1）/2
=350
根据“二叉树的第i层至多有2^(i − 1)个结点；深度为k的二叉树至多有2^k − 1个结点（根结点的深度为1）”这个性质：
因为2^9-1 < 699 < 2^10-1 ,所以这个完全二叉树的深度是10，前9层是一个满二叉树，
这样的话，前九层的结点就有2^9-1=511个；而第九层的结点数是2^(9-1)=256
所以第十层的叶子结点数是699-511=188个；
现在来算第九层的叶子结点个数。
由于第十层的叶子结点是从第九层延伸的，所以应该去掉第九层中还有子树的结点。因为第十层有188个，所以应该去掉第九层中的188/2=94个；
所以，第九层的叶子结点个数是256-94=162，加上第十层有188个，最后结果是350个。
于是n0 + n1 + n2 = 699
按照二叉树的性质n0 = n2 +1
于是2n2 +n1 + 1 = 699
考虑到完全二叉树中度为1结点个数最多1个，因此n1 = 0
n2 = 349
所以n0 = 350，即叶子结点350个
|
广告 您可能关注的内容 |
