与二叉树有关的题

设一棵完全二叉树共有700个结点，则在该二叉树中有多少个叶子结点？

回答不能只给答案，需要详细的解析。

计算结果：350个叶子结点

解法：

对完全二叉树而言，度为1的结点只能为0或1.设X,Y,Z分别为叶子结点、单支结点数、双支结点数的个数。则：
当Y=0时，700=X+0+Z=2Z+1,Z结果不为整数，故错。
当Y=1时，700=X+1+Z=2Z+2,Z=349.则:X=349+1=350.即叶子结点数为：350.
(二叉树中：叶子结点数=双支结点数+1.）

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

700/2=350

350 完全二叉树的定义：若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层从右向左连续缺若干结点，这就是完全二叉树。 可以算出，这棵二叉树共十层，1-9层的节点个数为2^9-1=511个,所以最后一层的节点个数为700-511=189个,189div2=95,那么倒数第二层的叶结点个数即是2^(9-1)-95=161个 所以所有的叶结点个数即为:189+161=350个