树系列第 4 篇：树的存储方式——链式、数组与父子表示

欢迎来到“树系列”第 4 篇。前面 3 篇，我们一直在研究树“长什么样”：第 1 篇从数组和链表出发，理解了为什么需要层次结构；第 2 篇把节点、边、根、叶子、深度、高度这些术语一个个捡了回来；第 3 篇把孩子的数量限制成最多两个，认识了计算机世界里最受宠的二叉树，还区分了满二叉树与完全二叉树。今天这篇要换一个视角：树在内存里，到底是怎么“放”的？ 你写的每一行代码、创建的每一个对象，最终都会被翻译成一串 0 和 1，放在内存的某个角落。一棵“有层次”的树，怎么才能住进一条“没有层次”的内存街道里？这就是本篇要解决的核心问题。

读完这一篇，你会得到三样东西：第一，四种主流存储方案的具体长相——链式存储、顺序存储、双亲表示法、孩子兄弟表示法，每一种我都会配上示意图和代码；第二，一张“什么时候该用谁”的对比表，让你以后做选择题时不再靠猜；第三，一个很关键的认知：存储方案没有绝对的好坏，只有代价的取舍。树的每一个操作——找孩子、找爸爸、找兄弟、遍历——在不同存储方案下付出的代价完全不同。你选哪种存储，本质上是在回答一个问题：你最常做的操作是什么？

0 先把前三篇的结论捡回来

树（tree）由节点（node）和连接节点的边（edge）组成。它有一个特殊的起点叫根节点（root），根是唯一没有父亲（parent）的节点；从根出发沿着边一层一层往下走，每个节点可以有若干个孩子（child），有同一个父亲的节点互为兄弟（sibling），没有孩子的节点叫叶子节点（leaf）。把某个节点和它所有的后代一起“剪”下来，仍然是一棵树，这叫子树（subtree）。这些术语来自第 1、2 篇，本篇会反复用到，请先在心里搭好这栋“术语大楼”。

第 3 篇的主角是二叉树（binary tree）：每个节点的度最多是 2。度是什么？就是一个节点拥有的孩子数量。二叉树还有一个非常漂亮的递归定义：一棵二叉树要么是空树，要么由一个根节点加上一棵左子树和一棵右子树组成，左、右子树本身仍然是二叉树。注意，这里的“左”和“右”不只是名字，它们是真实存在的两个位置：哪怕一个节点只有右孩子没有左孩子，这个“左”的位置也是存在的，只是空着而已。这一点现在听起来像是废话，等我们讲到数组存储时，你会发现它决定了一个惊人的空间浪费问题。

第 3 篇还介绍了两种特殊的二叉树。满二叉树（full/perfect binary tree）：每一层的节点都塞得满满当当，没有任何空缺；一个高度为 h 的满二叉树，第 k 层有 2 的 k 次方减 1 个节点（如果从第 1 层开始数），总共正好有 2 的 h 次方减 1 个节点。完全二叉树（complete binary tree）：最后一层可以不满，但必须严格地从左到右连续排列，中间不许出现“空一个再补一个”的情况。换句话说，如果你把一棵完全二叉树的节点按层从上到下、每层从左到右编号，编号必须是连续的 1、2、3、4……一直编到最后一个节点，中间不能跳号。满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。

为什么完全二叉树这么重要？因为编号连续意味着“第几个”这件事非常有规律。第 3 篇里我们提到过：n 个节点的完全二叉树，如果按“从根到最深叶子的边数”来算高度，大约是 log 以 2 为底的 n 再向下取整；如果按“层数”来算，就是向下取整再加 1。这个数量级的结论来自“每一层的节点数翻倍”这个铁律：层数每增加 1，最多能装的节点数就翻一倍，所以 n 个节点只需要大约 log n 层。本篇第 3 章会看到，完全二叉树的编号规律可以直接变成数组下标，这正是堆、线段树等数据结构能“又省空间又快”的秘密。先把这颗种子种下，后面会发芽。

不过，前三篇我们都还停留在“画图”的阶段：拿笔画一棵树，用文字描述它的形状。程序员不能只画图，程序员要让树真正跑起来。从下一篇的遍历到后面的二叉搜索树、堆、字典树，所有算法都建立在一个前提之上：树已经被存进内存了。存储方式决定了每个操作的快慢，甚至决定了某些操作“能不能做”。所以本篇不是枯燥的“内存考古”，而是给后面所有算法打地基。

1 问题引入：概念是树，内存却是线性的

先看看内存长什么样。你可以把内存想象成一条很长很长的街道，街道两侧是一排一模一样的门牌号：0 号、1 号、2 号、3 号……每个门牌号对应一个内存单元，程序运行时，数据就住在这些单元里。机器通过地址（address）找到它们，地址就是门牌号。这条街有个特点：它是线性的，也就是说，所有门牌号排成一条直线，0 号旁边是 1 号，1 号旁边是 2 号，不可能出现“0 号楼上住着 1 号”这种事。现代计算机的地址空间动辄几十 GB，换算成门牌号就是几百亿个，但它依然是一条街，而不是一座楼。

而树呢？树是层次的：根在“上面”，孩子们在“下面”，孙子在“更下面”；同一层的节点之间没有上下级关系，只有左右顺序。一棵树的形状是往四面八方“长”的，不是排成一排的。这就是本篇问题的全部矛盾：数据结构的形状是二维甚至多维的，而物理内存只有一维。把一棵树塞进内存，本质上是在做一次“降维打击”：我们必须找到一种办法，用一维的地址，把二维的父子关系完整地表达出来，而且不能丢信息——以后想从任何一个节点出发找到它的孩子、父亲、兄弟，都得办得到。

怎么表达“关系”呢？计算机里有两套基本思路。第一套思路是指路：每个节点不直接告诉别人“我的孩子在哪”，而是保存一个指针（pointer），指针的值就是孩子所在的内存地址。你顺着地址找过去，就找到了孩子。这就好比你家门上贴着一张纸条，写着“我儿子的家在 10086 号”，想找儿子，照着纸条走过去就行。第二套思路是算路：不保存任何地址，而是把节点放进一个连续的数组里，让“父亲和孩子的下标之间”存在一个固定公式。你只要知道自己的下标，一算就能算出孩子的下标。这就好比整条街的住户按家族谱系安排，规定“住在 2k 号的人，两个孩子住在 4k 号和 4k+1 号”，谁也不用贴纸条，公式就是规矩。

这两套思路衍生出我们今天的主角们：**链式存储（linked storage）**用指针表达关系；**顺序存储（sequential storage）**用数组下标表达关系；**双亲表示法（parent representation）**只记录“我的爸爸是谁”，是一种极简但偏科严重的方案；孩子表示法与孩子兄弟表示法则是链式思路在多叉树上的变体，其中“左孩子右兄弟”还能把多叉树变成一棵二叉树。看到这里你可能会问：这么多方案，我到底该学哪个？答案是：都该学。因为它们在真实世界全都活着——链式存储是绝大多数语言里“对象+引用”的树；数组存储是堆和线段树的命根子；双亲表示法藏在并查集这类数据结构里；孩子兄弟表示法则是文件系统、编译器符号表等场景的老朋友。

选存储方案的时候，心里要始终握着四把尺子：查孩子的代价（从一个节点走到它的孩子要几步）、查父亲的代价（反向走到爸爸要几步）、空间开销（每个节点额外要存多少“关系信息”）、遍历/序列化的方便程度（能不能顺着结构把整棵树走完、能不能把它完整地写进文件）。没有一种方案四项全能，每种方案都是在这四把尺子之间做取舍。比如，链式存储查孩子很快，查爸爸却很痛苦；数组存储什么都不用存，却能在一棵歪脖树上浪费掉大半内存。这正是数据结构迷人的地方：每个选择都有价格，聪明人先看清价格再掏钱。

本篇的路线图如下：第 2 章讲最常用的链式存储；第 3 章讲数组存储和它背后的下标数学；第 4 章讲双亲表示法；第 5 章讲孩子表示法和孩子兄弟表示法；第 6 章把四种方案放进同一张对比表；第 7 章预告序列化——也就是“怎么把内存里的树完整地保存成文件”，为第 5、6 篇的遍历做好衔接；最后是速查表和自测题。每一章我都会先讲“长什么样”，再讲“代价是什么”，最后讲“什么时候用它”。

2 链式存储：最常用、最直观的方案

2.1 指针：在内存里“指路”

在讲树之前，先回忆一个老朋友——链表。链表的每个节点除了保存数据，还保存一个 next 指针，指向下一个节点。你问“下一个是谁？”，节点不回答，而是给你一个地址，让你自己走过去看。这种“给你地址，你自己去找”的机制，就是指针的本质。链表为什么不能只靠“位置相邻”来连接？因为内存里的节点是动态分配的，A 节点和 B 节点可能相隔十万八千里，也可能正好挨在一起，我们没法保证它们的物理位置相邻，所以必须用地址显式地“指路”。

树比链表复杂在哪？链表的每个节点只有一个“出口”（next），而树的节点可能有多个“出口”（孩子）。二叉树的节点最多两个孩子，所以它的“指路”工作很简单：每个节点准备两个指针，一个指向左孩子，一个指向右孩子。没有孩子的地方，指针就指向空（null），表示“这条路到头了”。这就是二叉链表（binary linked list）：一张由节点和指针织成的网，网上的每个结都记得自己左右两条路的地址。

你可能会想：为什么不直接给每个节点分配一块内存，然后规定“左孩子一定存在我旁边的位置”？答案是：做不到，也不划算。树是动态生长的，你无法预知节点会以什么顺序创建，也无法预知树最终会歪成什么形状；强行固定位置只会导致大量空位。指针方案的好处恰恰是自由：节点爱在哪块内存就在哪块内存，关系由指针来维系，树的结构想怎么变就怎么变。链表时代我们牺牲“随机访问”换来了“动态插入删除”，树也一样：指针换来的自由，是我们心甘情愿付的价格。

2.2 二叉链表的节点长什么样

用 TypeScript 定义一个最简单的二叉树节点，只需要三个字段：值、左孩子指针、右孩子指针。下面的代码是全篇最基础的一块砖，请务必看懂：

// 二叉树节点：值 + 左孩子指针 + 右孩子指针
class TreeNode<T> {
  val: T;                 // 这个节点存的值
  left: TreeNode<T> | null;  // 指向左孩子；没有左孩子就是 null
  right: TreeNode<T> | null; // 指向右孩子；没有右孩子就是 null

  constructor(val: T) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

请留意两个细节。第一，left 和 right 的类型是 TreeNode<T> | null，这说明“左孩子”和“右孩子”的位置永远存在，只是内容可能为空。在概念上，哪怕一棵二叉树只有右孩子，它的“左”这个位置依然存在——这一点在数组存储里会变成噩梦，我们到第 3 章再算账。第二，节点里没有父亲指针。创建完一个节点，它不知道自己的爸爸是谁；爸爸是在后来“连接”时单方面认定的。这种“孩子不认爹、爹只认孩子”的设计，正是链式存储查父亲困难的根本原因，2.5 节会专门讲。

2.3 亲手连一棵树

有了节点类，建一棵树的过程就很朴素：先造出一个个孤零零的节点，再用指针把它们连起来。比如我们要建一棵 5 个节点的二叉树，形状是：根 A 有两个孩子 B 和 C，B 的左孩子是 D，C 的右孩子是 E。代码可以这样写：

// 先造 5 个孤零零的节点
const a = new TreeNode("A");
const b = new TreeNode("B");
const c = new TreeNode("C");
const d = new TreeNode("D");
const e = new TreeNode("E");

// 再用指针把它们连成树
a.left = b;   // A 的左孩子是 B
a.right = c;  // A 的右孩子是 C
b.left = d;   // B 的左孩子是 D
c.right = e;  // C 的右孩子是 E

// 验证：从根出发走到 D
console.log(a.left?.left?.val); // 输出 D

这段代码读起来像在“挂灯笼”：先把灯笼一个个买回来，再决定谁挂在谁的左边、谁的右边。你注意看，创建和连接是两步完成的：创建时节点之间毫无关系，连接之后关系才诞生。这与数组完全不同——数组一出生，位置关系就固定了；而链式树的关系是“后天培养”的。也正是因为关系是后天培养的，我们才能随心所欲地插入新节点、摘掉旧子树、把一棵子树搬到另一个位置：只要重新接几根指针，树就变样了。

把节点一个一个造出来，再把指针一根一根连上，一棵树就在内存里“长”了出来。这里的关键是：树的结构不是印在一整块内存上的，而是靠指针一块一块拼起来的。

2.4 内存布局长什么样

链式树的节点在内存里通常不挨在一起。程序运行时，每个节点通过 new 动态分配，操作系统在堆（heap）里找一块空闲内存给这个节点用。A 节点可能分配在地址 1008，B 节点可能分配在地址 2040，C 节点又可能在 3012，它们就像城市里散落的几栋房子，彼此之间隔着别的程序的垃圾、数组、字符串。真正把它们连成一棵树的，只有指针。下面这张示意图展示了一棵 5 节点二叉树在内存里的“散装”样子：

地址只是“户口”不是“家谱”，谁先谁后与树的父子关系毫无关系；而箭头只从父亲指向孩子，这正是链式存储查父亲困难的根本原因。

这张图里有几个要点值得盯着看。第一，地址本身没有任何规律：A 是 1008，B 是 2040，C 是 3012，谁先谁后跟树的父子关系毫无关系。你不能说“地址小的就是爸爸”，地址只是“户口”，不是“家谱”。第二，指针是单向的：A 知道 B 在哪，B 却不知道 A 在哪。箭头从父亲指向孩子，这是二叉链表的默认方向，也是后面“查父亲难”问题的根源。第三，空指针就是路标：B 的右指针是空，意思是“我没有右孩子，这条路不通”，而不是“我的右孩子住在地址 0”。计算机看到空指针就知道该停下来了，这是遍历时判断递归边界的依据。

还有一个容易被忽略的现实问题：因为节点分散在内存各处，程序沿着指针跳来跳去时，CPU 的缓存很难帮上忙。现代 CPU 访问内存时，会把附近的一小片数据一次性搬进高速缓存，如果数据是连续的一排，搬一次能用十几次；而链式树的指针像兔子一样乱跳，每次访问几乎都要重新去内存“取货”。这就是为什么很多高性能的树实现（比如某些数据库的 B+ 树）宁可牺牲一点直观性，也要把节点尽量排进连续内存。记住这个伏笔，第 3 章数组存储的优势之一就是“连续”。

2.5 想找爸爸？链式存储的尴尬

链式存储给了孩子“被找到”的便利，却欠了孩子一个“找到爸爸”的能力。从根出发，顺着左指针、右指针往下走，找孩子、找孙子、找重孙，一路畅通；但如果你手里只有一个节点 D，想问“我的爸爸是谁？”，D 只能摊手——它的结构里根本没有爸爸的地址。想回答这个问题，唯一的办法是回到根，从上往下把整棵树搜一遍，边搜边记录“谁的孩子是 D”，搜完整棵树才能给出答案。一次查找要遍历全树，代价是 O(n)，这在很多场景下是不可接受的。

怎么解决？最直接的办法是给节点再加一个 parent 指针，让每个孩子也记住爸爸的地址。代码只多一行字段：

// 带父指针的二叉树节点
class TreeNodeWithParent<T> {
  val: T;
  parent: TreeNodeWithParent<T> | null; // 指向父亲；根的父亲是 null
  left: TreeNodeWithParent<T> | null;
  right: TreeNodeWithParent<T> | null;

  constructor(val: T) {
    this.val = val;
    this.parent = null;
    this.left = null;
    this.right = null;
  }
}

但“多一个字段”不是免费的午餐。首先，内存变贵了：一个指针在 64 位系统上通常占 8 字节，原本每个节点要存 2 个指针（16 字节），加了 parent 变成 3 个指针（24 字节），关系信息的开销直接涨了 50%。如果树的节点只有 1 万个，这就多花了 8 万字节，约 78 KB，看起来不多，但放大到千万级节点就是几十 MB。其次，维护变麻烦了：每次连接父子关系，都要记得双向赋值——不仅 a.left = b，还要 b.parent = a；删除子树、搬移子树时，所有涉及的 parent 指针都要同步更新，漏掉一个，树就“断亲”了。第三，parent 指针会制造循环引用：孩子指爸爸、爸爸指孩子，垃圾回收器处理循环引用时要多绕几个弯（现代 GC 大多能处理，但代价确实存在）。

所以工程上的做法不是“一律加 parent”，而是“需要往上走的场景才加”。红黑树在旋转时要频繁调整父子关系、需要沿着节点一路向上检查颜色，所以它的实现几乎都带 parent 指针；普通业务里的树如果只做从上往下的查找和展示，就不必加。加不加 parent，本质上是一次“空间换时间”的经典交易：多花一点内存和一点维护成本，换来 O(1) 的查父亲操作。这个权衡思路，后面每一篇都会反复出现。

2.6 多叉树的链式变体：孩子数组与孩子链表

二叉树的节点只需要两个指针，因为孩子的数量被“二”限制死了。可普通树的节点想有几个孩子就有几个孩子：文件系统里一个目录可能只有 1 个子目录，也可能有 500 个。此时“左、右”两个指针就不够用了。链式思路怎么扩展？主流有两种变体。

第一种叫孩子数组（children array）：节点里保存一个数组，数组的每个元素是一个指向孩子的指针。数组可以动态增长，孩子多就多装几个，孩子少就少占点。TypeScript 写起来非常自然：

// 多叉树节点：值 + 孩子数组
class MultiTreeNode<T> {
  val: T;
  children: MultiTreeNode<T>[]; // 孩子的指针都放在这个数组里

