1. 概述
在计算机科学中，二叉树是一种非常流行且广泛使用的数据结构。它由一个根节点、一个左子节点（或左子树）和一个右子节点（或右子树）组成。每个节点最多有两个子节点（不包括叶子节点），基于这一特性，可以衍生出多种变体。
在本文中，我们将重点讨论其中两种常见的变体：完全二叉树（Complete Binary Tree） 和 几乎完全二叉树（Almost Complete Binary Tree）。
2. 满二叉树（Full Binary Tree）
2.1 定义
在介绍完全二叉树和几乎完全二叉树之前，我们先回顾一下满二叉树的概念。
满二叉树是指：除了叶子节点外，每个内部节点都恰好有两个子节点。换句话说，所有叶子节点必须处于同一层级，且所有非叶子节点都有两个子节点。
2.2 示例
如下图所示，是一个典型的满二叉树：
图中每个非叶子节点都有两个子节点，且所有叶子节点（D, E, F, G）都处于同一层。
再来看另一个例子：
节点 C 是一个非叶子节点，但它只有一个子节点。这不符合满二叉树的定义，因此这不是一个满二叉树。
3. 完全二叉树（Complete Binary Tree）
3.1 定义
完全二叉树是一种特殊的二叉树，其定义如下：
- 所有层级（除最后一层外）必须完全填满；
- 最后一层的节点可以不满，但必须从左向右连续填充；
- 每一层的节点数应为 2^L（L 表示层级）。
⚠️ 一个关键点是：不能跳过左边节点而只填充右边节点。
3.2 示例
来看一个例子：
- 层级 0（根节点 A）有 1 个节点；
- 层级 1（B, C）有 2 个节点；
- 层级 2（D, E）有 2 个节点，且从左到右填充。
✅ 所有条件都满足，因此这是一个完全二叉树。
再看另一个例子：
- 层级 0 和 1 均满足；
- 层级 2 中，节点 B 没有子节点，而节点 C 有子节点。
❌ 这不符合“从左向右填充”的规则，因此这不是一个完全二叉树。
3.3 应用场景
完全二叉树在以下场景中非常常见：
- 堆（Heap）数据结构（最大堆、最小堆）；
- 堆排序（Heap Sort）算法；
- 优先队列（如 Java 中的
PriorityQueue）； - 外部排序算法（External Sorting）。
4. 几乎完全二叉树（Almost Complete Binary Tree）
4.1 定义
几乎完全二叉树是完全二叉树的一种特例，其定义如下：
- 插入节点必须按层进行，且每层必须从左向右插入；
- 最后一层不一定填满；
- 每一层（除最后一层外）节点数必须为 2^L；
- 所有内部节点必须完全填满；
- 几乎完全二叉树一定是完全二叉树，但完全二叉树不一定是几乎完全二叉树。
4.2 示例
来看一个例子：
这个树是之前满二叉树的例子中删除了节点 G 后的结果。
- 层级 0 和 1 满足完全填满；
- 层级 2 是最后一层，未完全填满；
- 所有节点从左向右填充。
✅ 因此这是一个几乎完全二叉树。
再看另一个例子：
节点 C 缺少左子节点，但有右子节点。
❌ 这违反了“从左向右填充”的规则，因此这不是几乎完全二叉树。
5. 完全二叉树 vs 几乎完全二叉树
| 参数 | 完全二叉树 | 几乎完全二叉树 |
|---|---|---|
| 定义 | 最后一层可能未满，但节点必须从左填充 | 最后一层一定未满，节点必须从左填充 |
| 性质 | 可能是或不是几乎完全二叉树 | 一定是完全二叉树 |
| 应用 | 堆结构、优先队列、排序算法 | 无特定应用，通常使用完全二叉树替代 |
6. 总结
本文详细介绍了以下三种二叉树类型：
- 满二叉树（Full Binary Tree）；
- 完全二叉树（Complete Binary Tree）；
- 几乎完全二叉树（Almost Complete Binary Tree）。
通过定义和示例对比，我们明确了：
- 完全二叉树允许最后一层未满，但必须从左填充；
- 几乎完全二叉树是完全二叉树的子集；
- 两者在堆结构等数据结构中有着广泛应用。
理解它们之间的区别有助于在实现堆、优先队列等结构时做出更合理的数据结构选择。