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 层所有的结点都连续集中在最左边，这就是完全二叉树。

Answer 2

求出所有没有左孩子的节点 即为答案 本题的答案为：501

1.一颗完全二叉树结点的序号规则是 从上到下 从左到右，易知 结点n的左孩子为2n

例如：结点1的左孩子为2，右孩子为3，结点2的左孩子为2*2=4，右孩子为2*2+1=5

以此类推。

2.假设有两个结点n，n+1 则 结点n若无左孩子结点 则 n+1 必无左孩子结点

例如 一颗完全二叉树共有9个结点 则结点5的左孩子结点为 5*2=10，但是不存在10号结点，

所以5号结点无左孩子，以此类推6号孩子亦为左孩子。

本题的完全二叉树共有1001个结点，则 501号开始的结点皆无左孩子，即1001-500=501 个结点没有左孩子，没有左孩子的结点即为叶子结点。