  constructor(val: T) {
    this.val = val;
    this.children = [];
  }
}

const root = new MultiTreeNode("R");
const a = new MultiTreeNode("A");
root.children.push(a); // 把 A 挂成 R 的第一个孩子
root.children.push(new MultiTreeNode("B"));

孩子数组的好处是：想找第 k 个孩子，直接 children[k]，一步到位；想遍历所有孩子，循环数组即可。坏处是：数组本身需要连续内存，孩子数量频繁变化时会反复扩容、拷贝，而且如果一棵树大多数节点都只有一个孩子，数组里也会留下“容量大于实际个数”的浪费。JavaScript 的数组还会存储额外的长度信息，开销比裸指针多一点。

第二种叫孩子链表（child linked list）：不把孩子的指针放进一个数组，而是把它们串成一条链表。每个树节点只保存“第一个孩子”的指针，第一个孩子里再存“下一个孩子”的指针，链表的每个元素其实代表一条“父→子”的边：

// 孩子链表中的“边节点”：代表一条父→子的边
class ChildLink<T> {
  child: MultiTreeNode<T>;     // 这条边指向哪个孩子
  next: ChildLink<T> | null;   // 下一条边（下一个孩子）
}

// 树节点：只记住第一条边
class MultiTreeNodeLinked<T> {
  val: T;
  firstChild: ChildLink<T> | null; // 第一个孩子；没有孩子就是 null
}

孩子链表的好处是：孩子数量变化时，只需要在链表头部插入或摘除节点，不需要成片地移动内存；孩子少的时候几乎没有浪费。坏处是：想找第 k 个孩子必须从 firstChild 开始沿 next 走 k 步，是 O(k) 而不是 O(1)。这两种变体没有绝对优劣，规则仍然是“看你最常做什么”：频繁按序号取孩子，用数组；孩子数量动态剧烈变化、经常插删，用链表。它们和孩子兄弟表示法（第 5 章的主角）都属于“链式家族”，只是关系指针的挂法不同。

下面这张图是孩子数组方式下的一棵多叉树，节点的孩子列表就是它的“出口清单”：

叶子节点的 children 是空数组，但数组对象本身仍占一点头信息；如果换成孩子链表，叶子直接存 null 更省。

注意叶子节点的 children 数组是空的，但数组对象本身还存在（占一点头信息）；如果用链表变体，叶子的 firstChild 直接是 null，连空数组都省了。这些细节看似抠门，在大规模数据里就是几百万个对象的内存差别。

2.7 链式存储的优缺点

现在把链式存储的账本摊开。优点有四条：第一，直观，节点结构几乎就是树的形状，代码读起来跟概念图一一对应，初学者最容易上手；第二，动态，插入、删除、移动子树只需调整指针，不需要搬动其他节点，时间复杂度是 O(1)（前提是已经拿到了目标位置的指针）；第三，按需分配，树有几个节点就分配几个节点，不会为了“可能存在的孩子”提前预留空间；第四，与递归天然契合，前序、中序、后序遍历（第 5 篇的主角）在链式结构上写起来最短。

缺点也有四条：第一，指针开销大，二叉树每个节点至少要存 2 个指针，存值之外还要付“关系税”；第二，查父亲难，没有 parent 指针就得全树搜索，加 parent 指针又要多付内存和维护成本；第三，缓存不友好，节点散落内存，指针跳来跳去，CPU 缓存命中率低，大数据量下性能可能不如连续存储；第四，不能直接序列化，指针是内存地址，换个进程、换个运行时间地址就全变了，把树存进文件前必须先做“指针翻译”工作，这正是第 7 章序列化的由来。

所以链式存储最适合的场景是：树的形状动态变化、节点数量不太夸张、主要操作是“从根往下走”的通用场合。算法题里最常写的树、编译器里的抽象语法树、XML/JSON 解析出来的文档树，基本都是链式存储。它不是什么花哨的绝招，却是用得最广的默认答案。

3 顺序存储：把树平铺进数组

3.1 完全二叉树的下标魔法

链式存储用指针“指路”，顺序存储换了一个思路：用下标“算路”。做法是，把树的所有节点放进一个连续数组，然后约定一套编号规则：根节点放在数组下标 1 的位置，然后从上到下、从左到右，给每个节点依次编号。如果你用的是完全二叉树，这套编号会出现一个近乎魔法的规律——节点 i 的左孩子编号是 2i，右孩子编号是 2i+1，父亲编号是 i 除以 2 后向下取整。也就是说，只要知道任意一个节点的下标，不需要任何指针，靠一个乘法、一个加法就能算出它的孩子和爸爸。

为什么偏偏是 2i 和 2i+1？因为完全二叉树每一层的节点都是“从左到右挤满”的，所以编号天然符合二进制规律。根是 1，它的两个孩子是 2、3；2 号节点的两个孩子是 4、5；3 号节点的两个孩子是 6、7；4 号节点的两个孩子是 8、9……你可以自己在纸上画一棵 15 个节点的完全二叉树，把编号填进去，然后验证：每个编号 i，两个孩子确实恰好是 2i 和 2i+1。这个规律的本质是：第 k 层第一个节点的编号是 2 的 k 次方，而每往右挪一个位置，编号就加 1；一个节点在第 k 层的第 j 个位置，它的左孩子就是下一层的第 2j-1 个位置，编号正好等于两倍的父节点编号。数学上可以用归纳法严格证明，这里我们先用直觉和例子把它“看到”：

编号连续不是运气，而是“每层从左到右挤满”的定义保证；一旦编号跳号，数组里就必须给空位留格子。

如果把这 7 个节点按编号顺序塞进数组 A，得到的就是 A[1]=根、A[2]、A[3]……一直到 A[7]，每个位置都有人住，一个空洞都没有：

这就是顺序存储的核心诱惑：零指针、连续内存、查父子都是 O(1)——但前提是树“住得满”。

“一个空洞都没有”不是运气，而是完全二叉树的定义保证的：它的节点编号从 1 连续排到 n，中间不可能跳号。正因为编号连续，数组的下标才能和节点一一对应；反过来，一旦树不是完全二叉树，编号就会出现空洞，数组里就会出现没人住的空位——3.2 节会专门算这笔账。

用代码表达下标公式非常短：

// 约定：数组 A 从下标 1 开始用，A[1] 是根
function leftChild(i: number): number {
  return 2 * i;      // 左孩子下标
}
function rightChild(i: number): number {
  return 2 * i + 1;  // 右孩子下标
}
function parent(i: number): number {
  return Math.floor(i / 2); // 父亲下标
}

// 例子：5 号节点的父亲是 2，左孩子是 10，右孩子是 11
console.log(parent(5));    // 2
console.log(leftChild(5)); // 10
console.log(rightChild(5));// 11

很多语言（包括 JavaScript）的数组下标习惯从 0 开始，此时根放在 A[0]，公式会整体偏移：左孩子是 2i+1，右孩子是 2i+2，父亲是 (i-1)/2 向下取整。两个约定没有本质区别，只是“1 基”的公式更漂亮（2i、2i+1），面试和教科书里最常见；“0 基”的公式和语言习惯更贴合。你只需要记住：选一个约定，写代码时从头到尾别混用。混用是数组存储最常见的 bug 来源——一个函数用 1 基，另一个函数用 0 基，查来查去就是差 1。

// 0 基版本：根在 A[0]
function leftChild0(i: number): number {
  return 2 * i + 1;
}
function rightChild0(i: number): number {
  return 2 * i + 2;
}
function parent0(i: number): number {
  return Math.floor((i - 1) / 2);
}

到这里你可能已经感觉到：数组存储最大的诱惑是零指针。父子关系不再需要额外的内存来记录，而是写死在数学公式里。但这份诱惑有一个前提：树必须“住得满”。如果树长得歪歪扭扭，数组里就会布满空洞，公式照常工作，空间却在哗哗地漏。下一节，我们来看这个“漏”到底有多严重。

3.2 普通二叉树：空洞与空间浪费

先明确一件事：2i、2i+1 这套公式，对任何一棵二叉树都“算得动”，因为它本质上是在按“完全二叉树的完整位置表”给节点编号。问题在于，普通二叉树不是每个位置都有人住，编号一旦跳号，数组里就必须给跳掉的位置留一个空位。空位就是空洞，空洞就是白花的内存。

来看一个极端但常见的例子：一棵只有 3 个节点的“歪脖树”——根 A 只有右孩子 B，B 又只有左孩子 C。如果按完全二叉树的位置编号：A 是 1 号，A 的左孩子位置（2 号）空着，B 只能排到 3 号；B 的左孩子位置（6 号）是 C，B 的右孩子位置（7 号）空着。于是数组要开到下标 6，才能放下 C，而 2、4、5 三个位置全是空洞：

注意 C 的编号是 6 而不是 4：编号必须按完整位置表排，跳掉的位置在数组里也必须留出格子。

对应到数组里，长度被撑到 6，实际有用的只有 3 个格子：

这还算温柔；如果整棵树一直往右歪，第 n 个节点的下标会变成 2 的 n 次方减 1，30 个节点就能撑爆十亿级数组。

3 个节点要 6 个格子的空间，利用率只有一半。这还算温柔的。想象一棵“一直往右歪”的链：第一个节点在 1 号，第二个节点在 3 号，第三个节点在 7 号，第四个节点在 15 号……第 n 个节点的下标是 2 的 n 次方减 1。也就是说，n 个节点的右斜链需要一块长度约 2 的 n 次方的数组！写程序的人看到这个数字应该会倒吸一口凉气：30 个节点就能撑爆一块十亿级别的数组，哪怕每个格子只占 1 字节，那也是 1 GB 的“空气”。链式存储放同样的树，30 个节点就是 30 个节点的开销，而数组存储被空洞直接推上指数级。这就是普通二叉树不能盲目用数组存的根本原因。

所以结论要钉在墙上：顺序存储只适合“住得满”的树。最理想的住户是完全二叉树，次之是“空洞率可控”的近似完全结构；对于歪歪扭扭的普通二叉树，数组存储不是“有点浪费”，而是可能浪费到不可用的程度。这个结论不是数组的错，而是“用位置编号表达关系”这一方案的固有代价：编号越稀疏，数组越长。

3.3 从数组里读出整棵树

如果树是完全二叉树（或至少空洞不多），数组怎么当树用？我们用一个具体的例子走一遍。假设数组 A 从下标 1 开始，依次放着 5、3、8、1、4、7、9 这 7 个数，它表示的完全二叉树是：根 5，左孩子 3、右孩子 8；3 号节点的孩子是 1 和 4；8 号节点的孩子是 7 和 9。想知道某个节点的孩子或父亲，用上一节的公式直接算：

const A = [null, 5, 3, 8, 1, 4, 7, 9]; // A[0] 空着不用，下标 1..7 是节点

console.log(A[leftChild(2)]);   // 2 号节点的左孩子：A[4] = 1
console.log(A[rightChild(3)]);  // 3 号节点的右孩子：A[7] = 9
console.log(A[parent(5)]);      // 5 号节点的父亲：A[2] = 3

你可能会说：这看起来不像树啊，不就是普通数组吗？没错，这正是数组存储的妙处——树是“藏”在数组里的。我们不再显式地记录“谁是爸爸”，而是把父子的位置关系编码进下标。任何一个节点，它的孩子下标和父亲下标都是一道算术题，不用查表、不用指针，O(1) 就算出来。递归地遍历一棵数组里的树，代码也异常简洁：

// 前序遍历数组里的完全二叉树（下标从 1 开始）
function preorderFromArray(i: number, depth: number): void {
  if (i >= A.length) return;        // 越界 = 不存在这个节点
  console.log("  ".repeat(depth) + A[i]); // 先访问自己
  preorderFromArray(2 * i, depth + 1);    // 再访问左子树
  preorderFromArray(2 * i + 1, depth + 1); // 最后访问右子树
}

注意，这个递归和链式树的递归长得几乎一模一样，区别只是“找左孩子”从“访问 left 指针”变成了“计算 2i”。这份“长相相似”不是巧合：链式存储把关系放在指针里，数组存储把关系放在公式里，但树的逻辑结构是同一个。这也解释了为什么第 5、6 篇讲遍历时，我们可以同时给出链式版和数组版代码——遍历算法本身不挑存储，它只认“怎么找到孩子”这一个接口。

当然，数组版有个边界要小心：完全二叉树里下标不会越界，但代码里还是要判断 i >= A.length，因为最后一层可能不满，比如 7 个节点的树，5 号节点的右孩子下标是 11，已经超过数组长度，递归就会自然终止。如果是带空洞的普通二叉树数组，还要额外判断 A[i] 是否为 null，否则会把空洞当成节点访问。这些小细节写代码时最容易踩，面试时也常被用来挖坑。

3.4 堆为什么能用数组：先埋一颗种子

前面说了这么多“数组只适合完全二叉树”，你可能想问：现实里真有那么多完全二叉树吗？有，而且有一个你绝对听过的数据结构，就是堆（heap）。堆是“树系列”第 16 篇的主角，现在先埋下伏笔：堆本质上是一棵完全二叉树，外加一条“父子大小关系”的规则——大顶堆要求每个节点都比它的孩子大（或相等），小顶堆要求每个节点都比它的孩子小（或相等）。正因为堆“必须”是完全二叉树，它才能心安理得地住进数组；而它住进数组之后，才换来优先队列那种“插入、取最大值都是 O(log n)”的惊人效率。

堆的所有核心操作都走 2i、2i+1、i/2 这条下标通道；没有完全二叉树的下标数学，就没有堆的数组实现。

上面这棵堆，你观察它的形状：每一层从左到右都是满的，最后一层也连续，没有任何空洞。所以它放进数组时一个空格子都不浪费：A[1]=50、A[2]=30、A[3]=40、A[4]=10、A[5]=20、A[6]=15，整齐得像一排兵。堆的所有核心操作——插入时从末尾“上滤”，删除时把末尾元素搬到根再“下滤”——走的路都是 2i、2i+1、i/2 这条下标通道。可以说，没有完全二叉树的下标数学，就没有堆的数组实现；没有数组的连续内存，堆就失去了它最引以为傲的紧凑与高速。

这颗种子先埋在这里，等你读到第 16 篇时，会看到一棵堆从“数组长出来”的全过程。现在你只需要记住一句话：堆 = 完全二叉树的形状 + 父子大小规则 + 数组存储。三块拼图，缺一不可。

3.5 顺序存储的优缺点

把数组存储的账本也摊开。优点有四条：第一，几乎零关系开销，父子关系由下标公式免费提供，不需要为每个节点存指针；第二，连续内存、缓存友好，节点一个挨一个，CPU 遍历时命中率极高，大数据量下往往比链式快一个数量级；第三，查父亲 O(1)，这在链式存储里是奢望，在数组里只是一次除法；第四，序列化极其简单，数组本身就是一个可以直接写进文件的连续序列，不用翻译指针（第 7 章会展开）。这也是为什么很多数据库、优先队列、线段树的底层偏爱数组。

缺点同样四条：第一，只对完全二叉树友好，普通树会有空洞，歪链甚至指数级浪费；第二，插入删除要搬元素，数组的长度是固定的，在中间插一个节点往往要移动一片元素，动态性远不如链表；第三，扩容成本高，数组满了要重新分配一块更大的内存并整体拷贝，链式存储则没有这个问题；第四，结构变化会连累下标，一旦树形变化导致编号重排，所有下标引用都要跟着变，维护起来很别扭。所以数组存储适合“结构基本稳定、形状接近完全、操作以下标访问和遍历为主”的场景——堆、线段树、完全二叉树形态的哈夫曼编码表，都是它的主场。

4 双亲表示法：只关心爸爸是谁

4.1 只存“爸爸是谁”

链式存储的默认方向是“从上往下”，数组存储把方向藏在公式里，而**双亲表示法（parent representation）**干脆把整棵树的“关系信息”压缩成一行：每个节点只记录一件事——我的父亲是谁。实现上通常是一个数组 parent，数组的下标代表节点，数组的值代表父亲节点的下标；根没有父亲，用一个特殊值标记，比如 -1（有些实现用自己，有些用 null）。

一棵 6 个节点的树：A 是根，B、C 是 A 的孩子，D、E 是 B 的孩子，F 是 C 的孩子。约定节点按下标 0 到 5 排列为 A、B、C、D、E、F，那么 parent 数组就是 [-1, 0, 0, 1, 1, 2]：A 的父亲是 -1（根），B 的父亲是 0（A），C 的父亲是 0（A），D 的父亲是 1（B）……这张表虽然只有一行数字，却完整地记录了所有的父子关系：

它只擅长“向上”：查父亲 O(1)、追溯祖先链每步 O(1)；想知道“我的孩子是谁”却必须扫一遍全表，O(n)。

代码更是短得惊人——找爸爸就是一次数组访问：

// parent[i] = 节点 i 的父亲下标；-1 表示 i 是根
const parent = [-1, 0, 0, 1, 1, 2];

function fatherOf(i: number): number {
  return parent[i]; // O(1)，一次数组访问
}

// 从任意节点一路向上走到根
function rootOf(i: number): number {
  while (parent[i] !== -1) i = parent[i];
  return i;
}

注意这个方案有多“偏科”：它只能回答“爸爸是谁”和“祖先链怎么走”，却回答不了“我的孩子是谁”。想知道某个节点的孩子，必须把整个 parent 数组扫一遍，把所有 parent[j] === i 的 j 收集起来，一次 O(n)。想知道兄弟，也要先扫数组。换句话说，双亲表示法把“向下”的信息全部扔掉，换来极致的“向上”效率。它不是树的完整存储方案，而是一个面向特定操作的关系表。

4.2 能做什么、不能做什么

双亲表示法的能力边界非常清晰。擅长的事有三件：查父亲 O(1)；从任意节点追溯祖先链，直到根，每步 O(1)，适合“这个节点属于哪棵子树/哪个集合”的问题；还有判断两个节点是否“同宗”——各自往上走到根，看根是否相同。不擅长的事也有三件：查孩子 O(n)；按层次从上到下遍历不方便，因为要反复扫描数组才能把每层节点挑出来；动态增删节点麻烦，因为数组下标要求稳定，插入一个新节点往往要给一堆节点重新编号。

空间上，每个节点只需要存一个整数（或一个指针），比二叉链表的两个指针省，也比多叉链表的若干指针省得多；但它比纯数组顺序存储多花“每个节点一份关系值”的钱。更关键的是，双亲表示法通常要求节点编号静态：你先给所有节点编好号，再用编号建表。如果树在运行时会频繁插入、删除，编号一乱，表就乱了。所以它很少作为“唯一主存储”长期使用，更多是作为某个算法内部的一张辅助表——比如下面的并查集。

4.3 典型应用：并查集里的森林

双亲表示法最著名的“工作单位”是并查集（union-find）。并查集维护的是若干不相交集合，每个集合用一棵树表示，树的根就是集合的代表。它的底层结构就是一个 parent 数组：一开始每个元素自成一家，parent[i] = i；合并两个集合时，把一棵树的根挂到另一棵树的根下面，只改一个值；查找某个元素属于哪个集合时，沿着 parent 一路向上走到根。看，这完全就是一棵用双亲表示法存的森林：

class UnionFind {
  parent: number[];

