二叉树存储结构详解：顺序存储与链式存储选型及遍历实践

1. 为什么二叉树的存储结构值得单独琢磨

很多同学学二叉树，上来就背定义、画图、遍历，一到写代码就卡壳。尤其是期末复习或者准备考研数据结构的时候，翻到“二叉树的存储结构”这一节，感觉不就是数组和链表吗，有什么好讲的？但实际一做题、一写程序就露馅：顺序存储什么时候能用、什么时候不能用？链式存储的指针到底该怎么指？为什么我写的二叉树程序总是报运行时错误？这些问题的根子，全都埋在对存储结构的理解上。

先明确一个概念：二叉树本身是一种逻辑结构，它描述的是结点之间一对二的层次关系。但计算机内存是一维的，怎么把这种二维的层次关系“摆放”进去，就是存储结构要解决的事。换句话说，存储结构是逻辑结构在内存里的物理实现，同一棵二叉树，用不同的存储方式，写出来的增删改查代码天差地别。

这篇文章我打算从“为什么”的角度，把顺序存储和链式存储掰开揉碎讲透，再加上我这些年写二叉树程序攒下的踩坑经验。不管是数据结构初学者、期末冲刺选手，还是准备408考试的同学，看完应该都能对二叉树存储有一个立体的认识，不再是一个模模糊糊的概念。

2. 顺序存储结构：用数组怎么装下一棵树

2.1 核心思路：完全二叉树的编号规则

顺序存储的思想非常朴素：给二叉树的结点按从上到下、从左到右排好序号，然后把这个序号当作数组下标，把结点值存进数组对应位置。

这里的关键在于编号规则。设想一棵满二叉树，根结点编号为1，它的左孩子编号为2、右孩子编号为3；编号为2的结点的左孩子是4、右孩子是5；编号为3的结点的左孩子是6、右孩子是7……以此类推。你很快会发现一个规律：

对于编号为 i 的结点，其左孩子编号为 2i，右孩子编号为 2i+1，双亲编号为 2i。

这个规律是整个顺序存储的基石。正因为结点序号和它在树中的位置存在这种一一对应的数学关系，我们才能用数组下标直接推算出某个结点的左右孩子和父结点，不需要额外存任何指针信息。

这里要注意一个细节：数组下标从0开始还是从1开始。如果从下标0开始存根结点，那么编号公式就要调整：左孩子是 2i+1，右孩子是 2i+2，双亲是 (i-1)/2。很多教材默认从1开始，是因为公式更整洁好记；但C语言的数组默认从0开始，所以实际写代码时我会习惯把数组的第0个位置空出来不用，这样下标就能和编号直接对应，省得换算出错。

2.2 为什么说顺序存储“挑树”——不能浪费空闲位置

顺序存储有一个绕不开的毛病：它假设这棵树是“紧凑”的。如果一棵树不是完全二叉树，比如根结点只有右孩子、没有左孩子，那编号为2的位置就得空着。如果这个右孩子又只有右孩子，那编号为3的位置也空着，继续往下编号到5、到11……你会发现，一棵深度很大的“斜树”，数组里大部分空间都是空的。

这就是典型的空间浪费。我在实际处理中估算过：一棵深度为k的单支二叉树，用顺序存储需要准备 2^k-1 个结点空间，但实际只用了 k 个，利用率是 k/(2^k-1)，k越大浪费越离谱。所以顺序存储只适合完全二叉树或者接近完全的二叉树——比如堆排序里用到的最大堆、最小堆，它们天然是完全二叉树，顺序存储就是最合适的方案。

但这不代表顺序存储的学习价值低。你去看考研408的真题，经常给一棵完全二叉树的数组存储结果，让你画出树形结构、写出某个结点的双亲和左右孩子下标。这种题考的就是你对编号规则的熟练度。我建议你亲自拿纸笔画一棵7个结点的完全二叉树，把每个结点的编号标出来，再把数组下标对应上去，画一遍就记住了。

2.3 顺序存储的代码骨架：定位和遍历

下面给一个最简C语言实现，展示怎么用数组存一棵完全二叉树，并且通过下标计算完成遍历。代码不复杂，重点是体会“下标即关系”的感觉。

