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,仍满足上述要求,因此,上述结论成立.反之亦然.

证毕.