完全二叉树

当一棵二叉树的结点与同高度满二叉树中编号 1..n 的结点一一对应时，称为完全二叉树。

1000

定义的等价理解

完全二叉树可以理解为：从满二叉树最下一层的最右侧开始，连续删去若干结点后得到的二叉树。

也可以按层序扫描理解：

  • 从上到下、从左到右依次编号。
  • 结点编号必须连续占据 1..n。
  • 一旦层序位置上出现空缺，后面不能再出现非空结点。

特点

  • 只有最后两层可能有叶子结点。
  • 最多只有一个度为 1 的结点。
  • 如果某结点只有一个孩子，则一定是左孩子。
  • 按层序编号后，仍满足左孩子 2i、右孩子 2i+1、双亲 $\lfloor i/2\rfloor$。
  • i <= ⌊n/2⌋ 的结点是分支结点，i > ⌊n/2⌋ 的结点是叶子结点。

常见判断错误

若某个结点没有左孩子却有右孩子，则一定不是完全二叉树。

若最后一层中间出现空位，而右侧还有结点，也不是完全二叉树。完全二叉树的最后一层必须从左向右连续填充。

完全二叉树的高度、叶子数、度为 1 的结点数等推导见二叉树常考性质。