  constructor(n: number) {
    // 一开始每个人都是自己的根
    this.parent = Array.from({ length: n }, (_, i) => i);
  }

  find(x: number): number {
    // 沿着“爸爸的爸爸”向上走，直到自己是根
    while (this.parent[x] !== x) x = this.parent[x];
    return x;
  }

  union(a: number, b: number): void {
    const ra = this.find(a);
    const rb = this.find(b);
    if (ra !== rb) this.parent[ra] = rb; // 一棵树的根挂到另一棵根下
  }
}

为什么并查集敢用这么“偏科”的结构？因为并查集的所有操作都只需要“向上走”：find 要向上，union 要先 find 再改一个 parent 值。它几乎不需要“查孩子”，所以双亲表示法的短板在这里根本不会暴露；而它的省内存、好实现，恰好是并查集要的。这个故事再次印证本篇的主题：存储方案没有最好，只有最合适。一个“什么都能干一点”的结构，往往不如一个“把一件事做到极致”的结构。

4.4 双亲表示法与链式存储的对比

把双亲表示法和链式存储放一起，差异一目了然。链式存储里，每个节点带着“孩子清单”，从根向下探索如鱼得水，但向上走要么加 parent 指针、要么全树搜索；双亲表示法正好相反，向上一步到位，向下寸步难行。链式存储的动态性极好，插入删除只动局部指针；双亲表示法依赖稳定编号，结构一变就要重排。链式存储的空间开销和节点数成正比（每个节点都有指针），双亲表示法同样每节点一份开销，但它那份是“一行数字”，通常更紧凑。两者不是替代关系，而是互补关系：当你需要“既快向下又快向上”时，链式加 parent 指针才是正解；当你只需要“频繁向上、偶尔向下”时，双亲表示法更划算。

5 孩子表示法与孩子兄弟表示法：多叉树的专用招数

5.1 先看看多叉树有多“难伺候”

前面讲的链式存储、数组存储，其实都是围绕二叉树展开的：链式用两个指针，数组用 2i、2i+1 公式，全都建立在“每个节点最多两个孩子”的基础上。可现实世界里更多的是多叉树：文件系统里一个目录可以有 100 个子目录，组织架构里一个经理可以带 20 个下属，网页的 DOM 里一个 div 可以嵌套任意数量的子元素。这些树该怎么办？总不能让它们先“削成二叉树”再存吧？

答案分两步。第一步是孩子表示法（child representation）：既然孩子数量不确定，那就用“可以变长”的结构来装孩子。上一章 2.6 节已经介绍过两种变体：孩子数组用动态数组装孩子的指针，孩子链表用一条链表串起所有孩子。它们的共同点是：每个节点都直接保存“我的孩子有哪些”，从根出发向下探索非常自然。如果你把一棵多叉树画出来，孩子表示法的内存结构几乎就是原图的“翻版”，理解成本最低。

孩子链表的实现细节值得再看一眼：树节点里保存 firstChild，指向第一个孩子；每个“边记录”里保存 child（指向真正的孩子节点）和 next（指向下一条边）。于是从根出发，沿着 firstChild 找到第一条边，再沿着 next 一条条走下去，就能把根的所有孩子挨个访问一遍。这个“先走第一条边，再沿兄弟链横着走”的动作，是理解后面孩子兄弟表示法的钥匙，请记住这个节奏：先下探，再横走。

// 孩子链表：树节点 + 边记录
class ChildEdge<T> {
  child: MultiTreeNodeLinked<T>;
  next: ChildEdge<T> | null;
}

class MultiTreeNodeLinked<T> {
  val: T;
  firstChild: ChildEdge<T> | null;
}

孩子表示法的问题在于：每个节点的“关系信息量”不一样。一个节点有 10 个孩子，就要挂 10 条边；一个节点没有孩子，就什么都不挂。这本来没什么，但如果一棵树特别“稀疏”——大多数节点都只有一个孩子——那么孩子数组里会有大量空容量，孩子链表里则到处都是长度为 1 的链表。能不能设计一种结构，让所有节点的关系信息量都一样，固定两个指针，却能表达任意多个孩子？能，这就是左孩子右兄弟。

5.2 左孩子右兄弟：把多叉树变成二叉树

孩子兄弟表示法（child-sibling representation），也叫左孩子右兄弟（left-child right-sibling），核心思想只有一句话：一个节点的所有孩子，用一条“兄弟链”串起来，第一个孩子作为这个节点的“左孩子”，其余孩子依次作为前一个孩子的“右孩子”。翻译成节点结构，就是每个节点依然只保存两个指针，但它们的语义变了：

// 左孩子右兄弟节点：两个指针，语义换成“第一个孩子”和“下一个兄弟”
class LCRSNode<T> {
  val: T;
  firstChild: LCRSNode<T> | null;   // 左孩子 = 第一个孩子
  nextSibling: LCRSNode<T> | null;  // 右孩子 = 下一个兄弟
}

你别小看这个改动：它把“孩子数量不确定”的多叉树，变成了“每个节点只有两个指针”的二叉树！原来的第一个孩子现在挂在左指针上，原来的第二个、第三个孩子不再直接挂在父亲身上，而是依次挂在第一个孩子的右指针、第二个孩子的右指针上，形成一条向右延伸的链。父亲想找第二个孩子，先找左孩子（第一个孩子），再沿右链走一步。孩子多，链就长；孩子少，链就短。

来看一个具体例子。左边是一棵多叉树：根 R 有 A、B、C 三个孩子；A 有孩子 D；C 有孩子 E、F。右边是用左孩子右兄弟转换出的二叉树：

多叉树的麻烦在于“孩子数量不确定”，孩子数组要么扩容、要么预留，都会付出额外代价。

记住节奏“先下探，再横走”：找孩子先取左指针，再沿右链一路走；左指针表示“生”，右指针表示“亲”。

仔细对比两棵图：转换前 R 直接连着三个孩子，转换后 R 只连着一个“左孩子”A，B 和 C 变成了 A 的右链上的“兄弟”；同理，C 的孩子 E、F 中，E 是 C 的左孩子，F 是 E 的右孩子。原来“一个父亲、多个孩子”的扇形结构，被压成了“一个左孩子、一条右链”的二叉树形状。这就是多叉树转二叉树的核心编码：左指针表示“生”，右指针表示“亲”——左指针指向自己的第一个孩子，右指针指向自己的下一个兄弟。

转换之后怎么把“孩子”找回来？规则很简单：一个节点的所有孩子 = 左孩子 + 左孩子的右链上的所有节点。遍历孩子时，先取 firstChild，然后沿着 nextSibling 一直走，走到 null 为止：

// 打印 node 的所有孩子
function printChildren(node: LCRSNode<string>): void {
  for (let child = node.firstChild; child !== null; child = child.nextSibling) {
    console.log(child.val);
  }
}

这段代码同时揭示了孩子兄弟表示法的代价：找“第二个孩子”要沿右链走一步，找“第 k 个孩子”要走 k-1 步，是 O(k) 而不是 O(1)。孩子数组可以一步到位，孩子兄弟表示法却必须顺着链数过去。所以它适合“孩子不多、主要是挨个遍历”的场景，不适合“频繁按序号取第 k 个孩子”的场景。

5.3 为什么说这是一次“编码”

左孩子右兄弟不只是省空间的小技巧，它有一个更深刻的意义：任何一棵多叉树，都能被唯一地编码成一棵二叉树。反过来，任何一棵由“左孩子右兄弟”规则产生的二叉树，也都能唯一地还原成原来的多叉树。这种“一一对应”意味着，很多为二叉树设计的算法——前序、中序、后序遍历，深度优先搜索，甚至二叉树的序列化方案——都可以直接拿来处理多叉树：先把多叉树转成左孩子右兄弟的二叉树，跑完二叉树算法，再按规则还原。编译器、文件系统、各种通用树形库都在用这个思路，只不过有的把它们写进了节点结构，有的在遍历时临时转换。

还有一个数学上的彩蛋：左孩子右兄弟表示法证明了“二叉树在表达能力上并不比多叉树弱”。多叉树的“任意多个孩子”看着强大，但通过两条指针的巧妙复用，二叉树可以把同样的结构完整装下。这也是计算机科学里常见的“约简”思维：把复杂问题规约成已经会解决的问题。第 3 篇说二叉树是最受宠的树，左孩子右兄弟表示法从存储角度又补了一刀：它不只是“受宠”，它还能“一树多用”。

5.4 孩子兄弟表示法的应用场景

第一个经典场景是文件系统。文件系统里的目录树是多叉树：一个目录可以有任意多个子目录和文件。如果用孩子数组，每个目录都要维护一个可能很长的数组；如果目录大多只有一两个条目，内存浪费严重。很多经典实现采用“第一个孩子 + 兄弟链表”的方式：目录节点指向第一个条目，每个条目再指向它的兄弟条目，需要遍历一个目录时，顺着兄弟链走一圈即可。这种结构在 C 语言时代尤其流行，因为没有现成的动态数组可用，链表是最朴素的“可变长容器”。

第二个场景是把多叉树交给二叉树算法处理。比如你要对一棵多叉树做深度优先遍历、计算高度、判断两棵树是否同构，如果手头只有二叉树模板代码，可以先做一次左孩子右兄弟转换，套用模板，再还原结果。虽然现代工程里直接写多叉树遍历也不难，但在某些底层库或教学实现里，“转成二叉树”依然是最省事的路径。

第三个场景是节省指针开销。一个多叉树节点如果用“定长数组”实现，必须按最大可能孩子数预留空间，孩子少的节点就白白浪费；用左孩子右兄弟，每个节点固定两个指针，空间与节点数严格线性，最坏情况也不超 2n 个指针。对于节点数量巨大的通用树（比如大型目录、家族谱、知识图谱的树形投影），这笔账很可观。

5.5 孩子兄弟表示法的优缺点

优点：第一，节点结构固定，只有两个指针，空间开销确定且线性；第二，表达能力与二叉树等价，能把任意多叉树转成二叉树，复用二叉树算法；第三，动态性好，插入一个孩子只需要在兄弟链上调整一两个指针；第四，遍历孩子时“先左后右链”的顺序天然符合“先长子后次子”的直觉。

缺点：第一，找第 k 个孩子要沿兄弟链走 O(k) 步，没有随机访问；第二，找父亲依然困难，向上走要么全树搜索、要么再加 parent 指针；第三，兄弟链让“右指针”的语义不再是“右孩子”，初学时不注意会写出错误的遍历代码；第四，如果一棵树的节点普遍有大量孩子，兄弟链会很长，频繁访问后面的孩子时性能不如孩子数组。

选它还是选孩子数组？规则还是那句老话：孩子数量少、遍历为主、结构动态变化，选孩子兄弟；孩子数量多、经常按序号取孩子，选孩子数组。前者省空间、好复用，后者访问快、更直接。

6 四种方案放在一起比一比

现在四种方案都讲完了，把它们放进同一张表里，用同一套标准量一量。表中“孩子”指“给定一个节点，找到它的孩子”；“父亲”指“给定一个节点，找到它的父亲”；“兄弟”指“给定一个节点，找到它的兄弟”；“动态性”指“插入删除节点的方便程度”。复杂度统一按 n 个节点、k 个孩子的规模来写：

存储方案	查孩子	查父亲	查兄弟	额外空间	动态性	适用场景
链式存储（二叉链表）	O(1)，顺着指针	O(n) 搜全树；加 parent 则 O(1)	O(1)，经父亲取另一侧	每节点 2 个指针	好，指针一接一断	通用二叉树、动态树、算法题
顺序存储（数组）	O(1)，下标公式	O(1)，下标公式	O(1)，相邻下标	数组本身，普通树有空洞	差，插入删除要搬元素	完全二叉树、堆、线段树
双亲表示法（parent 数组）	O(n)，要扫描全表	O(1)，一次数组访问	O(n)，扫描全表	每节点 1 个关系值	差，依赖稳定编号	并查集、向上追溯祖先
孩子兄弟表示法	O(k)，左孩子沿右链	O(n) 搜全树；加 parent 则 O(1)	O(k)，沿兄弟链	每节点 2 个指针	好，兄弟链上调整	多叉树、文件系统、通用树

这张表最值得注意的不是“谁快谁慢”，而是没有一个方案在任何列里都拿第一。链式存储查孩子快、动态性好，但查父亲要付出代价；数组存储查父子都快、空间省，但动态性差、只欢迎完全二叉树；双亲表示法把查父亲做到极致，其余操作全部平庸；孩子兄弟表示法在多叉树上平衡了空间与动态性，却牺牲了按序号访问。所谓“最优存储”，永远要对着具体问题来问：你最常做的是哪个操作？数据规模多大？树形稳定还是天天变？多叉还是二叉？

实战里还经常出现混合方案：二叉树节点同时带 left、right、parent 三个指针（链式 + 回程）；数组里存值、另配一个双亲数组辅助“向上走”（顺序 + 双亲）；多叉树用孩子数组当主结构、再给每个节点存一个 parent 下标（孩子表示 + 双亲）。混合方案多花的空间，换来的是“两条路都走得通”的便利，代价就是维护成本上升。工程上有一条朴素的经验：先用最简单的主存储把功能跑通，再根据性能数据决定要不要加辅助结构。别一开始就追求“全都要”，那通常意味着“每一样都要维护”。

7 序列化预告：内存里的树，怎么存进文件

聊完四种内存存储方案，最后一个问题顺理成章地冒出来：内存里的树，怎么才能活到程序退出之后？程序一关，内存里的所有指针、所有节点瞬间归零；重启程序，树就没了。想把树保存到文件、写进数据库、发给另一台机器，必须把“住在内存里的树”翻译成“一串可以落盘的字节”，这个翻译过程叫序列化（serialization）；反过来，从字节重建出一模一样的树，叫反序列化（deserialization）。

序列化的最大障碍，就是我们开篇说的“指针”。指针的值是内存地址，地址只在本次运行里有效：今天 A 节点住在地址 1008，明天程序重启，同样的树可能住进完全不同的地址。把指针原样写进文件毫无意义，就像你把“我家住在 10086 号”写进日记，可别人搬家后地址全变了。所以序列化必须做一件事：把“地址”换成“身份”——用编号、顺序或嵌套关系来描述节点之间的连接，而不是用物理地址。

不同的存储方案，序列化难度天差地别。数组存储最轻松：数组本身就是一串连续的值，直接把数组和节点数写进文件，反序列化时原样读回数组，下标公式自动重建父子关系，连“翻译”都省了。双亲表示法也很轻松：文件里存一张“节点编号 + parent 编号”的表，读回来就是一个新 parent 数组，O(1) 查父亲的能力原样保留。链式存储最麻烦：指针没法直接写，必须先决定“用哪个顺序记录节点”，再在文件里用某种标记表达“左孩子是谁、右孩子是谁”，读文件时按同样的规则重建指针。麻烦归麻烦，它恰恰是下一篇章的入口——因为“用哪个顺序记录节点”，正是遍历算法研究的核心问题。

举个最直观的例子。一棵 3 个节点的链式二叉树，根 A、左孩子 B，想存成 JSON，最朴素的做法是把“指针”换成“嵌套对象”：每个节点写成 { "val": ..., "left": ..., "right": ... }，孩子用另一个对象表示，空子树用 null 表示。这样一个递归结构，文件里看起来就是一棵树的“文字版”：

{
  "val": "A",
  "left": {
    "val": "B",
    "left": null,
    "right": null
  },
  "right": null
}

你看，JSON 里没有地址，只有嵌套：A 的 left 字段不是“地址 1008”，而是“另一个对象”。反序列化时，解析器碰到嵌套对象就 new 一个新节点，碰到 null 就接空指针，树就重建出来了。这种“递归结构直接翻译”的方式，适合树形 JSON 本身；但它的缺点是文件里要写很多重复的字段名，节点一多体积膨胀。更紧凑的做法是：先按某种顺序把节点排成一列，再在文件里只写节点值和必要的空标记，重建时按同一顺序“反着走”。这个“某种顺序”，就是前序、中序、后序、层序——第 5、6 篇的主角。

指针是临时地址，不能直接落盘；所谓序列化，本质是把“关系”翻译成“顺序 + 标记”，这正是下一篇章遍历算法要解决的问题。

这张流程图把本篇和第 5、6 篇的关系画得明明白白：存储方案决定了“树怎么在内存里待着”，遍历决定了“树怎么排成一列”，序列化则把“排成一列”的结果落成文件。所以本篇不是孤立的一章：你现在理解了链式节点怎么用指针“指路”，第 5 篇讲深度优先遍历时，你会看到指针是怎么被一步步走完的；第 6 篇讲广度优先遍历时，你会看到“层”这个概念怎么变成访问顺序。等读完全系列再回头看这一章，你会觉得序列化不过是“遍历 + 文件格式”的组合拳。

还要提醒一个容易踩的坑：不是所有序列化都能无歧义重建。只写节点值、不写空标记，很多树会撞车——比如根 A 只有左孩子 B 的树，和根 A 只有右孩子 B 的树，只记值的话都是“A、B”两个字母，根本分不清。所以序列化方案必须自带“结构信息”：要么用嵌套对象（结构写在括号里），要么用空标记（null 占位），要么用双序列（前序 + 中序）互相校验。这些细节第 5 篇会专门展开，这里先埋下种子：序列化的本质，是把“关系”写成“顺序 + 标记”。

8 存储方式对比速查表

本章是全文的“收银台”，把四种方案浓缩成一张速查表。以后面试、做项目、写算法题，拿不准时回来扫一眼即可：

方案	关系怎么表达	最擅长	最怕什么	一句话口诀
链式存储（二叉链表）	每个节点两个指针指向孩子	动态插入删除、从根向下探索、通用二叉树	节点多且散、频繁向上查	“向下走，用指针指路”
顺序存储（数组）	下标公式 2i、2i+1 算父子	紧凑高效、缓存友好、查父子都快	非完全二叉树的空间空洞、动态增删	“形状整齐，数组最香”
双亲表示法	每个节点只记父亲的编号	向上追溯、判断同根、并查集	找孩子、动态增删节点	“只认爸爸，偏科到底”
孩子兄弟表示法	左孩子 + 右兄弟两条链	多叉树变二叉树、通用树的紧凑存储	按序号取第 k 个孩子	“先长子，再串兄弟”

如果你还是不知道怎么选，可以按下面这个“三问”流程走一遍。第一问：这棵树是多叉树吗？ 是，优先考虑孩子兄弟表示法或孩子数组；否，进入第二问。第二问：树的形状接近完全二叉树，且结构基本稳定吗？ 是，优先数组存储，堆、线段树都这么干；否，进入第三问。第三问：主要操作是向上追溯吗？ 是，考虑双亲表示法（比如并查集）；否，老老实实用链式存储，需要时再加 parent 指针。这个流程不保证最优，但保证你在 30 秒内能给出一个不丢人的答案。

最后用一句话给全篇收个尾：树是逻辑的，内存是线性的，指针和下标是两种把“层次”翻译成“位置”的语言；看懂四种翻译方案，你就看懂了树的下半场——从“画出来的树”到“跑起来的树”。

9 实战走查：四棵真实的树怎么选

理论讲完了，但“怎么选”这件事，光看表格还是不够直观。这一章我们走进四棵最常出现在真实代码里的树，看看它们最终选了哪种存储、为什么选它。每一棵树都是一个完整的决策案例，建议你跟着走查一遍，把自己代入“选型负责人”的角色。

场景一：二叉搜索树——链式是默认答案

第一棵树是二叉搜索树（BST）：每个节点的左子树里所有值都比它小，右子树里所有值都比它大，查找、插入、删除全都从根出发，每走一步比较一次大小，决定向左还是向右。它的核心操作是“向下探索”，而且树形会随着插入顺序不断变化：可能长得很匀称，也可能歪成一条链，完全无法提前预订形状。选什么？

答案是链式二叉链表。原因有三：第一，BST 的操作全部是“从根向下走”，链式的 left、right 指针就是为这条路量身定做的；第二，插入删除非常频繁，链式只要改一两个指针，数组则要搬动大片元素；第三，树形不可预测，数组存储要么面对空洞、要么频繁扩容。所以几乎所有教材和语言库里的 BST、AVL 树、红黑树，节点结构都是 { val, left, right } 的变体。红黑树还会多加一个 parent 指针和颜色字段，因为旋转时要沿着节点向上调整，这正是 2.5 节说的“需要向上才加 parent”的活例子。

场景二：优先队列（堆）——数组是天作之合

第二棵树是堆（heap），也就是优先队列的经典实现。它有两个硬约束：必须是完全二叉树；父子之间必须有固定的大小关系。这两个约束恰好把数组存储的全部优点激活了：形状完整，所以没有空洞；下标公式 2i、2i+1 让父子访问都是 O(1)；插入、删除时元素只沿“根到叶子”的一条路径移动，上滤、下滤各走 O(log n) 步，数组的“搬元素”代价在这里完全可控。

反过来想，堆如果改用链式存储会怎样？首先每个节点多两个指针，空间浪费；其次节点散落内存，缓存命中率下降；最致命的是，堆的插入需要“从数组末尾上滤”，链式结构要找到“最后一个节点”必须遍历整棵树，O(n) 的代价直接毁掉 O(log n) 的复杂度承诺。所以工程上提到堆，几乎默认就是“数组 + 完全二叉树 + 下标公式”三件套。这个故事告诉我们：不是数组存不了普通树，而是普通树配不上数组的公式；完全二叉树才是数组的知己。

场景三：并查集——双亲表示法的完美主场

第三棵树藏在**并查集（union-find）**里，严格说它是一片森林：每个集合是一棵树，集合的代表是树根，元素之间的关系只有一条——“我的爸爸是谁”。并查集需要回答的问题也只有两个：某个元素属于哪个集合（沿着 parent 一路向上走到根）；合并两个集合（把一棵树的根挂到另一棵树的根下面）。全程没有任何一个操作需要“查孩子”，双亲表示法那点偏科在这里完全不是缺点，反而是优点：一个 parent 数组搞定一切，代码短、内存省、每步 O(1)。

如果给并查集换成链式存储，会发生什么？每个节点要带上孩子指针，可并查集根本不需要向下走；还要为“找根”设计父指针，等于把双亲表示法重新发明一遍，却多背了一堆用不上的字段。所以并查集的选型结论特别干脆：操作只需要向上，就只存向上的信息。这也是全篇最值得记住的选型哲学之一——别为不存在的需求付费。

场景四：DOM 与文件系统——多叉树的真实战场

第四棵树是每天都陪着你上网的DOM 树，以及你电脑里的文件系统目录树。它们的共同点是：多叉、节点数量巨大、结构动态变化、主要操作是“从上往下遍历渲染”或“按路径定位某个孩子”，偶尔还要把整棵树序列化（DOM 存成 HTML/JSON，目录树存成路径字符串）。

现代浏览器实现 DOM 时，普遍用“孩子数组”风格：每个节点保存一个孩子列表，因为 JS 代码经常要按索引取第几个子元素、对子元素排序、把某个子元素插到指定位置，孩子数组配合动态数组的随机访问最顺手。而经典的文件系统实现里，目录条目往往用“孩子链表/兄弟链”组织：一个目录指向第一个条目，条目之间用 next 指针串起来，遍历目录时沿链走一圈，节省了大量数组预留空间。至于序列化，HTML 本身就是一棵树的嵌套文本表示：开标签、子内容、闭标签，天然编码了父子关系，反序列化就是递归地解析嵌套结构。这个场景再次验证：多叉树没有唯一答案，连同一棵树的“主存储”和“序列化格式”都可以是两套方案。

走查小结

四棵树的选型走完，你会发现一个规律：树的操作方向，决定存储方案的方向。BST 向下探索，选链式；堆形状完整且要快速算位置，选数组；并查集一路向上，选双亲；DOM 多叉且要随机访问孩子，选孩子数组；文件系统多叉且要省空间，选孩子兄弟。工程里甚至还有“复合形态”：数据库的 B+ 树，页内用有序数组存键（局部），页与页之间用指针相连（全局），一套数据结构同时吃掉两种存储的红利。所谓“懂存储”，不是背下四种方案，而是面对一棵具体的树，能说出“它的操作是什么、哪种翻译方式最省”。这一章的四棵走查树，就是帮你建立这种肌肉记忆的样本。

10 本篇要点小结

动笔之前，先把本篇的七颗钉子钉牢：

第一，存储的本质是翻译。树是二维的层次结构，内存是一维的线性街道；把所有存储方案放在一起看，它们做的事情完全相同——把“谁是爸爸、谁的孩子”翻译成位置信息。翻译工具有两种：指针（直接给出地址）和下标（用公式算出位置）。

第二，链式存储最通用。二叉链表节点就是“值 + 左指针 + 右指针”，结构直观、动态性好、插入删除快；但节点散落内存、缓存不友好，而且默认只有“向下”的信息，查父亲要么全树搜索，要么花空间加 parent 指针。

第三，数组存储最依赖形状。完全二叉树 1 基下标满足左孩子 2i、右孩子 2i+1、父亲向下取整 i/2；编号连续、零空洞，所以堆和线段树放心大胆地住在数组里。普通二叉树编号跳号，右斜链 n 个节点需要指数级的数组长度，这是数组存储的致命伤。

第四，双亲表示法最偏科。parent 数组只记“爸爸是谁”，查父亲 O(1)、向上追溯 O(1) 每步，但查孩子要扫描全表 O(n)；它依赖稳定编号，动态性差，最经典的用武之地是并查集。

第五，孩子兄弟表示法让多叉树“变二叉”。左指针指向第一个孩子，右指针指向下一个兄弟，任意多叉树都能被唯一编码成二叉树；节点固定两个指针，空间线性，还能复用二叉树算法，代价是找第 k 个孩子要沿兄弟链走 O(k) 步。

第六，序列化是存储的“出口”。指针是临时地址，不能落盘；必须用遍历确定记录顺序，用嵌套或空标记表达结构，才能无歧义地保存和重建一棵树。数组和双亲表示法天然好序列化，链式树则把希望寄托在遍历算法上——这正是第 5、6 篇的舞台。

第七，选择方案先问操作。多叉选孩子兄弟/孩子数组，形状整齐选数组，频繁向上选双亲，通用动态场景选链式，必要时混合：链式加 parent、数组加双亲辅助表。没有银弹，只有匹配。

11 术语小词典

把本篇出现过的关键术语集中收进一个小词典，方便你复习时快速查词。每个词条都给一句“人话版”解释，够用就好。

地址（address）：内存单元的“门牌号”，程序通过地址找到数据。指针保存的就是地址，所以指针能“指路”。

指针（pointer）：一个变量，它的值是另一个内存位置的地址。在树里，left、right、parent、firstChild、nextSibling 都是指针。

二叉链表（binary linked list）：用“值 + 左孩子指针 + 右孩子指针”存储二叉树节点的方案，是链式存储的标准形态。

顺序存储（sequential storage）：把节点放进数组，用下标公式表达父子关系的方案，只对完全二叉树友好。

完全二叉树（complete binary tree）：除最后一层外每层都满，最后一层从左到右连续排列的二叉树，编号连续，是数组存储的理想住户。

空洞（hole）：数组存储中留给“不存在的位置”的空格子。普通二叉树编号跳号产生空洞，右斜链会让空洞数爆炸。

双亲表示法（parent representation）：只记录每个节点的父亲编号（或指针）的方案，查父亲 O(1)，查孩子要扫描全表。

孩子兄弟表示法（child-sibling representation）：左指针指向第一个孩子、右指针指向下一个兄弟的方案，能把任意多叉树编码成二叉树。

兄弟链（sibling chain）：孩子兄弟表示法中，用右指针把同一父亲的孩子们串起来的链表，找第 k 个孩子要沿链走 k-1 步。

父指针（parent pointer）：链式节点中额外增加的回程指针，用空间换 O(1) 查父亲，红黑树、需要频繁向上的结构常带它。

序列化（serialization）：把内存中的结构翻译成可落盘的字节/文本，树序列化的关键是确定节点记录顺序并表达空位置。

反序列化（deserialization）：从字节/文本重建内存结构的过程，必须和序列化使用同一套规则，否则重建出的树会“变形”。

堆（heap）：完全二叉树 + 父子大小规则 + 数组存储的三合一结构，优先队列的经典实现，树系列第 16 篇的主角。

并查集（union-find）：用 parent 数组维护若干集合的算法结构，find 向上找根、union 改根，是双亲表示法最著名的应用。

O(1) 与 O(n)：算法复杂度的记法。O(1) 表示“常数步搞定，和数据量无关”；O(n) 表示“要遍历所有 n 个元素”。本篇文章用它们衡量不同操作的价格。

O(log n)：对数复杂度，意思是“数据量翻一倍，步数只加一”。树的高度大致是 log n，所以堆、二叉搜索树的核心操作都宣称自己是 O(log n)。

深度、层与高度（depth, level, height）：描述节点位置的三个词，第 2 篇约定根在第 1 层、深度为 0；本篇提到完全二叉树的高度公式时，用的就是这套约定。

子树（subtree）：一个节点连同它的全部后代构成的树。树的递归定义、递归遍历、递归序列化全都建立在子树上。

前序遍历（preorder traversal）：先访问根，再访问左子树，最后访问右子树的遍历方式，是第 5 篇的主角之一，也是序列化时最常用的记录顺序。

中序遍历（inorder traversal）：先访问左子树，再访问根，最后访问右子树。二叉搜索树按中序输出会得到一个有序序列。

后序遍历（postorder traversal）：先访问左子树，再访问右子树，最后访问根。删除整棵树、计算表达式树的值，都常用后序。

层序遍历（level-order traversal）：从上到下、从左到右一层一层地访问节点，是第 6 篇的主角；在数组存储里，它几乎等于按下标从小到大依次访问。

内存碎片（memory fragmentation）：动态分配导致空闲内存被切成许多小块、节点之间隔着他物的现象。链式树容易产生碎片，也是缓存不友好的根源。

递归（recursion）：函数在处理问题时调用自身，树的递归定义让遍历、建树、序列化都能用递归写得极短；下一篇会大量使用。

这份词典不需要背，读到不认识的词回来翻一翻即可。术语熟悉之后，下一篇讲遍历时，你会发现自己已经能看懂大半行话。

12 自测题（附答案）

13 下一篇预告

下一篇是《树系列第 5 篇：深度优先遍历》。我们已经知道树在内存里怎么放，接下来要回答一个更实际的问题：怎么把一棵树完整地走一遍？第 5 篇的主角是深度优先遍历的三兄弟——前序遍历、中序遍历、后序遍历。你会看到，它们只是“访问根、访问左子树、访问右子树”这三句话换顺序；你还会看到，递归写法为什么天然适配树，非递归写法又怎么用栈模拟系统调用，以及“遍历顺序”如何成为序列化与重建树的地基。

更妙的是，本篇讲过的存储知识会在第 5 篇全面“返场”：链式树沿着 left、right 指针走，数组树沿着 2i、2i+1 下标走，孩子兄弟树则按“先左孩子、再右兄弟”的顺序走——同样是深度优先，三种存储写出了三种风味。第 6 篇再讲广度优先遍历（层序遍历），到那时，“一棵树从怎么存、到怎么走、再到怎么落盘”的完整闭环就打通了。建议你在读第 5 篇之前，先亲手用代码实现一个链式二叉树的节点，把本篇的例子敲一遍，让“指针指路”的感觉落在指尖上。

14 写在最后

到这里，“树系列”已经走完四篇：第 1 篇回答“为什么要树”，第 2 篇回答“树由什么组成”，第 3 篇回答“为什么二叉树受宠”，第 4 篇回答“树在内存里怎么放”。如果把整棵“树系列”比作一棵树，前四篇就是它的根：后面即将登场的二叉搜索树、平衡树、堆、字典树、B 树、线段树，全都长在这套“节点 + 关系”的存储地基上。地基打不牢，后面的楼盖得再漂亮也会晃。

读这一篇时，你不需要一次记住所有细节，但请务必带走三个画面：第一，指针指路的画面——链式树是一张由地址织成的网，节点散落内存，关系全靠指针维系；第二，下标算路的画面——完全二叉树住进数组，左孩子 2i、右孩子 2i+1、父亲 i/2，一道算术题代替了所有指针；第三，只记爸爸的画面——双亲表示法用一行数组回答“我从哪里来”，把“向下”的信息彻底让渡出去。这三幅画面，会在后面几十篇里反复以各种变体出现。

如果你今天只有十分钟动手时间，我建议做三件小事：第一，用 TypeScript 建一棵 7 节点的链式二叉树，并打印每个节点的左右孩子；第二，把同一棵树按 1 基下标写进数组，用公式验证每个节点的父子关系；第三，把 parent 数组 [-1, 0, 0, 1, 1, 2] 画回一棵树，看看自己的还原是否和原树一致。三件事做完，本篇的四种方案至少有三种会长在你的肌肉记忆里。至于孩子兄弟表示法，等你真正需要处理一棵多叉树时，再回来翻这一篇也不迟——知道“有这样的招数”，比背下全部细节更重要。

下一篇，《树系列第 5 篇：深度优先遍历》，我们让树真正“走起来”。第 5 篇见。