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

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

【免费下载链接】hello-algo《Hello 算法》：动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語，提供 Python, Java, C++, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo

二叉树最常见的实现是链表表示：每个存储单元为节点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]

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

值得注意的是 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/ 四种遍历）。

【免费下载链接】hello-algo《Hello 算法》：动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語，提供 Python, Java, C++, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo