完全二叉树¶

1. 定义性质¶

完全二叉树满足：

除了最后一层，前面每一层都必须填满；最后一层的结点必须从左到右连续排列。

也就是说：

可以缺右边，不能缺左边或中间。

2. 层序位置连续¶

如果按层序给二叉树的位置编号：

          1
       /     \
      2       3
    /  \    /  \
   4    5  6    7

那么一棵有 n 个结点的完全二叉树，结点必须占据：

1, 2, 3, ..., n

不能跳号。

例如：

1, 2, 3, 4, 5, 7

不是完全二叉树，因为位置 6 空了，却出现了位置 7。

3. 不能有右儿子但没有左儿子¶

如果一个结点出现：

只有右儿子，没有左儿子

那么这棵树一定不是完全二叉树。

例如：

  1
   \
    2

不是完全二叉树。

4. 左子树高度不能小于右子树高度¶

完全二叉树中，左边不能比右边矮。

所以必须满足：

height[left] >= height[right]

如果：

height[left] < height[right]

一定不是完全二叉树。

5. 左右子树高度差最多为 1¶

完全二叉树中，左右子树高度差只能是：

height[left] - height[right] == 0

或者：

height[left] - height[right] == 1

不能是负数，也不能大于 1。

也就是：

height[left] == height[right]

或：

height[left] == height[right] + 1

6. 左右高度相等时：左满，右完全¶

如果：

height[left] == height[right]

那么当前树要成为完全二叉树，需要满足：

左子树是满二叉树
右子树是完全二叉树

也就是：

isFull[left] && isComplete[right]

原因：右边已经长到和左边一样高了，左边必须已经填满。

7. 左子树比右子树高 1 时：左完全，右满¶

如果：

height[left] == height[right] + 1

那么当前树要成为完全二叉树，需要满足：

左子树是完全二叉树
右子树是满二叉树

也就是：

isComplete[left] && isFull[right]

原因：左边可以继续向下一层生长，但右边必须已经完整填满，不能有缺口。

8. 满二叉树一定是完全二叉树¶

满二叉树：

每一层都填满

完全二叉树：

前面每层填满，最后一层从左到右填

所以：

满二叉树一定是完全二叉树
完全二叉树不一定是满二叉树

9. 算法判断时常用的三个量¶

判断一棵子树是否是完全二叉树，常维护三个信息：

height[u]       // 子树高度
isFull[u]       // 是否是满二叉树
isComplete[u]   // 是否是完全二叉树

空子树通常可以看作：

height[0] = 0;
isFull[0] = true;
isComplete[0] = true;

这样递推会更方便。

10. 最核心的两条递推判断¶

对于结点 u，设左儿子为 l，右儿子为 r。

情况一：左右高度相等

height[l] == height[r] && isFull[l] && isComplete[r]

则 u 的子树是完全二叉树。

情况二：左边比右边高 1

height[l] == height[r] + 1 && isComplete[l] && isFull[r]

则 u 的子树是完全二叉树。

11. 总结¶

1. 完全二叉树按层填，最后一层从左到右连续。
2. 不能有右儿子但没有左儿子。
3. 左右高度差只能是 0 或 1。
4. 高度相等：左满右完全；左高 1：左完全右满。