在上一篇文章《二叉树（Binary Tree）类型特点》中我们了解了二叉树的一些常见类型和特点，这篇我们专注说下完全二叉树的特性。
附图1
tree_four.jpg
完全二叉树特性：
- 度为1 的节点只有左子树
- 度为1 的节点要么是1个，要么是0个
- 同样节点数量的二叉树，完全二叉树高度是最小的
假设高度为h（ h ≥ 1 ）的完全二叉树，那么至少有个节点；最多有
个节点；总节点数量为
n 则 ≤
<
,
≤
<
，伪代码：h = floor (
) +
, floor () 是向下取整的意思
以「附图一」为列推导：
只少有个节点：
+
+
+ …… +
+
最多有个节点:
总节点数量为n,<
,
≤
<
; 推导过程：
假如的结果
向下取整(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）
和国内的定义是一样的
网友评论