1. 从一道竞赛题看数组存二叉树的真实价值

很多人第一次看到"用数组存储二叉树"这个说法，脑子里冒出来的第一反应是：这不就是堆吗？堆排序、优先队列，课本上翻来覆去讲的那套。但如果你真的在比赛或者工程里遇到过需要动态维护树形结构、又不想写指针和结构体的场景，就会发现事情远没有这么简单。这道题出现在一场算法基础集训营里，定位是"模拟"，看起来平平无奇，实际上它考察的是你对完全二叉树数组表示法的理解深度，以及能不能把"数组下标与树节点位置"之间的映射关系玩明白。

我先说结论：数组存二叉树这件事，核心就一句话——用下标关系代替指针关系。根节点放在下标1（或者0），那么下标为 i 的节点，左孩子是 2i，右孩子是 2i+1，父节点是 i/2。这套规则在完全二叉树里完美成立，因为完全二叉树是"从上到下、从左到右"逐层填满的，中间没有空洞。但一旦树不是完全二叉树，数组里就会出现"空位"，这些空位需要用特殊值标记，否则你没法区分"这个位置没有节点"和"这个位置有节点但值为0"。

这道题的关键词是"模拟"，意味着它不要求你发明什么新算法，而是要求你严格按照题目描述的规则，一步一步地把操作模拟出来。这类题在竞赛里非常常见，看起来简单，但细节极多，稍不留神就会在边界条件上翻车。接下来我会从数组存二叉树的底层逻辑讲起，然后拆解这道题可能涉及的模拟操作，再分享一些我在实际做题和工程中踩过的坑，最后给出可复现的代码框架和调试技巧。

如果你正在准备算法竞赛，或者单纯想搞清楚"数组和树之间到底怎么对应"，这篇文章应该能帮你把这块知识彻底夯实。即使你之前没接触过完全二叉树，我也会用最直白的方式把原理讲清楚，保证你能跟着思路走下来。

2. 数组与二叉树的映射关系到底怎么建立

2.1 为什么偏偏选数组而不是指针

在讲具体映射之前，先回答一个更根本的问题：为什么要有"数组存二叉树"这种操作？直接用结构体加指针不是更直观吗？

原因有三个。第一，空间局部性好。数组在内存里是连续存放的，CPU 缓存命中率高，遍历的时候速度比指针跳转快得多。第二，不需要动态内存分配。指针版本每次插入节点都要 malloc 或者 new，开销大且容易产生内存碎片；数组版本提前开好空间，直接用下标访问，干净利落。第三，下标本身就是信息。在完全二叉树里，你不需要额外存储"我是谁的孩子"这种关系，下标一算就知道，省空间也省代码。

但代价也很明显：数组存二叉树只适合完全二叉树或者近似完全的树。如果树退化成一条链，比如每个节点只有右孩子，那么数组里会有大量空位，空间浪费极其严重。举个例子，一棵深度为 n 的右斜树，只有 n 个节点，但数组需要开到 2^n 的大小，指数级爆炸。所以竞赛里用数组存树，通常题目会明确告诉你"这是一棵完全二叉树"，或者操作本身保证了树的形态不会太离谱。

这道题既然定位是"模拟"，大概率是给定一棵完全二叉树，然后让你执行一系列操作，比如查询某个节点的左右孩子、修改某个节点的值、或者按照某种顺序输出节点。你需要做的就是把下标和树结构之间的对应关系牢牢记住，然后在每次操作时正确地计算出目标下标。

2.2 下标映射的三种常见约定

数组存二叉树的下标约定不止一种，不同题目、不同教材可能不一样，这是最容易搞混的地方。我整理了一个对照表，你做题的时候一定要先确认题目用的是哪一种。

1-based 是最符合直觉的，因为根节点是1，第一层是1，第二层是2和3，第三层是4、5、6、7，每一层的下标范围是 [2^(k-1), 2^k - 1]，非常规整。你在做题时如果看到题目说"根节点存储在数组下标1的位置"，那就果断用 1-based。

0-based 左偏也很常见，根节点在0，左孩子在1，右孩子在2，第三层是3、4、5、6。这种约定下，节点 i 的父节点是 (i-1)/2，左孩子是 2i+1，右孩子是 2i+2。很多编程语言的标准库（比如某些堆实现）用的是这种。

注意：如果你在比赛里搞混了这两种约定，代码可能在小数据上跑对，但一到大一点的数据就全错，而且错误非常隐蔽，因为树的结构看起来"差不多"。我的建议是，每道题开始写代码之前，先在草稿纸上画一棵深度为3的完全二叉树，把下标标上去，确认映射关系，再动手写。

