Hello 算法：二叉树的数组表示——索引映射公式、空位编码约定与遍历实现

二叉树最常见的实现是链表表示：每个存储单元为节点 TreeNode，节点之间通过指针相连。但在《Hello 算法》的树章节中，二叉树还有第二种存储方式——数组表示。本文基于仓库文档 array_representation_of_tree.md 展开，讲清三件事：数组表示的索引映射公式如何推导、任意二叉树为何必须在层序序列中显式写出空位（None）、以及 ArrayBinaryTree 类如何在源码中实现节点访问与四种遍历。读完本文，你可以直接使用 codes/python/chapter_tree/array_binary_tree.py 这样的实现，理解堆、优先队列等“基于数组的树结构”的底层索引逻辑。

从链表表示到数组表示

在链表表示下，父节点与子节点之间靠指针“连线”，访问子节点就是解引用指针。那么能否干脆去掉指针，把所有节点按一定顺序排进一个数组？

答案是肯定的，而且这正是很多经典数据结构（如完全二叉堆）的存储基础。核心思想只有一句话：把层序遍历的序列直接存进数组，用下标算术代替指针跳转。

完美二叉树：索引映射公式的推导

先看最简单的场景——完美二叉树（每个节点都有左右两个子节点，所有层都是满的）。将所有节点按层序遍历顺序存入数组后，每个节点都对应唯一的数组索引。

根据层序遍历的特性，可以推导出父节点索引与子节点索引之间的映射公式：

若某节点的索引为 i，则其左子节点索引为 2i + 1，右子节点索引为 2i + 2。

反过来，子节点索引为 i 时，父节点索引为 (i - 1) // 2（整除）。

映射公式的角色相当于链表中的节点引用（指针）：给定数组中的任意一个节点，都可以通过公式直接访问它的左（右）子节点和父节点，时间复杂度为 O(1)，且不需要存储任何指针字段。

任意二叉树：必须在序列中显式写出空位

完美二叉树只是特例。真实场景中，二叉树的中间层通常存在许多空位（None）。问题在于：

• 标准的层序遍历序列不包含这些 None；
• 仅凭该序列，无法推测 None 的数量和分布位置；
• 这意味着存在多种不同的二叉树结构都符合同一条层序序列。

解决办法是：在层序遍历序列中显式地写出所有 None。处理之后，数组序列与二叉树结构之间就是一一对应的关系了。文档中给出的示例数组为：

# 二叉树的数组表示
# 使用 None 来表示空位
tree = [1, 2, 3, 4, None, 6, 7, 8, 9, None, None, 12, None, None, 15]

不同语言标记空位的方式不同，仓库文档给出了各语言的等价写法，核心都是“让数组元素可以取空值”：

语言	空位标记方式	示例
Python	None	[1, 2, 3, 4, None, 6, ...]
Java	包装类 Integer 的 null	Integer[] tree = {1, 2, 3, 4, null, 6, ...}
C#	可空类型 int?	int?[] tree = [1, 2, 3, 4, null, 6, ...]
Go	any 切片的 nil	tree := []any{1, 2, 3, 4, nil, 6, ...}
Swift	可空类型 Int?	let tree: [Int?] = [1, 2, 3, 4, nil, 6, ...]
JS / TS	null（TS 标注 number | null）	let tree = [1, 2, 3, 4, null, 6, ...]
Dart	可空类型 int?	List<int?> tree = [1, 2, 3, 4, null, 6, ...]
Rust	Option<i32> 的 None	[Some(1), Some(2), ..., None, ...]
Kotlin	null	arrayOf(1, 2, 3, 4, null, 6, ...)
Ruby	nil	[1, 2, 3, 4, nil, 6, ...]
C / C++	哨兵值 INT_MAX（要求节点值不能取该值）	{1, 2, 3, 4, INT_MAX, 6, ...}

值得注意的是 C 与 C++ 没有原生空值，仓库选择了 INT_MAX 作为哨兵——这是一种典型的“魔数标记”取舍，代价是节点取值域被排除了一个值。

完全二叉树的特殊待遇

文档特别指出：完全二叉树非常适合用数组表示。由完全二叉树的定义（None 只出现在最底层且靠右的位置）可知，所有 None 一定出现在层序序列的末尾。因此用数组表示完全二叉树时，可以直接省略末尾的 None，序列长度恰好等于节点数，不浪费任何空间。这也是二叉堆（Heap）能用普通数组高效实现的原因。

源码实现：ArrayBinaryTree 的节点访问与遍历

以下实现（各语言版本结构一致，Python 版见 array_binary_tree.py，C 版见 array_binary_tree.c，Java 版见 array_binary_tree.java）封装了一棵基于数组表示的二叉树，包含两类操作：

• 给定某节点，获取它的值、左（右）子节点、父节点；
• 获取前序遍历、中序遍历、后序遍历、层序遍历序列。

核心方法：下标算术即指针

以 Python 版为例，节点访问就是三行公式（array_binary_tree.py）：

def val(self, i):
    """获取索引为 i 节点的值"""
    # 若索引越界，则返回 None ，代表空位
    if i < 0 or i >= self.size():
        return None
    return self._tree[i]

def left(self, i):
    """获取索引为 i 节点的左子节点的索引"""
    return 2 * i + 1

def right(self, i):
    """获取索引为 i 节点的右子节点的索引"""
    return 2 * i + 2

def parent(self, i):
    """获取索引为 i 节点的父节点的索引"""
    return (i - 1) // 2

两个细节值得注意：