#include <stdio.h> #include <stdlib.h> #define MAXSIZE 100 // 用数组存储完全二叉树，下标从1开始，[0]留空 int tree[MAXSIZE]; int size = 0; // 实际结点个数 // 添加结点（按层次顺序依次添加，保证完全二叉树性质） void insert(int value) { if (size >= MAXSIZE - 1) { printf("树已满\n"); return; } tree[++size] = value; } // 前序遍历：根 -> 左 -> 右 void preorder(int index) { if (index > size) return; // 超过实际结点范围，递归终止 printf("%d ", tree[index]); preorder(2 * index); // 左孩子 preorder(2 * index + 1); // 右孩子 } int main() { // 依次插入结点：1为根，2、3为左右孩子，4、5是2的孩子 for (int i = 1; i <= 5; i++) insert(i); printf("前序遍历: "); preorder(1); printf("\n"); return 0; }

运行结果是：

前序遍历: 1 2 4 5 3

注意看递归里的终止条件index > size，这个是关键。因为数组里可能有空闲位置，必须靠这个条件判断“当前下标是不是超出了树的实际边界”。我在初学的时候经常忘记加这个判断，结果越界访问，轻则读到垃圾值，重则段错误。

3. 链式存储结构：指针的世界更灵活

3.1 二叉链表：每个结点带两个指针

链式存储的思路更直观：每个结点不仅存数据，还存指向左右孩子的指针。因为二叉树每个结点最多两个分支，所以这种结构叫二叉链表。结点的C语言定义长这样：