2.3 空节点的处理：为什么不能简单用0表示

在完全二叉树里，理论上数组的每个位置都有节点，不存在空位。但实际题目中，树可能不是满的，最后一层可能只有部分节点。这时候数组末尾会有一些位置没有节点，你需要用特殊值标记。

很多人的第一反应是用0表示空节点。但如果题目里节点的值本身就可以是0呢？那就完蛋了，你没法区分"这个位置是空"和"这个位置的值是0"。所以更稳妥的做法是用一个题目中不会出现的值，比如 -1、INT_MIN、或者一个特殊字符串。

还有一种情况：题目给的树不是完全二叉树，中间有空洞。比如根节点有左孩子但没有右孩子，那么右孩子的那个下标位置就是空的。这种情况下，数组里会出现"中间空、后面还有节点"的情况。这时候你遍历数组时不能遇到空就停，必须遍历到数组的最大有效下标。

我在实际做题时总结了一个原则：先看题目保证什么。如果题目说"这是一棵完全二叉树"，那你可以放心用数组，末尾的空位用特殊值标记即可。如果题目说"这是一棵普通二叉树"，那数组存储可能不是最优选择，你需要考虑用其他方式（比如哈希表映射下标，或者干脆用指针）。这道题既然标题里写了"数组存储"，那大概率是完全二叉树或者近似完全二叉树。

3. 模拟类题目的通用拆解思路

3.1 先搞清楚"模拟"到底在模拟什么

"模拟"这个词在算法竞赛里出现的频率极高，但很多人对它的理解停留在"照着题目说的做"。这话没错，但太笼统了。我的经验是，模拟题的核心在于状态定义和状态转移。你需要先明确：题目里有哪些状态？每个操作会改变哪些状态？操作之间有没有依赖关系？

拿这道题来说，如果它是一道数组存二叉树的模拟题，可能的状态包括：数组本身的内容、当前有效节点的数量、某个指针的位置（比如当前遍历到哪个节点）。操作可能包括：插入一个节点、删除一个节点、查询某个节点的孩子、修改某个节点的值、按照某种顺序输出。

你需要做的是，把题目描述的每一个操作，翻译成对数组下标的操作。比如"查询节点 x 的左孩子"，翻译成代码就是"如果 2x 在有效范围内且不为空，则输出 arr[2x]，否则输出空"。看起来简单，但边界条件很多：x 本身可能不存在、2x 可能越界、2x 位置可能是空。

3.2 边界条件是模拟题的生命线

我做过统计，模拟题里超过70%的错误都出在边界条件上。具体到数组存二叉树，常见的边界问题有这几类：

第一类，下标越界。当你计算 2i 或 2i+1 时，结果可能超过数组的最大长度。这时候你必须先判断再访问，不能直接 arr[2*i]，否则会运行时错误。

第二类，空节点判断。即使下标在范围内，那个位置也可能是空的。你需要先检查 arr[2*i] 是否等于特殊值，再决定输出什么。

第三类，根节点的父节点。根节点下标是1（1-based），它的父节点按公式是 1/2 = 0，但下标0通常不用。你需要特判根节点没有父节点。

第四类，树的深度与数组长度的关系。如果题目给的树深度是 d，那么数组至少需要开到 2^d - 1。但有时候题目给的数组长度是固定的，你需要判断某个下标是否在有效范围内。

提示：写模拟题的时候，我习惯先把所有可能的边界情况列出来，然后针对每一种写一个测试用例。比如空树、只有一个根节点、只有左孩子、只有右孩子、满二叉树、最后一层只有一个节点，等等。这些用例能帮你覆盖绝大多数边界。

3.3 从题目描述到代码的翻译技巧

模拟题最大的难点不是算法，而是"把自然语言翻译成代码"。题目描述往往有一些隐含的规则，你需要仔细读题，把每一个细节都抠出来。

我的做法是，读题的时候拿一支笔，把所有的名词、动词、条件都圈出来。名词对应状态变量，动词对应操作，条件对应分支判断。然后画一个简单的状态转移图，看看操作之间有没有顺序依赖。

比如题目说"如果节点 x 存在，则输出它的左孩子；如果左孩子不存在，则输出 -1"。这句话翻译成代码就是：

if x is valid: left = 2 * x if left <= n and arr[left] != EMPTY: print(arr[left]) else: print(-1) else: print(-1)

你看，一句话拆出来四五个分支。如果你读题的时候漏了"如果节点 x 存在"这个前提，代码就会在 x 不存在的时候出错。

4. 数组存二叉树的实操细节与代码框架

4.1 建树：从输入到数组的映射

假设题目给你一棵完全二叉树的层序遍历结果，让你存到数组里。层序遍历的顺序就是从上到下、从左到右，正好对应数组的下标顺序。所以你可以直接按顺序读入，存到 arr[1] 到 arr[n]。

但如果题目给的是其他形式的输入呢？比如给你每个节点的左右孩子信息，让你构建数组。这时候你需要先确定根节点是谁（通常是入度为0的那个），然后从根开始，用 BFS 或者递归的方式，把每个节点放到正确的下标位置。

我写过一个通用的建树函数，思路是这样的：先找到根节点，把它放在下标1。然后用一个队列，每次取出一个节点，如果它有左孩子，就放到 2i；如果有右孩子，就放到 2i+1。这样一层一层下去，就能把整棵树映射到数组里。

def build_tree(n, left_child, right_child, root): arr = [EMPTY] * (4 * n) queue = [(root, 1)] while queue: node, idx = queue.pop(0) arr[idx] = node if left_child[node] != -1: queue.append((left_child[node], 2 * idx)) if right_child[node] != -1: queue.append((right_child[node], 2 * idx + 1)) return arr

这里数组开了 4*n 的大小，是一个经验值。因为完全二叉树的数组表示，最坏情况下下标可能达到 2n 左右，开 4n 足够安全。如果你不确定，可以动态扩展，但竞赛里一般直接开大一点省事。

4.2 查询与修改：下标计算的核心逻辑

查询和修改是模拟题里最常见的操作。查询某个节点的左孩子，核心就是计算 2*i，然后判断是否有效。修改某个节点的值，直接 arr[i] = new_value。

但这里有一个容易忽略的点：修改操作可能会影响后续查询的有效性。比如你把某个节点删除了（设为空），那么它的孩子们也应该被视为无效。但数组里它们的值还在，你需要额外维护一个"有效"标记，或者在查询时递归判断父节点是否有效。

我在一次比赛中就踩过这个坑。题目要求删除一个节点，我直接把 arr[i] 设为空，但后面查询它的孩子时，孩子还在数组里，导致输出错误。正确的做法是，删除节点时，把它的整个子树都标记为空，或者维护一个父节点有效性检查。

def delete_node(arr, i): if i >= len(arr) or arr[i] == EMPTY: return arr[i] = EMPTY delete_node(arr, 2 * i) delete_node(arr, 2 * i + 1)

这个递归删除看起来简单，但如果树很深，递归层数可能很大。竞赛里一般树不会太深，但工程里要注意栈溢出。

4.3 遍历：层序、前序、中序、后序的数组实现

数组存二叉树的一个好处是，遍历非常方便。层序遍历就是直接遍历数组，跳过空位。前序、中序、后序可以用递归，也可以用栈模拟。

前序遍历的数组实现：

def preorder(arr, i): if i >= len(arr) or arr[i] == EMPTY: return print(arr[i]) preorder(arr, 2 * i) preorder(arr, 2 * i + 1)

中序和后序只是把 print 的位置换一下。你看，不需要指针，不需要结构体，代码非常简洁。

但这里有一个细节：数组的长度决定了递归的终止条件。如果数组开得太大，递归会访问很多空位，效率低。所以实际写的时候，最好维护一个 max_index，表示当前有效节点的最大下标，递归时只访问到 max_index。

5. 那些年我在数组存树上踩过的坑

5.1 下标从0还是从1开始：一个字母引发的血案

我刚学数组存二叉树的时候，最大的困惑就是下标到底从0还是从1开始。课本上有的用0，有的用1，网上的代码也是五花八门。有一次比赛，我按照0-based 写了代码，结果题目默认是1-based，样例过了，但提交后全WA。我调了半个小时，最后发现是根节点的下标搞错了。

从那以后，我养成了一个习惯：每道题开始写代码之前，先在注释里写清楚下标约定。比如：

# 下标约定：1-based，根节点在 arr[1] # 左孩子：2*i，右孩子：2*i+1，父节点：i//2

这样即使写到后面忘了，看一眼注释就能想起来。而且如果队友来看你的代码，也能立刻明白。

5.2 数组开多大才够：2n 还是 4n

数组开多大，是另一个容易翻车的地方。理论上，一棵有 n 个节点的完全二叉树，数组的最大下标不会超过 2n。但这是理论值，实际题目里可能会有一些边界情况，比如 n=1 的时候，2n=2，但你需要访问 arr[1]，所以至少开到2。如果 n 稍微大一点，2n 可能刚好不够。

