Question

设一颗完全二叉树共有700个结点 ，则该二叉树中有------个叶子结点。

答案我有 我需要解题关键过程！

Answer 1

350个叶子节点。

根据二完全叉树的性质：

如果一棵具有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）。可根据完全二叉树的结点总数计算出叶子结点数。

则该题叶子结点数根据完全二叉树的概念可知，度为1的结点数要么为1，要么为0，二叉树总结点数n＝n0+n1+n2＝n/2，得出n0＝n/2＝700/2=350，所以本题答案是350个叶子结点。

扩展资料：

1、完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。

2、完全二叉树特点

叶子结点只可能在最大的两层上出现,对任意结点，若其右分支下的子孙最大层次为L，则其左分支下的子孙的最大层次必为L 或 L+1；

（1）只允许最后一层有空缺结点且空缺在右边，即叶子结点只能在层次最大的两层上出现；

（2）对任一结点，如果其右子树的深度为j，则其左子树的深度必为j或j+1。 即度为1的点只有1个或0个

参考资料：百度百科-完全二叉树

Answer 2

根据二叉树的性质3可知：叶子结点数n0＝n2+1，根据完全二叉树的概念可知，度为1的结点数要么为1，要么为0，二叉树总结点数N＝n0+n1+n2＝2n0+n1－1，得出n0＝（N+1－n1）/2＝N/2向上取整，所以本题答案是350个叶子结点。

扩展资料：

完全二叉树的性质：

①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）。可根据完全二叉树的结点总数计算出叶子结点数。

参考资料：完全二叉树–百度百科

Answer 3

解法一：根据二叉树的性质3可知：叶子结点数n0＝n2+1，根据完全二叉树的概念可知，度为1的结点数要么为1，要么为0，二叉树总结点数N＝n0+n1+n2＝2n0+n1－1，得出n0＝（N+1－n1）/2＝N/2向上取整，所以本题答案是350个叶子结点。解法二：易求出总层数和末层叶子数。总层数k=log2N向上取整 =10;且前9层总结点数为2^9-1=511 (完全二叉树的前k-1层肯定是满的)所以末层叶子数为700-511=189个。请注意叶子结点总数≠末层叶子数！还应当加上第k-1层（靠右边）的0度结点个数。末层的189个叶子只占据了上层的95个结点（189/2 )，上层（k=9)右边的0度结点数还有2^(9-1)-95=161个。所以，全部叶子数＝189(末层)＋161(k-1层)=350个。

Answer 4

因为700 是偶数，所以n1=1 n0=n2+1
所以
n0+1+n0-1=700
n0=350

Answer 5

完全二叉树的层数 : [log2 (700)]+1=10
前9层总共共有的结点：2^9-1=511
第十层的结点：700-511=189
第九层的结点：2^(9-1)=256
第10层对应第9层的结点有：189/2=94……1
第九层的子结点：256-95=161
第十层子结点：189
子结点总数：189+161=350
你应该可以看懂吧，如果不懂的话，就多看看定义。