数据结构树全解析：从二叉树遍历到红黑树与B+树

学数据结构的时候，树这一章往往是很多人第一次意识到“代码还能这么玩”的地方。链表再怎么折腾也就是一条线，但树不一样，它有了分支，有了层级，有了递归的用武之地。无论你是在准备考研、期末复习，还是刷LeetCode遇到二叉树的题一头雾水，又或者工作中突然要处理B+树索引、哈夫曼编码这类应用，你会发现所有人都会告诉你：把树搞懂，数据结构就通了一半。

这篇东西我打算换个讲法，不按教材目录平铺直叙，而是从一个动手写过树、也被树的各种变体折磨过的人的角度，把“树”这个主题彻底拆开。从基础概念、存储设计，到四种遍历的递归与非递归实现，再到AVL、红黑树、B+树这些进阶变体，最后落到真实工程场景和面试考点上。内容会有点长，但每一段都是能直接上手的干货，建议有基础的读者直接从第3章开始看，新手则老老实实按顺序读。

1. 树的基本概念与存储设计

1.1 节点、边与层级：构建树的基础词汇

树是n个节点的有限集合，它最大的特点就是“一对多”的关系。你可以把树想象成一个公司的组织架构：CEO是根节点，下面分技术部、市场部、运营部，每个部门又有自己的小组，组长再带普通员工。这种结构天然适合表达父子关系、层级关系和归属关系。

这里有几个术语我建议背得滚瓜烂熟，因为后文所有内容都建立在这套词汇上：

• 根节点：整棵树最顶层的节点，一棵树只有一个根。根没有父节点。
• 叶子节点：度为0的节点，也就是没有孩子的节点，相当于组织架构里的普通员工。
• 内部节点：既不是根也不是叶子的节点，有父也有子。
• 节点的度：该节点拥有的子树个数，也就是直接子节点的数量。
• 树的度：所有节点中最大的度。度为2的树就是二叉树，度为3就是三叉树，以此类推。
• 树的深度（高度）：从根到最远叶子节点的边数。这里有个小坑，不同教材对深度和高度的定义略有差异，有的从0开始数，有的从1开始数，做题前先确认题目约定。

举个例子，下面这段代码定义了一个最简单的二叉树节点结构：

typedef struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; } TreeNode;

这个结构体看起来简单，但它是整棵树的基石。left和right两个指针，一个指向左子树根节点，一个指向右子树根节点，通过递归引用，就能表达任意复杂的树形结构。学习树的第一课，就是先把这种“节点自我嵌套”的思维建立起来。不要把节点看作孤立的元素，而要看作一个子树的根，它统治着它下面的整个层级。

1.2 存储结构怎么选：双亲、孩子还是孩子兄弟

实际写代码的时候，我们90%的情况用的都是二叉树节点结构（left/right指针），因为任何树都能通过“孩子兄弟表示法”转换成二叉树。但教材里还会讲另外两种存储方式，考试可能会考，这里也一并说清楚。

第一种：双亲表示法。用一个一维数组存所有节点，每个节点除了存数据本身，再存一个parent下标，指向它的父节点在数组中的位置。这种结构找父节点贼快，O(1)搞定，但找孩子需要遍历整个数组，效率很低。适用于需要频繁向上回溯的场景，比如并查集的一种实现思路。

第二种：孩子表示法。每个节点维护一个孩子链表，把所有子节点串起来。这种结构找孩子很方便，但找父节点就麻烦了。适合自顶向下的遍历场景。

第三种：孩子兄弟表示法。这也是我最推崇的一种，每个节点只存两个指针：firstChild（第一个孩子）和nextSibling（下一个兄弟）。这样一来，任何一棵普通的树，不管每个节点有多少个孩子，都能统一成二叉树的形态。这就是树的“二叉树化”，也是很多算法题里把多叉树当二叉树处理的底层原理。

这三种存储结构各有优劣，考试选择题喜欢考“以下哪种结构适合频繁找父节点”，答案是双亲表示法。而工程上，我们绝大多数时候直接用标准二叉树节点结构，因为它在时间效率和空间消耗之间取得了最好的平衡。这也是为什么严蔚敏那本教材花大量篇幅讲二叉树，本质上二叉树就是树结构的“最小完备模型”。

2. 二叉树与遍历：越基础的东西越能拉开差距

2.1 为什么二叉树是树结构的“主角”