我的经验是，直接开 4*n + 5。这个大小在绝大多数情况下都够用，而且浪费的空间可以忽略不计。如果你实在不放心，可以开 1 << (depth + 1)，其中 depth 是树的深度。但计算深度本身也需要遍历，不如直接开 4n 省事。

注意：有些题目会明确告诉你数组的最大长度，比如"数组长度不超过1000"，那你就按题目给的来。但如果题目没说，开 4n 是最稳妥的。

5.3 空节点的值：0、-1还是null

空节点用什么值表示，看起来是个小问题，但实际上很容易出bug。如果题目里节点的值范围是 [0, 10^9]，那你用0表示空节点就会冲突。如果节点的值可以是负数，那你用-1也会冲突。

我的做法是，先看题目里节点的值范围，然后选一个绝对不可能出现的值。比如值范围是 [1, 1000]，那我就用0表示空。如果值范围是 [-1000, 1000]，那我就用 INT_MIN 或者一个很大的负数。如果值范围没有限制，那我就用一个特殊对象，比如 Python 里的 None。

EMPTY = None # 最安全，但比较时要注意 # 或者 EMPTY = -10**18 # 如果值范围有限

用 None 的好处是不会和任何整数冲突，坏处是每次比较都要用is None而不是== None，而且不能直接参与算术运算。用特殊整数则相反。我一般根据题目灵活选择。

6. 从竞赛题到工程：数组存二叉树的实际应用

6.1 堆：数组存二叉树最成功的案例

说到数组存二叉树，最成功的应用就是堆。堆是一棵完全二叉树，用数组存储，父节点和子节点之间满足大小关系。堆排序、优先队列、Dijkstra 算法里的优先队列，底层都是数组存二叉树。

堆的核心操作是上浮和下沉，都是基于下标计算的。上浮的时候，不断和父节点比较，如果比父节点大（或小），就交换；下沉的时候，不断和孩子中较大（或较小）的那个比较，如果比孩子小（或大），就交换。整个过程不需要指针，只需要下标运算，非常高效。