typedef struct BiTNode { int data; // 数据域 struct BiTNode *lchild, *rchild; // 左右孩子指针 } BiTNode, *BiTree;

申请一个结点、把数据填进去、把两个指针指好，就能像搭积木一样把一棵树搭起来。和顺序存储相比，链式存储最大的优势是不浪费空间：一棵n个结点的二叉树，只需要n个结点的空间，再加上每个结点两个指针的开销。它不要求树长得“紧凑”，任意形态的二叉树都可以直接用链式表示。

这里有一个非常经典的考点：n个结点的二叉链表一共有多少个空指针域？答案是 n+1 个。推导过程是：每个结点有2个指针域，共 2n 个；n个结点的二叉树有 n-1 条边，每条边对应一个非空指针，所以空指针域 = 2n - (n-1) = n+1。这个结论在线索二叉树那一章特别重要，因为线索化就是把这些空指针利用起来，指向前驱和后继结点。

3.2 三叉链表：加一个父指针

二叉链表能轻松找到孩子，但想找“父结点”就得从根开始遍历，复杂度很高。所以有时候我们会给每个结点多加一个parent指针，变成三叉链表：

typedef struct BiTNode3 { int data; struct BiTNode3 *lchild, *rchild; struct BiTNode3 *parent; // 指向双亲 } BiTNode3, *BiTree3;

多一个指针的好处是，某些需要回溯的操作会方便很多。典型场景是非递归遍历算法：比如非递归中序遍历，当你访问完左子树的最深结点后，需要回到父结点，有 parent 指针就能直接回溯，不用维护额外的栈结构。

代价是每个结点多占用一个指针的内存，而且建树的时候要多一步：创建子结点时，把子结点的 parent 指向当前结点。别小看这一步，漏了它，后面所有基于 parent 的算法都会出问题。我在带学生做实验时，最常见的bug之一就是“parent指针没赋值，结果回溯时拿到的是NULL”。所以用三叉链表之前，先想清楚你是否真的需要频繁回溯，如果只是普通遍历，二叉链表加栈也完全够用。

3.3 动态建树：递归式构造的真实过程

链式存储的建树方式有很多种，最常用的是递归构造——按照某种遍历顺序（通常是前序）建立结点之间的父子关系。我以一个“输入前序序列，空结点用#表示”的方式建树为例：

#include <stdio.h> #include <stdlib.h> typedef struct BiTNode { char data; struct BiTNode *lchild, *rchild; } BiTNode, *BiTree; // 按前序序列建树，'#'表示空结点 // 输入示例: AB#C##D## void createBiTree(BiTree *T) { char ch; scanf(" %c", &ch); // 注意前面加空格，跳过换行符 if (ch == '#') { *T = NULL; // 空结点，指针置空 } else { *T = (BiTNode *)malloc(sizeof(BiTNode)); (*T)->data = ch; createBiTree(&(*T)->lchild); // 递归建左子树 createBiTree(&(*T)->rchild); // 递归建右子树 } }

这里有两个治我多年的细节。第一是scanf(" %c", &ch)那个空格，不加的话，上一次输入留下的换行符会被当做一个有效字符读进去，导致建树莫名其妙多出空结点。第二是函数参数用BiTree *T，也就是二级指针，因为建树过程中要给T本身赋值（分配内存或置空），用一级指针的话，函数内部修改不会生效，只会改到形参副本。很多初学者写二叉树程序报错，根子就在这里。

4. 两种存储结构的选型判断

4.1 一张表看透各自优劣

我经常跟学生说，存储结构的选择没有绝对的对错，关键看你的应用场景。先看一张对比表：

这个表不是让你背，而是帮你建立“先看树的形态，再定存储方案”的思维模式。如果一棵树是完全二叉树或者接近完全，比如堆，那就用顺序存储，省指针、省代码；如果树的形态千奇百怪，比如二叉搜索树，插入删除频繁、树高动态变化，那就必须链式存储。

4.2 一个“烂树”的例子最能说明问题

我上课的时候喜欢拿一个极端例子讲：一棵深度为4、但每个结点只有右孩子的“右斜树”。用顺序存储存储它，需要 2^4-1=15 个数组位置，但树里其实只有4个结点，数组里11个位置全是空。用链式存储呢，只有4个结点加4个右指针，干净利落。

反过来，一棵15个结点的完全二叉树，用顺序存储只需要15个数组位置，且所有结点下标连续；用链式存储需要15个结点，每个结点还要存两个指针，假设int占4字节、指针占8字节，那就是15×4 + 15×16 = 300字节，而顺序存储只要15×4=60字节。差距一目了然。

所以选型其实就一句话：先判断树是不是完全二叉树，是就考虑顺序，不是就默认链式。这句“默认链式”不是偷懒，而是链式存储的通用性强，代码写起来思维负担小。

4.3 考研和面试里怎么快速判断

如果你是奔着考试去的，这类题目通常有两种出法。一种是给你一棵树的数组存储结果，要求你还原树的形状、判断是不是完全二叉树。做法就是先把数组画成“编号位置图”，空位置画成方框，然后看空位置是不是都集中在最后一段——只要某个空位置后面还有非空结点，就说明不是完全二叉树。

另一种是给你树形图，让你写它的顺序存储数组。这种题要先给结点按层次编号，再把编号映射到数组下标，空着的位置补充特殊标记，一般是0或者#。我强烈建议你做题时不要跳步，老老实实画编号，不然下标算错一道题就白干了。

除了考试，这事在工程里也有价值。比如你要实现一个内存池化的二叉堆，顺序存储配合数组的局部性原理，缓存命中率比链表高不少；而你要做一棵带大量旋转操作的平衡树，链式存储里旋转就是改几个指针，用顺序存储的数组搬元素绝对让人崩溃。

5. 基于存储结构的遍历实操

5.1 从链式存储出发写三种深搜遍历

存储结构定了，遍历算法才谈得上实现。链式存储的遍历是递归的天下，因为树本身就是递归定义的结构。前序、中序、后序三种遍历的区别，仅仅在于访问根结点的时机：

• 前序：先访问根，再遍历左子树，最后遍历右子树
• 中序：先遍历左子树，再访问根，最后遍历右子树
• 后序：先遍历左子树，再遍历右子树，最后访问根

看起来只是三行代码位置互换，但访问顺序完全不同。以中序为例，在一棵二叉搜索树里做中序遍历，输出是升序序列，这个性质可以直接用来验证BST是否构建正确。

void inorder(BiTree T) { if (T == NULL) return; inorder(T->lchild); printf("%c ", T->data); inorder(T->rchild); }

就这么简单。但很多初学者会问：这样递归下去，栈会不会爆？答案是：会，当树长成一条链表状且深度很大时，递归深度就是树的结点数，程序确实可能栈溢出。这也是为什么工程里要写非递归版本，用显式的栈来模拟递归过程，把系统栈的深度限制转换成堆内存的自己分配。

5.2 非递归遍历：显式栈把递归变成循环

以中序遍历为例，非递归实现的思路是：先把左子树一路压栈，压到头之后弹栈访问，再转向右子树继续这个过程。

#include <stdio.h> #include <stdlib.h> #define MAXSTACK 100 typedef struct BiTNode { char data; struct BiTNode *lchild, *rchild; } BiTNode, *BiTree; // 非递归中序遍历 void inorderNonRecursive(BiTree T) { BiTree stack[MAXSTACK]; int top = -1; BiTree p = T; while (p != NULL || top != -1) { // 一路向左，把路径上的结点压栈 while (p != NULL) { stack[++top] = p; p = p->lchild; } // 弹栈访问 if (top != -1) { p = stack[top--]; printf("%c ", p->data); p = p->rchild; // 转向右子树 } } }

这段代码我写得比较直白，用数组模拟栈而不是C标准库的stack，主要是不想引入额外依赖，也方便初学者看到栈的每一个动作。如果你在代码里用while(1)想当然地写内部循环，很容易陷入死循环；核心是理解p指针的走向：它要么从父结点下来去左孩子，要么从左子树的最深处往上回溯。这个过程想通了，非递归遍历就通关了。

5.3 顺序存储遍历的本质：下标走位

如果底层是顺序存储，遍历的写法就完全不同了，不再有“指针往下指”的概念，而是用下标公式推算下一站。以前序遍历为例，访问完下标i的结点之后，如果有左孩子（下标 2i 在合法范围内），就跳到左孩子；左孩子走完了再回退到最近的、还没访问过右孩子的祖先结点，去它的右孩子。因为回退需要记录路径，所以顺序存储的前序遍历也离不开栈。

我发现很多参考书喜欢直接抛递归代码，导致学生觉得顺序存储的遍历“也就是这样啊”。但真正手写的时候，最容易出的问题反而是**“递归深度和数组边界”**。递归版本里，preorder(2*index)直接算下标，如果你用一个距离很远的合法 index 去递归，可能瞬间算出远超数组范围的下标，但递归函数内部又没法确认“这个位置真的有用”，只能靠提前判断if (index > size) return;。我建议写顺序存储遍历时，不管递归还是非递归，第一件事就是明确数组的实际有效长度size，所有下标运算都要跟它比较，没有例外。

6. 常见问题与排查技巧实录

6.1 为什么我的二叉树程序总是报运行时错误

这个问题在热词里反复出现，确实太典型了。我总结了一下，大概率出在这几类原因里：

第一类是野指针。建树时申请了结点，但左右指针没初始化。malloc出的内存是脏的，不会自动清零，必须手动赋值。我见过有人写T->lchild = NULL; T->rchild = NULL;只是其中一遍，漏了另一边，遍历的时候一访问就Segmentation Fault。

第二类是递归出口缺失。递归遍历里忘写if (T == NULL) return;，或者写成了if (T != NULL)但循环逻辑不收敛。递归会一直调用到系统栈崩溃，报错信息往往是stack overflow或者直接闪退。

第三类是二级指针传参错误。建树函数里用的是BiTree *T，但调用时却传了createBiTree(T)而不是createBiTree(&T)，函数内部的分配结果全部丢失。这种情况程序运行特别诡异，有时候能建出半个树，有时候直接崩溃，特别难排查。

第四类是scanf输入格式不匹配。前面提到的scanf(" %c")少了空格，读进了残留的换行符；或者输入序列本身长度和树的结点数不匹配，凑巧能跑通，换个数据就出事。

遇到这些报错，我的排查习惯是：先加printf打印每一步的结点地址和值，从根开始一层层验证，确认“到底哪一步开始出现NULL或垃圾数据”。这个土办法比盯着代码空想有效一百倍。

6.2 选择存储结构时的三个隐藏坑

第一个坑是盲目追求链式的灵活性。有些人觉得链表听起来高级，把所有二叉树都存成链式，完全不顾树的形态。比如用数组存堆明明是教科书最优解，非得用链式实现堆排序，代码写得又长又容易错，完全没必要。

第二个坑是忽略指针本身的内存开销。链式存储虽然不浪费空位置，但每个结点两个指针本身就占固定成本。如果你要存储的海量数据本身很小（比如一个char型值），链式存储的指针开销是数据的数倍，这时候反而要考虑用数组下标代替指针的静态二叉链表——用数组存父子下标关系，兼顾灵活性和内存效率。

第三个坑是不清楚“存储结构”和“遍历算法”的耦合关系。很多人背了递归遍历代码，但不知道这段代码是建立在链式存储的指针跳转上的。一旦面试官让你把一棵树从顺序存储转成链式存储，或者反过来，就完全傻眼。我建议你亲手写一下“数组表示转二叉链表”的递归函数：把 index 为 i 的数组元素转换成值为 tree[i] 的新结点，并递归转换 2i 和 2i+1。写完这个，你对两者的理解才算打通。

6.3 一道好用的自测题：超市货架想象法

我想借热搜里的“超市货架 遍历二叉树”这个奇怪组合，送你一个生活化的思考方式：想象一棵二叉树是一个超市仓库的货架规划图。每个货架位置是一个结点，根结点是仓库入口，左货道和右货道分别通向两个子区域。

如果采用顺序存储，你把每个货位编号，货位号满足“左子货位号是父货位号的2倍、右子货位号是2倍加1”，那么只要知道入口货位号，你就能精确找到任何一个区域放什么货。问题是如果你在某条货道中间空了一些货位，后续编号全被迫跳号，仓库利用率就下降了。

如果采用链式存储，每个货位立着一个标签，写明“本货位放着货物X，往左走通向货位Y，往右走通向货位Z”，新开一个货位只需要改一下标签的指向就行。你拉着一辆小车按标签逛仓库，就是一次遍历。想象一下，如果标签帮你标好了“中序遍历顺序是：先左、再自己、后右”，你逛一圈出来正好是把货品按某个规则排好的顺序。

这种想象法虽然简单，但能把存储结构从“代码概念”变成“空间布局问题”，我个人觉得特别适合考前快速理清思路。

7. 从存储结构看更大的数据结构版图

二叉树的存储结构不是孤立知识点，它是理解整个树形结构家族的一把钥匙。理解了“数组下标代表关系”和“指针指向代表关系”这两种思路，你再去看堆、并查集、平衡树、B树、Trie树，会发现它们本质上都在回答同一个问题：关系用什么方式存？

堆就是顺序存储的完全二叉树，所有关于堆的操作都依赖下标公式；并查集用数组存父结点下标，其实就是一种退化成只有父指针的静态三叉链表的变体；B树和Trie树则完全是动态指针的世界，结点数量不可预知、树形动态变化，只有链式存储才扛得住。

我还想强调一个容易被忽视的关联——线索二叉树。它解决的问题是“二叉链表里 n+1 个空指针被浪费了”，于是把空指针改成指向前驱和后继，让遍历不需要栈。想学懂线索二叉树，前提就是你得彻底搞懂二叉链表的结构和空指针域的分布。我在前面强调的 n+1 个空指针的推导，到了线索化那章会直接派上用场。

从考研408的角度看，二叉树存储结构的选择题一般会混合“完全二叉树判断”“数组下标推算”“空指针数量计算”“三叉链表结点数计算”这几种考法。平时做题如果这些类型都见过，考试就没什么好慌的。

从实际工程的角度看，你写一个文件系统目录树，结点是目录和文件，子目录数量不固定，几乎必然选择孩子兄弟表示法——它本质也是链式存储的变形，把多叉树用二叉链表表达。这也是为什么二叉树的链式存储是“万能胶”，学会了它，多叉树你也能用指针玩出花来。

所以我常说一句话：二叉树存储结构不值得背，值得“玩”。玩的方式就是拿不同的树，用两种方式各存一遍，再把它们互相转换，最后用不同方式去遍历。这个过程跑通一遍，你对数据结构的理解会往上跳一个台阶。

如果让我提一个最容易上手的实践建议：找个晚上，手写一棵5结点完全二叉树，先用数组存、写前序遍历，再改成链表存、写中序遍历，最后写一个“数组转链表”的函数。这半小时的练习，可能比看两小时参考书都管用。