如果你去问一个工作十年的老程序员，树结构里用得最多的是什么，大概率答案是二叉树。这不是偶然的。二叉树每个节点最多两个孩子，left和right两个指针，存储结构极其规整；而且任何多叉树都可以通过孩子兄弟法转换成二叉树，所以掌握二叉树就等于掌握了所有树的处理能力。

二叉树里还有两个特殊形态需要单独记一下。满二叉树是每一层节点数都达到最大值，也就是第k层有2^(k-1)个节点；完全二叉树则是除最后一层外，每一层都是满的，最后一层的节点都连续集中在左侧。完全二叉树最经典的应用是堆（优先队列），因为节点编号和数组下标天然对应，父节点下标是i，左孩子是2i+1，右孩子是2i+2（从0开始编号时），不需要指针就能用数组存完整棵树。

很多初学者不明白为什么非要把二叉树拎出来单讲，我的理解是：二叉树是所有树结构里“表达力不减、复杂度最低”的形态。它足够简单，递归实现时思路清晰；它又足够复杂，能覆盖几乎所有算法场景。把二叉树的增删改查和遍历写熟练，后面学平衡树、B树都是顺水推舟的事。

2.2 四种遍历的递归与非递归实现

树的核心操作是遍历，一共有四种经典方式：前序遍历（根-左-右）、中序遍历（左-根-右）、后序遍历（左-右-根）、层次遍历（从上到下、从左到右逐层扫）。

先看递归版，代码极简：