def heapify_up(arr, i): while i > 1 and arr[i] > arr[i // 2]: arr[i], arr[i // 2] = arr[i // 2], arr[i] i //= 2 def heapify_down(arr, i, n): while 2 * i <= n: child = 2 * i if child + 1 <= n and arr[child + 1] > arr[child]: child += 1 if arr[i] >= arr[child]: break arr[i], arr[child] = arr[child], arr[i] i = child

你看，这些代码里没有任何指针，全是下标运算。这就是数组存二叉树的威力。

6.2 线段树：数组存二叉树的另一个经典场景

线段树是另一种用数组存储的二叉树。它把区间划分成一个个节点，每个节点存储一个区间的信息。线段树通常是一棵完全二叉树，所以可以用数组存储，根节点在1，左孩子在2i，右孩子在2i+1。

线段树的数组大小通常是 4n，因为它的形态虽然接近完全二叉树，但可能会有一些空位。建树、查询、更新都是递归进行的，递归的时候传入当前节点的下标和它对应的区间范围。

def build(arr, tree, node, start, end): if start == end: tree[node] = arr[start] else: mid = (start + end) // 2 build(arr, tree, 2 * node, start, mid) build(arr, tree, 2 * node + 1, mid + 1, end) tree[node] = tree[2 * node] + tree[2 * node + 1]

这段代码是线段树建树的标准写法，node 是当前节点在数组中的下标，start 和 end 是它对应的区间。你看，数组存二叉树的思想在这里体现得淋漓尽致。

6.3 什么时候不该用数组存二叉树

虽然数组存二叉树有很多好处，但也不是万能的。以下几种情况，我建议你用指针或者邻接表：

第一种，树不是完全二叉树，且节点数量很大。比如一棵有10万个节点的普通二叉树，如果形态很偏，数组可能需要开到几百万甚至更大，空间浪费严重。

第二种，需要频繁插入和删除节点。数组的插入和删除需要移动元素，时间复杂度是 O(n)，而指针版本只需要 O(1)。

第三种，树的形态动态变化，且无法保证完全二叉树的性质。比如平衡树的各种旋转操作，用数组实现会非常复杂。

所以，选择数组还是指针，取决于具体的应用场景。竞赛里如果题目明确说"完全二叉树"，那就放心用数组；如果题目说"普通二叉树"，那就要慎重考虑。

7. 调试与验证：怎么确认你的数组树是对的

7.1 手动画图：最笨但最有效的方法

调试数组存二叉树的问题，最有效的方法就是手动画图。拿一张纸，画一棵深度为3或4的完全二叉树，把每个节点的下标标上去。然后对照你的代码，看看每次操作后数组的变化是否符合预期。

我一般会画两棵树：一棵是题目给的输入树，一棵是我代码里数组对应的树。然后逐步执行代码，每执行一步，就在两棵树上标记变化。如果发现不一致，就说明代码有问题。

这个方法看起来很笨，但非常有效。尤其是对于模拟题，很多bug都是因为对题目的理解有偏差，画图能帮你快速发现这种偏差。

7.2 写一个打印函数：把数组还原成树

另一个实用的技巧是写一个打印函数，把数组还原成树形结构输出。这样你可以直观地看到数组里存的是什么，而不是盯着一堆数字发呆。

def print_tree(arr, n): depth = 0 while (1 << depth) - 1 < n: depth += 1 for d in range(depth): start = 1 << d end = min(1 << (d + 1), n + 1) line = [] for i in range(start, end): if i < len(arr) and arr[i] != EMPTY: line.append(str(arr[i])) else: line.append(".") print(" " * (depth - d - 1) + " ".join(line))

这个函数会按照树的形状打印数组，空节点用点表示。你一眼就能看出树的结构对不对。

7.3 对拍：用暴力程序验证你的代码

如果你在比赛里，时间允许的话，可以写一个暴力程序，用指针或者递归的方式实现同样的功能，然后和你的数组版本对拍。随机生成小数据，比较两个程序的输出。如果输出一致，说明你的数组版本大概率是对的。

对拍是竞赛里最可靠的调试方法之一。我很多次都是在对拍的时候发现了边界条件的bug，比如空树、单节点、满二叉树等情况。

8. 一些提高效率的编码习惯

8.1 把下标计算封装成函数

数组存二叉树里，下标计算到处都是：2i、2i+1、i//2。如果每次都手写，容易写错，而且代码可读性差。我习惯把它们封装成函数：

def left(i): return 2 * i def right(i): return 2 * i + 1 def parent(i): return i // 2 def is_valid(i, n): return 1 <= i <= n

这样代码看起来清晰多了，而且如果下标约定变了，只需要改这几个函数。

8.2 用常量表示空节点

前面说过，空节点的值要选一个不会冲突的。我习惯在代码开头定义一个常量：

EMPTY = -1 # 或者 None，根据题目定

然后在所有需要判断空的地方都用这个常量，不要直接写 -1 或 0。这样如果以后要改，只需要改一个地方。

8.3 提前处理边界情况

模拟题里，边界情况往往是最容易出错的。我习惯在代码开头先把边界情况处理掉，比如：

if n == 0: print("空树") return if n == 1: print(arr[1]) return

这样后面的代码就可以假设树至少有两个节点，减少分支判断。

9. 从这道题延伸出去的学习路径

如果你把这道题搞定了，说明你对数组存二叉树的基本操作已经没问题了。接下来可以往这几个方向深入：

第一个方向，线段树和树状数组。这两个数据结构都是数组存二叉树的经典应用，线段树适合区间查询和区间更新，树状数组适合前缀和查询和单点更新。它们的下标计算和这道题一脉相承，但操作更复杂。

第二个方向，堆的高级应用。比如可并堆、左偏树、斜堆，这些数据结构虽然形态不是完全二叉树，但很多实现也用数组存储。理解数组存二叉树的原理，能帮你更快上手这些高级数据结构。

第三个方向，树的序列化与反序列化。把一棵树存成数组，本质上就是一种序列化。反过来，从数组还原成树，就是反序列化。这个技能在工程里非常有用，比如把树形结构存到数据库或者通过网络传输。

第四个方向，完全二叉树的数学性质。完全二叉树有很多优美的数学性质，比如节点数 n 和深度 d 的关系是 d = floor(log2(n)) + 1，叶子节点的数量是 ceil(n/2)，等等。这些性质在解题时经常能帮你简化问题。

我在实际工作中，遇到需要处理层级关系的场景，比如组织架构、文件目录、评论回复，都会优先考虑用数组存二叉树的思想。虽然这些场景里的树不一定是完全二叉树，但数组存储的思路——用下标关系代替指针关系——是通用的。你可以用哈希表把节点 ID 映射到数组下标，然后用类似的方式计算父子关系。这样既保留了数组的高效，又不受完全二叉树的限制。

最后分享一个我常用的调试技巧：当你觉得代码逻辑没问题但结果不对时，把数组的每一步变化都打印出来，然后和手算的结果逐步对比。十有八九，你会在某一步发现一个下标计算错误或者一个边界判断遗漏。数组存二叉树的题目，细节决定成败，耐心和细心比聪明更重要。