Question

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

Answer 1

由完全二叉树性质可知，若给每个结点依次序标上1~n序号，序号为
i
的结点（假设有两个孩纸存在）其左孩纸序号为
2i（皆为偶数），右孩纸序号为
2i
+
1
（皆为奇数），故
1001
为右孩子，其父结点序号为
500
（
2i
+
1
=
1001

解得
i
=
500
），故n2
=
500
（按规律501的孩纸序号应为501
*
2
=
1002
和
1003，
此题一共只有1001个结点，故501
没有孩纸），n1要么为
0
要么为
1
，奇数个结点时为最后一个叶子结点为右孩纸，偶数个结点时最后一个为左孩纸。
具体如下：
1、简介
完全二叉树的定义、性质以及算法见正文。这里补充一点：完全二叉树是效率很高的数据结构，堆是一种完全二叉树或者近似完全二叉树，所以效率极高，像十分常用的排序算法、Dijkstra算法、Prim算法等都要用堆才能优化，几乎每次都要考到的二叉排序树的效率也要借助平衡性来提高，而平衡性基于完全二叉树。
2、判断完全二叉树
完全二叉树：叶节点只能出现在最下层和次下层，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树
3、完全二叉树定义
若设二叉树的深度为h，除第
h
层外，其它各层
(1～h-1)
的结点数都达到最大个数，第
h
层所有的结点都连续集中在最左边，这就是完全二叉树。