Question

求一道关于数据结构的题

一棵完全二叉树上有1001个结点，其中叶子结点的个数是？

Answer 1

完全二叉树，叶子数为n（n>=2），则节点数为2*n-1，可以用数学归纳法证明如下：

当n＝2时，很显然结点数为3（2个叶子，一个父结点），满足;

设当n=k时，节点数为2*k-1；

则当n＝k+1时，因是完全二叉树，在n=k时的情形下，此时某一个叶子，自己变成了一个父节点，下面增加2个叶子，此时叶子数为k+1，而节点数为2*k-1+2=2*(k+1)-1，仍满足上述要求，因此，上述结论成立。反之亦然。

证毕。