数据结构与算法 / 系统课时

完全二叉树与数组表示

完全二叉树与数组表示

完全二叉树把树形层级紧凑地映射到连续数组中,因此无需保存父子指针,也能在常数时间定位亲属节点。本课将建立结构判定、下标公式与代码验证之间的对应关系。

学习目标

  • 识别完全二叉树与满二叉树、普通二叉树的区别。
  • 掌握从数组下标计算父节点、左孩子和右孩子的方法。
  • 能在代码中正确处理根节点、叶节点和越界边界。

核心原理

完全二叉树要求除最后一层外的每一层都被填满,最后一层的节点必须从左向右连续出现。它不要求所有叶节点处于同一层,因此完全二叉树不一定是满二叉树。

完全二叉树与数组下标映射

采用从 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)。

判断结构时还要注意“从左向右连续”这一条件。若最后一层先出现空位,后面又出现节点,即使其他层完整,也不是完全二叉树。

本课练习

  1. 对数组 ["A", "B", "C", "D", "E", "F", "G", "H"],计算下标 3 的父节点和两个孩子下标,并判断哪些孩子真实存在。
  2. 编写函数 is_complete_layout(items),其中 None 表示空位;一旦发现空位,后续不能再出现非空节点。使用至少三个测试用例验证结果。

本课总结

  • 完全二叉树的最后一层必须从左向右连续填充。
  • 层序数组让父子节点下标可以通过固定公式在 O(1) 时间内计算。
  • 所有下标公式都必须配合根节点和数组边界检查。

下一课预告

下一课将学习“最大堆与最小堆”,在完全二叉树的数组表示之上增加堆序约束,并分析堆顶访问、插入和删除的效率。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

完全二叉树与数组表示

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通