void preorder(TreeNode *root) { if (root == NULL) return; printf("%d ", root->val); // 访问根 preorder(root->left); // 递归左子树 preorder(root->right); // 递归右子树 } void inorder(TreeNode *root) { if (root == NULL) return; inorder(root->left); printf("%d ", root->val); inorder(root->right); } void postorder(TreeNode *root) { if (root == NULL) return; postorder(root->left); postorder(root->right); printf("%d ", root->val); }

递归版本之所以好写，是因为递归天然模拟了函数调用栈：每次进入一个子树就压栈，处理完就弹栈。但递归有两个问题：一是深度过大时可能栈溢出（比如一棵极度不平衡的树有十万层），二是面试官为了考察你的基本功，经常要求你写非递归版本。

非递归的核心思想是用显式的栈模拟递归调用栈。以前序遍历为例：

void preorder_iter(TreeNode *root) { if (root == NULL) return; TreeNode *stack[1000]; int top = -1; stack[++top] = root; while (top >= 0) { TreeNode *node = stack[top--]; printf("%d ", node->val); // 注意：先压右孩子，再压左孩子 if (node->right) stack[++top] = node->right; if (node->left) stack[++top] = node->left; } }

这里有一个非常经典的坑：前序遍历的非递归版，压栈顺序是“先右后左”。为什么？因为栈是先进后出的，我们希望下一轮先访问左孩子，那左孩子就必须最后压入栈，这样它才能最先弹出。这个细节我当年第一次写时就栽了跟头，打印出来的顺序永远不对，后来把压栈顺序反过来才恍然大悟。

中序遍历的非递归版稍复杂一些，需要一直往左走，把沿途节点都压栈，走到NULL再弹出访问，然后处理右子树：

void inorder_iter(TreeNode *root) { TreeNode *stack[1000] = {0}; int top = -1; TreeNode *cur = root; while (top >= 0 || cur != NULL) { while (cur != NULL) { stack[++top] = cur; cur = cur->left; } cur = stack[top--]; printf("%d ", cur->val); cur = cur->right; } }

后序遍历的非递归最麻烦，因为要保证“左-右-根”的顺序，根节点必须最后访问，所以需要记录上一个访问的节点，或者用“逆前序”技巧：前序遍历是根-左-右，改成根-右-左，再反转结果，就是左-右-根。这个方法很取巧，但笔试时确实好写。

层次遍历则需要用队列，不是栈。每弹出一个节点，就把它的左孩子和右孩子依次入队，这样天然按层推进：

void levelorder(TreeNode *root) { if (root == NULL) return; TreeNode *queue[1000]; int head = 0, tail = 0; queue[tail++] = root; while (head < tail) { TreeNode *node = queue[head++]; printf("%d ", node->val); if (node->left) queue[tail++] = node->left; if (node->right) queue[tail++] = node->right; } }

关于遍历，我还有一句重要的经验：中序遍历一棵二叉搜索树，得到的结果一定是有序递增序列。这句话是无数面试题和算法题的基石，比如判断一棵树是否为BST、找第K小节点、验证树的合法性，本质上都在用这个性质。

2.3 遍历题型的几个变体

遍历不只是打印顺序，它还是很多复杂操作的基础。我挑几个最高频的题型说：

由前序+中序重建二叉树。前序遍历的第一个元素一定是根，在中序遍历里找到这个根的位置，左边就是左子树，右边就是右子树，然后递归切分。核心思路是这样，但代码里最容易出错的是左右子树的边界下标。我建议画一张中序遍历的数组图，把左边界、右边界、根的位置标清楚，写起来就不容易乱了。

求树的深度。递归解是一行代码的事：int depth(TreeNode *root) { return root ? 1 + fmax(depth(root->left), depth(root->right)) : 0; }。非递归解可以用层次遍历，每遍历一层深度加1。

判断一棵树是否为二叉搜索树。很多新手会写“左孩子小于根、右孩子大于根就返回true”，这是错的。因为BST要求左子树的所有节点都小于根，不只是左孩子。正确做法是用中序遍历，看结果是否严格递增；或者递归时携带节点的上下界（min、max），时刻检查节点值是否落在合法区间内。

最近公共祖先（LCA）。在二叉树里找两个节点的最近公共祖先，核心逻辑是递归：如果当前节点是p或q，就返回当前节点；否则递归左子树和右子树，两边都不为空说明当前节点就是LCA。这道题在字节、腾讯的算法面试里出现频率极高，值得多刷几遍。

3. 从二叉搜索树到平衡树：平衡到底在平衡什么

3.1 BST为什么会退化

二叉搜索树（BST）被誉为最基础的数据结构之一，它的规则很简单：左子树所有节点小于根，右子树所有节点大于根。查找、插入、删除的平均时间复杂度都是O(log n)，听起来很完美。

但有个致命弱点：如果数据是按顺序插入的（1, 2, 3, 4, 5...），BST会退化成一条链。这时查找一个节点的时间复杂度退化成O(n)，和链表没什么区别。为什么会这样？因为每次新插入的节点都跑到右子树最右边，树完全失去了平衡。

所以平衡树想解决的问题本质只有一个：如何让树在动态插入和删除的过程中，始终保持相对平衡，从而让操作复杂度稳定在O(log n)。这不是一个简单的需求，背后有很多精巧的设计思路。

3.2 AVL与红黑树的取舍

AVL树是最早被发明的自平衡二叉搜索树，它要求任何节点的左右子树高度差绝对值不超过1，这个差值叫平衡因子。当插入或删除导致平衡被打破时，通过四种旋转操作（LL、RR、LR、RL）来恢复平衡。

AVL的优点是极度平衡，查找性能极佳；缺点是维护成本高，每次插入都可能引发多次旋转。所以AVL适合“查询远多于插入删除”的场景，比如数据库里某些读多写少的索引结构。

红黑树则是另一种思路，它不追求严格平衡，而是通过给节点染色（红/黑）加上一组约束，保证任意路径的长度差不超过2倍，即“最长路径不超过最短路径的两倍”。红黑树的调整操作比AVL少得多，插入删除更快，但查询性能略逊于AVL。

你肯定听过Java 8的HashMap在链表长度超过8时会转为红黑树，目的就是防止哈希冲突严重时链表过长导致查询退化成O(n)。为什么选红黑树而不选AVL？因为HashMap的操作是读改写混合的，插入删除频繁，红黑树的调整代价更低，整体吞吐更高。这也是“工程选型要结合场景”的典型例子。

到这儿我顺便提一嘴，很多文章会把红黑树讲得神乎其神，实际面试时能说出红黑树的五条性质、说明为什么比AVL更适合插入删除场景，就已经超过六成候选人了。红黑树的性质不需要硬背，理解它“放松平衡约束换性能”的设计哲学更重要。

3.3 B树与B+树：从内存走向磁盘

AVL和红黑树都是内存结构，假设访问任意节点的代价相同。但真实世界里数据存在磁盘上，访问一次磁盘IO的时间大约是内存访问的几万倍，这时候树的设计目标就变了：尽量减少磁盘IO次数。

磁盘IO的代价与“读了多少个节点”相关，所以想让树更矮，就要让一个节点多存几个孩子，这就是B树（多路平衡查找树）的由来。B树每个节点可以存储多个关键字和多个孩子指针，比如一棵3阶B树，每个节点最多2个关键字、3个孩子。对比二叉树，同样节点数B树的高度大幅降低，自然减少了磁盘IO次数。

B+树是B树的变体，也是MySQL InnoDB索引的底层结构。它和B树的关键区别有两点：

1. B+树的非叶子节点只存索引key，不存数据；所有数据都存在叶子节点。这样一来非叶子节点能容纳更多的key，树更矮。
2. B+树的叶子节点通过链表串在一起，范围查询（比如查id>5的所有记录）只需要找到第一个符合条件的叶子，然后顺着链表往后扫，极其高效。

面试的时候经常被问“为什么数据库索引用B+树不用红黑树”，标准答法就是：数据量大时红黑树太高，根节点到叶子节点需要几十次IO；而B+树只用三四层就能支撑千万级数据，IO次数少一个数量级，而且叶子节点链表天然支持高效范围查询。

4. 树在真实项目里的几种经典玩法

4.1 哈夫曼树与编码压缩

哈夫曼树也叫最优二叉树，它的定义很朴素：带权路径长度（WPL）最小的二叉树。什么叫WPL？所有叶子节点的权值乘以它到根节点的路径长度，然后求和，这个值越小越好。

构建哈夫曼树的流程其实特别简单：把每个权值看成一颗只有根节点的树，每次从森林里取两棵权值最小的树合并，新树的根权值是两者之和，再放回森林，重复直到只剩一棵树。这个过程用优先队列（最小堆）实现非常顺手。

哈夫曼树的应用不只是考试题，哈夫曼编码是压缩算法的经典基础。高频字符用短编码，低频字符用长编码，并且保证没有一个编码是另一个编码的前缀（这叫前缀编码），这样压缩数据后可以无歧义地解压。你在学任何压缩算法时，哈夫曼编码都是绕不开的基石。

4.2 表达式树与编译器

编译器把人类写的表达式翻译成机器能执行的指令，中间有一个关键步骤是把中缀表达式（比如a+b*c）转成后缀表达式，或者直接构造一棵表达式树。表达式树中，叶子节点是操作数，内部节点是运算符，后序遍历这棵树就能得到后缀表达式，计算时用栈实现。

你可能觉得这些离业务开发很远，但如果你接触过任何规则引擎、计算器程序、报表公式解析，底层基本都是这套逻辑。理解了表达式树，你就能看懂为什么1+2*3的结果是7不是9，因为构建成树之后，根节点是+，左子树是1，右子树是2*3这个乘法子树，计算顺序自然就被树的结构固定下来了。树的这种“用结构表达优先级和顺序”的能力，是很多工程设计的核心。

4.3 树形结构在系统里的影子

树结构无处不在，很多场景只是换了名称和包装。文件系统目录是一棵树，根目录是根节点，文件夹是内部节点，文件是叶子节点；网站的DOM结构是一棵树；路由表里的Trie（字典树）是一棵树，专门用来处理字符串前缀匹配；进程调度里的堆（优先队列）本质是一棵完全二叉树。

还有一类容易被忽略的“树”，是硬件和操作系统里的设备树与时钟树。设备树是Linux内核用来描述硬件信息的树形数据结构，解决嵌入式平台上驱动代码和硬件配置耦合的问题；时钟树则是芯片内部时钟源经过PLL分频、倍频后分发到各个外设的树形路径。这两种树虽然和数据结构课的“树”不完全是一码事，但它们都借用了树的层级组织思想。工程师用树形思维管理复杂系统，这也是为什么学数据结构一定要把树学透，因为它是一种思维工具，而不只是代码工具。

5. 手写树的实现细节与调试技巧

5.1 节点定义与内存管理

C语言下写树，最痛苦的是内存管理。每创建一个节点，都要malloc一次，用完不free就会内存泄漏。我见过不少同学在LeetCode上刷题刷得很顺，一到自己用C写完整程序就各种段错误，原因往往是忘了给节点分配内存，或者free之后还继续访问指针。

Java系同学会轻松很多，new出来的对象有垃圾回收兜底，但要注意别在递归里重复创建大量对象导致GC频繁。写代码前的设计建议是：明确每个节点由谁负责释放。如果树是自包含的，写完销毁函数递归释放所有子树；如果只是借用别人的指针，千万别擅自free。

5.2 递归的三个常见坑

递归是树操作的核心，但也最容易出错。我总结三个高频坑：

第一，缺少终止条件或终止条件写错。比如判断空节点时用了root == NULL，但某些递归逻辑里节点可能被传成NULL导致访问root->val段错误。诀窍是每次进入递归函数第一行就检查空指针，这也叫“防守式编程”。

第二，返回值语义不清晰。比如求树的高度，有的递归函数返回的是“该节点为根的子树的深度”，有的返回的是“从该节点到根的层数”，语义不同会导致递归公式完全不一样。我建议在纸上写下函数的输入、输出含义再动手写代码，能避免大量返工。

第三，忽略了空子树。比如判断对称二叉树，递归参数是左右两个节点，你只处理了左节点不空而右节点空的情况，却没考虑两个都走到底的情况，导致死循环或越界。写递归时，把所有可能的分支列出来：都空、一个空、都不空，三种情况分别处理，基本就稳了。

5.3 层次遍历与层序遍历的调试技巧

层次遍历是广度优先搜索在树上的体现，但初学时很容易把队列的入队出队条件搞混。我常用的调试手段是“打印节点+打印当前队列长度”，比如：

while (head < tail) { int size = tail - head; // 当前层节点数 for (int i = 0; i < size; i++) { TreeNode *node = queue[head++]; printf("%d ", node->val); if (node->left) queue[tail++] = node->left; if (node->right) queue[tail++] = node->right; } printf("| "); // 每层结束打一个竖线 }

这样你能直观看到每一层有哪些节点，如果顺序不对，很快能定位是入队顺序的问题还是边界条件的问题。还有一个小技巧：输入一棵树后用“缩进+空位补齐”的方式打印出树形结构，比单调地打印一行数组直观得多。我自己写树算法时，经常先写一个printTree函数把树可视化，再跑测试用例，效率直接翻倍。

5.4 用简单测试用例验证

树的测试用例设计是一门手艺。不要一上来就测复杂情况，我建议按这个顺序来：先测空树（NULL入参），再测单节点，再测左斜树（所有节点只有左孩子）、右斜树、完全二叉树、满二叉树，最后再测随机生成的树。每一层都验证通过后，再往上叠加复杂度，出问题时能快速锁定原因。特别是某些递归结构，单节点和空树往往能暴露出终止条件的问题。

6. 树的高频考点与实战速查

6.1 概念题与代码题速查表

我把树的高频考点整理成一个表，方便你复习时快速定位：

这个表里的每一条我都建议动手写一遍代码，只看不写等于白看。

另外复习时别只盯着二叉树，多叉树的遍历（孩子兄弟法转二叉树）也要会，有些学校期末喜欢考。还有几个容易被忽略但偶尔会考出来的概念：树的路径长度、树的带权路径长度WPL、完全二叉树的性质（比如第i个节点叶子的判定条件），这些都在王道或严蔚敏教材里有定义，考前过一眼不至于丢分。

6.2 复习方法建议

很多人在树这章卡住，不是智商问题，是学习方法不对。我的个人经验是“三步走”：

第一步，动手画。找一本书或一套题，把每个概念都在纸上画出来。根、叶子、深度、度、平衡因子，画着画着就理解了。这一步不能省，树是空间结构，光在脑子里想很容易乱。

第二步，手写代码。先写递归版的遍历和增删查，再改成非递归版。写的时候不参考任何资料，写完再对照标准答案检查。注意“写”不只是敲键盘，先在纸上写伪代码，理清栈的进出顺序，再上机调试，效果最好。

第三步，刷题验证。去网上随便找一套树相关的算法题，从LeetCode 94（二叉树的中序遍历）、102（层序遍历）、105（前序中序重建）、236（LCA）开始刷。这几题覆盖面很广，基本把树的遍历、递归、分治都练到了。刷完这些再做二叉搜索树和平衡树的题目，你会觉得顺手很多。

如果你是在准备考研或期末，我建议把严蔚敏教材的二叉树章节和习题刷两遍，第一遍快速过概念，第二遍重点做代码题和画图题。王道系列的“数据结构”笔记也整理得不错，特别是知识点框架和易错点总结，适合冲刺阶段使用。

信息学奥赛的同学如果刷到“家谱树”这种题，本质上就是树的先根遍历或拓扑排序，不要被名字吓住。树的知识点一旦串起来，你会发现变种再多，底层的递归+栈+队列三板斧是不变的。

最后再分享一个小经验：调试树算法时，把每一步递归的输入输出打出来。比如前序遍历，打印每次进入函数时的节点值、当前栈内容，你会亲眼看到递归是怎么一层层展开、一层层收回的。这个习惯帮我解决了很多莫名其妙的段错误和死循环，也推荐你试一试。树这个数据结构，学的时候你可能会觉得它绕，但一旦把它变成你的思维的一部分，后续学图、学动态规划、学各种复杂算法，都会顺很多。