完全二叉树（Complete Binary Tree）
除最后一层外，其余各层的节点都达到最大个数，最后一层靠左排列的二叉树。
定义
完全二叉树是一种特殊的二叉树，满足以下条件：
除最后一层外，其他各层的节点数都达到最大个数，且最后一层的节点都靠左对齐排列。
核心特性
| 特性 | 说明 |
|---|---|
| 节点排列 | 最后一层节点靠左排列，中间不能有空隙 |
| 数组存储 | 非常适合用数组存储，索引关系简单 |
| 与满二叉树关系 | 满二叉树是完全二叉树的特例（最后一层也全满） |
| 高度 | 对于 n 个节点，树高 h = ⌊log₂n⌋ + 1 |
数组存储索引关系
完全二叉树可以用数组存储，节点索引关系如下（1-based 索引）：
| 关系 | 计算公式 |
|---|---|
| 父节点 | parent(i) = i / 2 |
| 左子节点 | left(i) = i * 2 |
| 右子节点 | right(i) = i * 2 + 1 |
（0-based 索引时：parent(i) = (i-1)/2，left(i) = 2i+1，right(i) = 2i+2）
与类似概念对比
| 维度 | 完全二叉树 | 满二叉树（Perfect） | 二叉堆 |
|---|---|---|---|
| 节点排列 | 最后一层靠左 | 所有层全满 | 完全二叉树 + 堆性质 |
| 节点数 | 可以有空缺（仅限最后一层右侧） | 全满，共 2^h - 1 个 | 同完全二叉树 |
| 数组存储 | 适合 | 适合 | 通常用数组存储 |
| 典型应用 | 二叉堆底层结构 | 理论分析 | 优先级队列、堆排序 |
判断完全二叉树
算法思路（使用 BFS 层序遍历）：
- 遇到第一个空缺节点（null）后，后续不能再有非空节点
- 如果遇到 null 后还有非 null 节点，则不是完全二叉树
应用场景
- 二叉堆的底层结构：最大堆、最小堆都是完全二叉树
- 堆排序：利用完全二叉树的数组存储特性
- 优先级队列：基于二叉堆实现
- 数组存储的二叉树：节省指针空间，访问高效
注意事项
- 不是二叉搜索树：完全二叉树只关注结构，不关注节点值的大小顺序
- 最后一层必须靠左：这是与"完满二叉树"（Full Binary Tree）的关键区别
- 数组实现优势：不需要指针，通过索引计算父子关系，缓存友好