数据结构与算法 / 系统课时
完全二叉树与数组表示
完全二叉树与数组表示
完全二叉树把树形层级紧凑地映射到连续数组中,因此无需保存父子指针,也能在常数时间定位亲属节点。本课将建立结构判定、下标公式与代码验证之间的对应关系。
学习目标
- 识别完全二叉树与满二叉树、普通二叉树的区别。
- 掌握从数组下标计算父节点、左孩子和右孩子的方法。
- 能在代码中正确处理根节点、叶节点和越界边界。
核心原理
完全二叉树要求除最后一层外的每一层都被填满,最后一层的节点必须从左向右连续出现。它不要求所有叶节点处于同一层,因此完全二叉树不一定是满二叉树。

采用从 0 开始的数组下标时,节点 i 的关系为:
- 父节点下标:当
i > 0时为⌊(i - 1) / 2⌋。 - 左孩子下标:
2 * i + 1。 - 右孩子下标:
2 * i + 2。 - 子节点下标只有在小于数组长度
n时才有效。
数组按层序存储节点,因此访问父子位置都是 O(1)。保存 n 个节点需要 O(n) 空间,并且不再需要额外的左右指针。含 n 个节点的完全二叉树高度为 ⌊log2 n⌋。
完整可运行示例
下面的 Python 程序按数组下标输出每个节点的直接亲属关系。将代码保存为 complete_tree.py 后运行。
python
def parent_index(index):
# 根节点没有父节点。
return (index - 1) // 2 if index > 0 else None
def left_index(index):
return 2 * index + 1
def right_index(index):
return 2 * index + 2
values = ["A", "B", "C", "D", "E", "F"]
for index, value in enumerate(values):
relations = []
parent = parent_index(index)
if parent is not None:
relations.append(f"parent={values[parent]}")
# 只有落在数组范围内的子节点才真实存在。
left = left_index(index)
if left < len(values):
relations.append(f"left={values[left]}")
right = right_index(index)
if right < len(values):
relations.append(f"right={values[right]}")
print(f"{value}[{index}]: {', '.join(relations)}")运行命令:
bash
python complete_tree.py预期输出
text
A[0]: left=B, right=C
B[1]: parent=A, left=D, right=E
C[2]: parent=A, left=F
D[3]: parent=B
E[4]: parent=B
F[5]: parent=C常见错误
把一基公式直接用于零基数组会造成整体偏移。例如,零基数组的左孩子不能写成 2 * i。另一个常见问题是先访问 values[2 * i + 2] 再检查范围,这会在缺少右孩子时抛出越界异常;应先比较计算结果与 len(values)。
判断结构时还要注意“从左向右连续”这一条件。若最后一层先出现空位,后面又出现节点,即使其他层完整,也不是完全二叉树。
本课练习
- 对数组
["A", "B", "C", "D", "E", "F", "G", "H"],计算下标3的父节点和两个孩子下标,并判断哪些孩子真实存在。 - 编写函数
is_complete_layout(items),其中None表示空位;一旦发现空位,后续不能再出现非空节点。使用至少三个测试用例验证结果。
本课总结
- 完全二叉树的最后一层必须从左向右连续填充。
- 层序数组让父子节点下标可以通过固定公式在
O(1)时间内计算。 - 所有下标公式都必须配合根节点和数组边界检查。
下一课预告
下一课将学习“最大堆与最小堆”,在完全二叉树的数组表示之上增加堆序约束,并分析堆顶访问、插入和删除的效率。
按自己的节奏,确认真正理解。