1. 越界即空位：val(i) 对越界索引返回 None，而不是抛异常。这使递归遍历代码无需额外判断数组长度——子节点索引落在数组之外时，自然被当作空位剪枝。
2. 整数除法的语义一致性：(i - 1) // 2 在 Python 中是向下取整，在 C/Java 中对非负整数同样是截断除法（C 版对应 (i - 1) / 2，array_binary_tree.c），各语言行为一致；C 版则以 INT_MAX 作为越界/空位的统一返回值。

层序遍历：对数组表示是 O(n) 的线性扫描

链表表示下，层序遍历需要借助队列逐层出队入队；而在数组表示下，数组本身就是层序序列，遍历只需一次线性扫描并跳过空位（array_binary_tree.py）：

def level_order(self):
    """层序遍历"""
    self.res = []
    # 直接遍历数组
    for i in range(self.size()):
        if self.val(i) is not None:
            self.res.append(self.val(i))
    return self.res

这是数组表示的直观收益之一：层序序列就是数组的“投影”，零额外数据结构。

深度优先遍历：递归套用映射公式

前序/中序/后序遍历共用同一个 dfs 函数，通过参数 order 控制“访问时机”（array_binary_tree.py）：

def dfs(self, i, order):
    """深度优先遍历"""
    if self.val(i) is None:
        return
    # 前序遍历
    if order == "pre":
        self.res.append(self.val(i))
    self.dfs(self.left(i), order)
    # 中序遍历
    if order == "in":
        self.res.append(self.val(i))
    self.dfs(self.right(i), order)
    # 后序遍历
    if order == "post":
        self.res.append(self.val(i))

从源码结构看，它与链表版 binary_tree_dfs 的结构完全同构，唯一区别是“走到子节点”这一步从 node.left 换成了 self.left(i) 的下标计算。空位剪枝由 val(i) is None 完成，越界情况已被 val 的越界返回统一兜住。

数组表示与链表表示的双向转换

文档示例中的数组 [1, 2, 3, 4, None, 6, 7, 8, 9, None, None, 12, None, None, 15] 对应的树结构为：

              /——— 15
        /——— 7
    /——— 3
   |    \——— 6
   |        \——— 12
——— 1
    \——— 2
       |    /——— 9
        \——— 4
            \——— 8

仓库的公共模块 tree_node.py 提供了两种表示之间的互转函数，其实现正是映射公式的直接应用：

def list_to_tree_dfs(arr, i):
    """将列表反序列化为二叉树：递归"""
    # 如果索引超出数组长度，或者对应的元素为 None ，则返回 None
    if i < 0 or i >= len(arr) or arr[i] is None:
        return None
    # 构建当前节点
    root = TreeNode(arr[i])
    # 递归构建左右子树
    root.left = list_to_tree_dfs(arr, 2 * i + 1)
    root.right = list_to_tree_dfs(arr, 2 * i + 2)
    return root

反向的 tree_to_list_dfs 则从根节点索引 0 出发，把每个节点写回 res[2i+1]、res[2i+2]，中间缺失的下标自动补 None。这两个函数也解释了为何各语言的 TreeNode 工具类普遍内置 listToTree / treeToList（如 Java 版 array_binary_tree.java 的 main 函数先调用 TreeNode.listToTree(arr) 打印链表表示，再构造 ArrayBinaryTree 演示数组操作）——它们都以同一套索引约定为契约，这也与 tree_node.py 中注明“序列化编码规则”的注释相互印证。

此外，该序列约定并非 Hello 算法自创，而是业界通用的层序序列化格式（LeetCode 的树输入格式即如此），因此仓库中的示例数组可以直接用于各种在线评测平台的题目输入。

优点与局限性

综合文档结论与源码实现，数组表示的优缺点可以归纳如下。

优点

• 缓存友好：数组存储在连续的内存空间中，访问与遍历速度较快；
• 节省指针空间：不需要存储指针字段，节点间关系完全由下标隐式表达；
• 支持随机访问：任意索引 O(1) 直达，链表表示下则只能从根出发逐跳。

局限性

• 要求连续内存：数组存储需要连续内存空间，不适合存储数据量过大的树；
• 增删效率低：增删节点需通过数组插入与删除操作实现，涉及大量元素搬移；
• 空间利用率低：当二叉树中存在大量 None（如深度不平衡的“左旋链”）时，数组中真实节点占比可能极低，最坏情况下退化为 O(2^h) 的空间占用。

由此可以推断仓库的实践取向：数组表示用于结构相对规整、以查询遍历为主的场景（完全二叉树、堆、序列化存储）；而频繁增删、形态不规则的树（如二叉搜索树、AVL 树，见 binary_search_tree.py、avl_tree.py）仍采用链表表示。

小结

• 数组表示的核心是层序序列 + 索引映射公式：左子 2i+1、右子 2i+2、父节点 (i-1)//2，公式即指针；
• 任意二叉树必须显式写出空位（None/null/INT_MAX 等），序列才能唯一还原树结构；完全二叉树可以省略末尾空位，这也是二叉堆采用数组实现的根本原因；
• 层序遍历在数组表示下降级为一次线性扫描；前中后序遍历与链表版实现同构，只是用下标计算替代指针跳转；
• 各语言的完整实现可在 codes/python/chapter_tree/array_binary_tree.py、codes/c/chapter_tree/array_binary_tree.c、codes/java/chapter_tree/array_binary_tree.java、codes/go/chapter_tree/array_binary_tree.go 等对应语言目录中对照阅读，codes/ 目录下其余 C#、JS、TS、Rust、Kotlin、Ruby、Dart、Swift 版本亦遵循同一套接口（size / val / left / right / parent / 四种遍历）。