在上一篇文章《二叉树（Binary Tree）类型特点》中我们了解了二叉树的一些常见类型和特点，这篇我们专注说下完全二叉树的特性。

附图1

tree_four.jpg

完全二叉树特性：

• 度为1 的节点只有左子树
• 度为1 的节点要么是1个，要么是0个
• 同样节点数量的二叉树，完全二叉树高度是最小的

假设高度为h（ h ≥ 1 ）的完全二叉树，那么至少有个节点；最多有个节点；总节点数量为n 则 ≤ < , ≤ < ，伪代码：h = floor ( ) + , floor () 是向下取整的意思

以「附图一」为列推导：
只少有个节点：
= + + + …… + +
最多有个节点:
= + + + …… + , 即满二叉树 。
总节点数量为n , ≤ < , ≤ < ; 推导过程：
假如 = 4.8 ，则h= 5 ; = 5.2 , h= 6 ； = 6.0 ，h= 7; 由此可得：h = 向下取整 + 的结果
向下取整(floor) 和 向上取整（ceiling） 是不遵循四舍五入原则的

日常开发中的 除法默认都是向下取整的。以 Java 为例

int a = 5 / 2 ;
// 结果为2 ；不是2.5

一颗有n (n > 0 )个节点的完全二叉树 , 从上到下、从左到右对节点从1开始编号, 对任意第i个节点 ：

• 如果i = 1 ；它是根节点
• 如果i > 1 ；它的父节点 编号是 floor（ i / 2 ）,即：i / 2 向下取整
• 如果 2 * i ≤ n ；它的左子节点 编号是 2 * i
• 如果 2 * i > n ；它没有左子节点
• 如果 2 * i + 1 ≤ n ；它的右子节点 编号是 2 * i +1
• 如果 2 * i + 1 > n ；它没有右子节点

一颗有n (n > 0 )个节点的完全二叉树 , 从上到下、从左到右对节点从0开始编号, 对任意第i个节点 ：

• 如果i = 0 ；它是根节点
• 如果i > 0 ；它的父节点 编号是 floor（ （ i - 1）/ 2 ）,即：（ i - 1）/ 2 向下取整
• 如果 2 * i ≤ n -1 ；它的左子节点 编号是 2 * i + 1
• 如果 2 * i > n - 1 ；它没有左子节点
• 如果 2 * i + 2 ≤ n - 1 ；它的右子节点 编号是 2 * i +2
• 如果 2 * i + 2 > n - 1 ；它没有右子节点

假设有一颗完全二叉树的 总结点数量为 ，则他有多少个叶子节点

假设： 叶子节点数量为： ； 度为1 的节点数量为； 度为2 的节点数量为 ；
总节点数量为 = + + ，且 = + ； 则： = + -
完全二叉树中 度为1的节点要么为0， 要么为1 ；所以：
（1）当 = 1 时； = ， 必为偶数 ；
叶子节点数量为： = ；
非叶子节点数量： + =
（2）当 = 0 时； = ， 必为奇数 ；
叶子节点数量为： = ；
非叶子节点数量： + =
由此可得：
总结点数量为 ，
第一种方式：
是偶数 ，叶子节点数量为： = ；
是奇数 ，叶子节点数量为： = ；
则叶子节点数量为： = floor( ) ；floor( )是向下取整，
非叶子节点数量为： + = floor( ) ；floor() 是向下取整
代码中：

n0 = (n+ 1 )/ 2

或

n0 = n+ 1 >> 1

第二种方式：
叶子节点数量为： = ceiling( ) ；ceiling() 是向上取整
非叶子节点数量为： + = ceiling( ) ；ceiling() 是向上取整

在国外的一些教材中对一些特殊的二叉树会有一些不同的名字，下面简单的说明一下：

完满二叉树 （Full Binary Tree）

所有非叶子节点的度都为2 ； 也就是国内说的 “ 真二叉树”

完美二叉树 （Perfect Binary Tree）

所有非叶子节点的度都为2 ，且所有的叶子节点都在最后一层； 也就是国内说的 “ 满二叉树”

完全二叉树 （Complete Binary Tree）

和国内的定义是一样的