1. 为什么二叉树的存储结构值得单独琢磨很多同学学二叉树上来就背定义、画图、遍历一到写代码就卡壳。尤其是期末复习或者准备考研数据结构的时候翻到“二叉树的存储结构”这一节感觉不就是数组和链表吗有什么好讲的但实际一做题、一写程序就露馅顺序存储什么时候能用、什么时候不能用链式存储的指针到底该怎么指为什么我写的二叉树程序总是报运行时错误这些问题的根子全都埋在对存储结构的理解上。先明确一个概念二叉树本身是一种逻辑结构它描述的是结点之间一对二的层次关系。但计算机内存是一维的怎么把这种二维的层次关系“摆放”进去就是存储结构要解决的事。换句话说存储结构是逻辑结构在内存里的物理实现同一棵二叉树用不同的存储方式写出来的增删改查代码天差地别。这篇文章我打算从“为什么”的角度把顺序存储和链式存储掰开揉碎讲透再加上我这些年写二叉树程序攒下的踩坑经验。不管是数据结构初学者、期末冲刺选手还是准备408考试的同学看完应该都能对二叉树存储有一个立体的认识不再是一个模模糊糊的概念。2. 顺序存储结构用数组怎么装下一棵树2.1 核心思路完全二叉树的编号规则顺序存储的思想非常朴素给二叉树的结点按从上到下、从左到右排好序号然后把这个序号当作数组下标把结点值存进数组对应位置。这里的关键在于编号规则。设想一棵满二叉树根结点编号为1它的左孩子编号为2、右孩子编号为3编号为2的结点的左孩子是4、右孩子是5编号为3的结点的左孩子是6、右孩子是7……以此类推。你很快会发现一个规律对于编号为 i 的结点其左孩子编号为 2i右孩子编号为 2i1双亲编号为 2i。这个规律是整个顺序存储的基石。正因为结点序号和它在树中的位置存在这种一一对应的数学关系我们才能用数组下标直接推算出某个结点的左右孩子和父结点不需要额外存任何指针信息。这里要注意一个细节数组下标从0开始还是从1开始。如果从下标0开始存根结点那么编号公式就要调整左孩子是 2i1右孩子是 2i2双亲是 (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个结点的二叉链表一共有多少个空指针域答案是 n1 个。推导过程是每个结点有2个指针域共 2n 个n个结点的二叉树有 n-1 条边每条边对应一个非空指针所以空指针域 2n - (n-1) n1。这个结论在线索二叉树那一章特别重要因为线索化就是把这些空指针利用起来指向前驱和后继结点。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 一张表看透各自优劣我经常跟学生说存储结构的选择没有绝对的对错关键看你的应用场景。先看一张对比表对比维度顺序存储链式存储适用树形完全二叉树、满二叉树任意形态二叉树空间利用率非完全二叉树时浪费严重结点内存利用率高单结点指针开销固定访问双亲/孩子通过下标公式 O(1) 定位找孩子 O(1)找双亲需遍历或额外指针插入/删除可能涉及大量元素移动只改指针O(1) 完成连接更新内存管理静态数组需要预知最大结点数动态分配按需生长典型应用堆、优先队列、完全二叉树普通二叉搜索树、AVL树、表达式树这个表不是让你背而是帮你建立“先看树的形态再定存储方案”的思维模式。如果一棵树是完全二叉树或者接近完全比如堆那就用顺序存储省指针、省代码如果树的形态千奇百怪比如二叉搜索树插入删除频繁、树高动态变化那就必须链式存储。4.2 一个“烂树”的例子最能说明问题我上课的时候喜欢拿一个极端例子讲一棵深度为4、但每个结点只有右孩子的“右斜树”。用顺序存储存储它需要 2^4-115 个数组位置但树里其实只有4个结点数组里11个位置全是空。用链式存储呢只有4个结点加4个右指针干净利落。反过来一棵15个结点的完全二叉树用顺序存储只需要15个数组位置且所有结点下标连续用链式存储需要15个结点每个结点还要存两个指针假设int占4字节、指针占8字节那就是15×4 15×16 300字节而顺序存储只要15×460字节。差距一目了然。所以选型其实就一句话先判断树是不是完全二叉树是就考虑顺序不是就默认链式。这句“默认链式”不是偷懒而是链式存储的通用性强代码写起来思维负担小。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 和 2i1。写完这个你对两者的理解才算打通。6.3 一道好用的自测题超市货架想象法我想借热搜里的“超市货架 遍历二叉树”这个奇怪组合送你一个生活化的思考方式想象一棵二叉树是一个超市仓库的货架规划图。每个货架位置是一个结点根结点是仓库入口左货道和右货道分别通向两个子区域。如果采用顺序存储你把每个货位编号货位号满足“左子货位号是父货位号的2倍、右子货位号是2倍加1”那么只要知道入口货位号你就能精确找到任何一个区域放什么货。问题是如果你在某条货道中间空了一些货位后续编号全被迫跳号仓库利用率就下降了。如果采用链式存储每个货位立着一个标签写明“本货位放着货物X往左走通向货位Y往右走通向货位Z”新开一个货位只需要改一下标签的指向就行。你拉着一辆小车按标签逛仓库就是一次遍历。想象一下如果标签帮你标好了“中序遍历顺序是先左、再自己、后右”你逛一圈出来正好是把货品按某个规则排好的顺序。这种想象法虽然简单但能把存储结构从“代码概念”变成“空间布局问题”我个人觉得特别适合考前快速理清思路。7. 从存储结构看更大的数据结构版图二叉树的存储结构不是孤立知识点它是理解整个树形结构家族的一把钥匙。理解了“数组下标代表关系”和“指针指向代表关系”这两种思路你再去看堆、并查集、平衡树、B树、Trie树会发现它们本质上都在回答同一个问题关系用什么方式存堆就是顺序存储的完全二叉树所有关于堆的操作都依赖下标公式并查集用数组存父结点下标其实就是一种退化成只有父指针的静态三叉链表的变体B树和Trie树则完全是动态指针的世界结点数量不可预知、树形动态变化只有链式存储才扛得住。我还想强调一个容易被忽视的关联——线索二叉树。它解决的问题是“二叉链表里 n1 个空指针被浪费了”于是把空指针改成指向前驱和后继让遍历不需要栈。想学懂线索二叉树前提就是你得彻底搞懂二叉链表的结构和空指针域的分布。我在前面强调的 n1 个空指针的推导到了线索化那章会直接派上用场。从考研408的角度看二叉树存储结构的选择题一般会混合“完全二叉树判断”“数组下标推算”“空指针数量计算”“三叉链表结点数计算”这几种考法。平时做题如果这些类型都见过考试就没什么好慌的。从实际工程的角度看你写一个文件系统目录树结点是目录和文件子目录数量不固定几乎必然选择孩子兄弟表示法——它本质也是链式存储的变形把多叉树用二叉链表表达。这也是为什么二叉树的链式存储是“万能胶”学会了它多叉树你也能用指针玩出花来。所以我常说一句话二叉树存储结构不值得背值得“玩”。玩的方式就是拿不同的树用两种方式各存一遍再把它们互相转换最后用不同方式去遍历。这个过程跑通一遍你对数据结构的理解会往上跳一个台阶。如果让我提一个最容易上手的实践建议找个晚上手写一棵5结点完全二叉树先用数组存、写前序遍历再改成链表存、写中序遍历最后写一个“数组转链表”的函数。这半小时的练习可能比看两小时参考书都管用。