满二叉树

高度为 h 且含有 $2^h-1$ 个结点的二叉树称为满二叉树。

1000

定义要点

  • 只有最后一层有叶子结点。
  • 所有非叶结点都有两个孩子，不存在度为 1 的结点。
  • 第 i 层结点数达到二叉树第 i 层的最大值 $2^{i-1}$。
  • 高度为 h 时，总结点数达到二叉树高度为 h 时的最大值 $2^h-1$。

编号性质

按层序从 1 开始编号时：

  • 结点 i 的左孩子编号为 2i。
  • 结点 i 的右孩子编号为 2i+1。
  • 若 i > 1，结点 i 的双亲编号为 $\lfloor i/2\rfloor$。

这些编号关系也适用于完全二叉树中实际存在的结点。

容易混淆点

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

判断满二叉树时，不能只看“形状比较饱满”，要看是否满足高度 h 与结点数 $2^h-1$ 的严格关系。