1. 从一道竞赛题看数组存二叉树的真实价值很多人第一次看到用数组存储二叉树这个说法脑子里冒出来的第一反应是这不就是堆吗堆排序、优先队列课本上翻来覆去讲的那套。但如果你真的在比赛或者工程里遇到过需要动态维护树形结构、又不想写指针和结构体的场景就会发现事情远没有这么简单。这道题出现在一场算法基础集训营里定位是模拟看起来平平无奇实际上它考察的是你对完全二叉树数组表示法的理解深度以及能不能把数组下标与树节点位置之间的映射关系玩明白。我先说结论数组存二叉树这件事核心就一句话——用下标关系代替指针关系。根节点放在下标1或者0那么下标为 i 的节点左孩子是 2i右孩子是 2i1父节点是 i/2。这套规则在完全二叉树里完美成立因为完全二叉树是从上到下、从左到右逐层填满的中间没有空洞。但一旦树不是完全二叉树数组里就会出现空位这些空位需要用特殊值标记否则你没法区分这个位置没有节点和这个位置有节点但值为0。这道题的关键词是模拟意味着它不要求你发明什么新算法而是要求你严格按照题目描述的规则一步一步地把操作模拟出来。这类题在竞赛里非常常见看起来简单但细节极多稍不留神就会在边界条件上翻车。接下来我会从数组存二叉树的底层逻辑讲起然后拆解这道题可能涉及的模拟操作再分享一些我在实际做题和工程中踩过的坑最后给出可复现的代码框架和调试技巧。如果你正在准备算法竞赛或者单纯想搞清楚数组和树之间到底怎么对应这篇文章应该能帮你把这块知识彻底夯实。即使你之前没接触过完全二叉树我也会用最直白的方式把原理讲清楚保证你能跟着思路走下来。2. 数组与二叉树的映射关系到底怎么建立2.1 为什么偏偏选数组而不是指针在讲具体映射之前先回答一个更根本的问题为什么要有数组存二叉树这种操作直接用结构体加指针不是更直观吗原因有三个。第一空间局部性好。数组在内存里是连续存放的CPU 缓存命中率高遍历的时候速度比指针跳转快得多。第二不需要动态内存分配。指针版本每次插入节点都要 malloc 或者 new开销大且容易产生内存碎片数组版本提前开好空间直接用下标访问干净利落。第三下标本身就是信息。在完全二叉树里你不需要额外存储我是谁的孩子这种关系下标一算就知道省空间也省代码。但代价也很明显数组存二叉树只适合完全二叉树或者近似完全的树。如果树退化成一条链比如每个节点只有右孩子那么数组里会有大量空位空间浪费极其严重。举个例子一棵深度为 n 的右斜树只有 n 个节点但数组需要开到 2^n 的大小指数级爆炸。所以竞赛里用数组存树通常题目会明确告诉你这是一棵完全二叉树或者操作本身保证了树的形态不会太离谱。这道题既然定位是模拟大概率是给定一棵完全二叉树然后让你执行一系列操作比如查询某个节点的左右孩子、修改某个节点的值、或者按照某种顺序输出节点。你需要做的就是把下标和树结构之间的对应关系牢牢记住然后在每次操作时正确地计算出目标下标。2.2 下标映射的三种常见约定数组存二叉树的下标约定不止一种不同题目、不同教材可能不一样这是最容易搞混的地方。我整理了一个对照表你做题的时候一定要先确认题目用的是哪一种。约定方式根节点下标左孩子右孩子父节点适用场景1-based12i2i1i/2竞赛最常见堆排序标准0-based 左偏02i12i2(i-1)/2部分工程代码0-based 右偏02i2i1i/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左孩子是 2i1右孩子是 2i2。很多编程语言的标准库比如某些堆实现用的是这种。注意如果你在比赛里搞混了这两种约定代码可能在小数据上跑对但一到大一点的数据就全错而且错误非常隐蔽因为树的结构看起来差不多。我的建议是每道题开始写代码之前先在草稿纸上画一棵深度为3的完全二叉树把下标标上去确认映射关系再动手写。2.3 空节点的处理为什么不能简单用0表示在完全二叉树里理论上数组的每个位置都有节点不存在空位。但实际题目中树可能不是满的最后一层可能只有部分节点。这时候数组末尾会有一些位置没有节点你需要用特殊值标记。很多人的第一反应是用0表示空节点。但如果题目里节点的值本身就可以是0呢那就完蛋了你没法区分这个位置是空和这个位置的值是0。所以更稳妥的做法是用一个题目中不会出现的值比如 -1、INT_MIN、或者一个特殊字符串。还有一种情况题目给的树不是完全二叉树中间有空洞。比如根节点有左孩子但没有右孩子那么右孩子的那个下标位置就是空的。这种情况下数组里会出现中间空、后面还有节点的情况。这时候你遍历数组时不能遇到空就停必须遍历到数组的最大有效下标。我在实际做题时总结了一个原则先看题目保证什么。如果题目说这是一棵完全二叉树那你可以放心用数组末尾的空位用特殊值标记即可。如果题目说这是一棵普通二叉树那数组存储可能不是最优选择你需要考虑用其他方式比如哈希表映射下标或者干脆用指针。这道题既然标题里写了数组存储那大概率是完全二叉树或者近似完全二叉树。3. 模拟类题目的通用拆解思路3.1 先搞清楚模拟到底在模拟什么模拟这个词在算法竞赛里出现的频率极高但很多人对它的理解停留在照着题目说的做。这话没错但太笼统了。我的经验是模拟题的核心在于状态定义和状态转移。你需要先明确题目里有哪些状态每个操作会改变哪些状态操作之间有没有依赖关系拿这道题来说如果它是一道数组存二叉树的模拟题可能的状态包括数组本身的内容、当前有效节点的数量、某个指针的位置比如当前遍历到哪个节点。操作可能包括插入一个节点、删除一个节点、查询某个节点的孩子、修改某个节点的值、按照某种顺序输出。你需要做的是把题目描述的每一个操作翻译成对数组下标的操作。比如查询节点 x 的左孩子翻译成代码就是如果 2x 在有效范围内且不为空则输出 arr[2x]否则输出空。看起来简单但边界条件很多x 本身可能不存在、2x 可能越界、2x 位置可能是空。3.2 边界条件是模拟题的生命线我做过统计模拟题里超过70%的错误都出在边界条件上。具体到数组存二叉树常见的边界问题有这几类第一类下标越界。当你计算 2i 或 2i1 时结果可能超过数组的最大长度。这时候你必须先判断再访问不能直接 arr[2*i]否则会运行时错误。第二类空节点判断。即使下标在范围内那个位置也可能是空的。你需要先检查 arr[2*i] 是否等于特殊值再决定输出什么。第三类根节点的父节点。根节点下标是11-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如果有右孩子就放到 2i1。这样一层一层下去就能把整棵树映射到数组里。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*i1父节点i//2这样即使写到后面忘了看一眼注释就能想起来。而且如果队友来看你的代码也能立刻明白。5.2 数组开多大才够2n 还是 4n数组开多大是另一个容易翻车的地方。理论上一棵有 n 个节点的完全二叉树数组的最大下标不会超过 2n。但这是理论值实际题目里可能会有一些边界情况比如 n1 的时候2n2但你需要访问 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右孩子在2i1。线段树的数组大小通常是 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、2i1、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 映射到数组下标然后用类似的方式计算父子关系。这样既保留了数组的高效又不受完全二叉树的限制。最后分享一个我常用的调试技巧当你觉得代码逻辑没问题但结果不对时把数组的每一步变化都打印出来然后和手算的结果逐步对比。十有八九你会在某一步发现一个下标计算错误或者一个边界判断遗漏。数组存二叉树的题目细节决定成败耐心和细心比聪明更重要。
