Question

设一棵完全二叉树共有839个结点，则在该二叉树中有多少个叶子结点 答案是420 求解释

Answer 1

1、求深度。因为2的9次方=512,2的10次方=1024。显然有839个结点的完全二叉树的深度为10(说明总共有10层)
2、求最后一层的叶子结点。最后一层叶子节点数=总节点数839-第9层及之前的所有节点数511（计算出来的，即2的n次方-1，n为层数）=328
3、判断上一层是否有叶子结点。因为328/2=164<256(也就是第9层的结点数)，所以第九层有叶子结点。第9层的叶子节点数=256-164=92
4、求总的叶子节点数。总叶子节点数=第9层叶子节点数+最后一层叶子节点数=92+328=420
（够详细了吧）

Answer 2

设该树深度为n。根据完全二叉树性质 ，829对2取对数，值应该大于等于n-1而小于n，由此解得n。 然后前n-1层的节点都是满的，可算出最后一层的节点数k，然后（k+1）/2取整=r，就是第n-1层含有子节点的个数，那么用n-1层的节点数减去r得到该层的叶子节点数s。最后k+s即为所求

如哪一步不会求，可追问

Answer 3

可以根据公式进行推导，假设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，就可根据完全二叉树的结点总数计算出叶子结点数。