学数据结构的时候树这一章往往是很多人第一次意识到“代码还能这么玩”的地方。链表再怎么折腾也就是一条线但树不一样它有了分支有了层级有了递归的用武之地。无论你是在准备考研、期末复习还是刷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左孩子是2i1右孩子是2i2从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树的关键区别有两点B树的非叶子节点只存索引key不存数据所有数据都存在叶子节点。这样一来非叶子节点能容纳更多的key树更矮。B树的叶子节点通过链表串在一起范围查询比如查id5的所有记录只需要找到第一个符合条件的叶子然后顺着链表往后扫极其高效。面试的时候经常被问“为什么数据库索引用B树不用红黑树”标准答法就是数据量大时红黑树太高根节点到叶子节点需要几十次IO而B树只用三四层就能支撑千万级数据IO次数少一个数量级而且叶子节点链表天然支持高效范围查询。4. 树在真实项目里的几种经典玩法4.1 哈夫曼树与编码压缩哈夫曼树也叫最优二叉树它的定义很朴素带权路径长度WPL最小的二叉树。什么叫WPL所有叶子节点的权值乘以它到根节点的路径长度然后求和这个值越小越好。构建哈夫曼树的流程其实特别简单把每个权值看成一颗只有根节点的树每次从森林里取两棵权值最小的树合并新树的根权值是两者之和再放回森林重复直到只剩一棵树。这个过程用优先队列最小堆实现非常顺手。哈夫曼树的应用不只是考试题哈夫曼编码是压缩算法的经典基础。高频字符用短编码低频字符用长编码并且保证没有一个编码是另一个编码的前缀这叫前缀编码这样压缩数据后可以无歧义地解压。你在学任何压缩算法时哈夫曼编码都是绕不开的基石。4.2 表达式树与编译器编译器把人类写的表达式翻译成机器能执行的指令中间有一个关键步骤是把中缀表达式比如ab*c转成后缀表达式或者直接构造一棵表达式树。表达式树中叶子节点是操作数内部节点是运算符后序遍历这棵树就能得到后缀表达式计算时用栈实现。你可能觉得这些离业务开发很远但如果你接触过任何规则引擎、计算器程序、报表公式解析底层基本都是这套逻辑。理解了表达式树你就能看懂为什么12*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 概念题与代码题速查表我把树的高频考点整理成一个表方便你复习时快速定位考点核心考察点解答要点树的深度/高度递归与迭代递归一行迭代用层序计数四种遍历栈与队列的应用前序非递归先压右中序一路向左压栈层序用队列由前序中序重建树递归划分区间前序第一个为根中序定位左右子树范围判断BST中序有序 / 节点上下界不能用“左孩子根右孩子”代替全局验证最近公共祖先LCA后序递归思维左右递归非空即根二叉树的最大宽度层序数组下标用堆式编号宽度最右下标-最左下标1树的序列化与反序列化前序或层序 哨兵用NULL占位前序递归序列化AVL失衡旋转LL/RR/LR/RL插入后回溯平衡因子LL右旋、RR左旋、LR先左后右红黑树性质五条性质与旋转染色黑高一致、路径差不超过2倍B树与B树区别索引结构选型内节点只存key、叶子链式、范围查询哈夫曼编码构建与WPL计算最小堆取两最小合并前缀编码表达式树中缀转树、后序求值运算符为根操作数为叶子这个表里的每一条我都建议动手写一遍代码只看不写等于白看。另外复习时别只盯着二叉树多叉树的遍历孩子兄弟法转二叉树也要会有些学校期末喜欢考。还有几个容易被忽略但偶尔会考出来的概念树的路径长度、树的带权路径长度WPL、完全二叉树的性质比如第i个节点叶子的判定条件这些都在王道或严蔚敏教材里有定义考前过一眼不至于丢分。6.2 复习方法建议很多人在树这章卡住不是智商问题是学习方法不对。我的个人经验是“三步走”第一步动手画。找一本书或一套题把每个概念都在纸上画出来。根、叶子、深度、度、平衡因子画着画着就理解了。这一步不能省树是空间结构光在脑子里想很容易乱。第二步手写代码。先写递归版的遍历和增删查再改成非递归版。写的时候不参考任何资料写完再对照标准答案检查。注意“写”不只是敲键盘先在纸上写伪代码理清栈的进出顺序再上机调试效果最好。第三步刷题验证。去网上随便找一套树相关的算法题从LeetCode 94二叉树的中序遍历、102层序遍历、105前序中序重建、236LCA开始刷。这几题覆盖面很广基本把树的遍历、递归、分治都练到了。刷完这些再做二叉搜索树和平衡树的题目你会觉得顺手很多。如果你是在准备考研或期末我建议把严蔚敏教材的二叉树章节和习题刷两遍第一遍快速过概念第二遍重点做代码题和画图题。王道系列的“数据结构”笔记也整理得不错特别是知识点框架和易错点总结适合冲刺阶段使用。信息学奥赛的同学如果刷到“家谱树”这种题本质上就是树的先根遍历或拓扑排序不要被名字吓住。树的知识点一旦串起来你会发现变种再多底层的递归栈队列三板斧是不变的。最后再分享一个小经验调试树算法时把每一步递归的输入输出打出来。比如前序遍历打印每次进入函数时的节点值、当前栈内容你会亲眼看到递归是怎么一层层展开、一层层收回的。这个习惯帮我解决了很多莫名其妙的段错误和死循环也推荐你试一试。树这个数据结构学的时候你可能会觉得它绕但一旦把它变成你的思维的一部分后续学图、学动态规划、学各种复杂算法都会顺很多。 
长河君 · 2026/9/9 18:03:40 · 阅读 1.2k 数据结构树全解析：从二叉树遍历到红黑树与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左孩子是2i1右孩子是2i2从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树的关键区别有两点B树的非叶子节点只存索引key不存数据所有数据都存在叶子节点。这样一来非叶子节点能容纳更多的key树更矮。B树的叶子节点通过链表串在一起范围查询比如查id5的所有记录只需要找到第一个符合条件的叶子然后顺着链表往后扫极其高效。面试的时候经常被问“为什么数据库索引用B树不用红黑树”标准答法就是数据量大时红黑树太高根节点到叶子节点需要几十次IO而B树只用三四层就能支撑千万级数据IO次数少一个数量级而且叶子节点链表天然支持高效范围查询。4. 树在真实项目里的几种经典玩法4.1 哈夫曼树与编码压缩哈夫曼树也叫最优二叉树它的定义很朴素带权路径长度WPL最小的二叉树。什么叫WPL所有叶子节点的权值乘以它到根节点的路径长度然后求和这个值越小越好。构建哈夫曼树的流程其实特别简单把每个权值看成一颗只有根节点的树每次从森林里取两棵权值最小的树合并新树的根权值是两者之和再放回森林重复直到只剩一棵树。这个过程用优先队列最小堆实现非常顺手。哈夫曼树的应用不只是考试题哈夫曼编码是压缩算法的经典基础。高频字符用短编码低频字符用长编码并且保证没有一个编码是另一个编码的前缀这叫前缀编码这样压缩数据后可以无歧义地解压。你在学任何压缩算法时哈夫曼编码都是绕不开的基石。4.2 表达式树与编译器编译器把人类写的表达式翻译成机器能执行的指令中间有一个关键步骤是把中缀表达式比如ab*c转成后缀表达式或者直接构造一棵表达式树。表达式树中叶子节点是操作数内部节点是运算符后序遍历这棵树就能得到后缀表达式计算时用栈实现。你可能觉得这些离业务开发很远但如果你接触过任何规则引擎、计算器程序、报表公式解析底层基本都是这套逻辑。理解了表达式树你就能看懂为什么12*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 概念题与代码题速查表我把树的高频考点整理成一个表方便你复习时快速定位考点核心考察点解答要点树的深度/高度递归与迭代递归一行迭代用层序计数四种遍历栈与队列的应用前序非递归先压右中序一路向左压栈层序用队列由前序中序重建树递归划分区间前序第一个为根中序定位左右子树范围判断BST中序有序 / 节点上下界不能用“左孩子根右孩子”代替全局验证最近公共祖先LCA后序递归思维左右递归非空即根二叉树的最大宽度层序数组下标用堆式编号宽度最右下标-最左下标1树的序列化与反序列化前序或层序 哨兵用NULL占位前序递归序列化AVL失衡旋转LL/RR/LR/RL插入后回溯平衡因子LL右旋、RR左旋、LR先左后右红黑树性质五条性质与旋转染色黑高一致、路径差不超过2倍B树与B树区别索引结构选型内节点只存key、叶子链式、范围查询哈夫曼编码构建与WPL计算最小堆取两最小合并前缀编码表达式树中缀转树、后序求值运算符为根操作数为叶子这个表里的每一条我都建议动手写一遍代码只看不写等于白看。另外复习时别只盯着二叉树多叉树的遍历孩子兄弟法转二叉树也要会有些学校期末喜欢考。还有几个容易被忽略但偶尔会考出来的概念树的路径长度、树的带权路径长度WPL、完全二叉树的性质比如第i个节点叶子的判定条件这些都在王道或严蔚敏教材里有定义考前过一眼不至于丢分。6.2 复习方法建议很多人在树这章卡住不是智商问题是学习方法不对。我的个人经验是“三步走”第一步动手画。找一本书或一套题把每个概念都在纸上画出来。根、叶子、深度、度、平衡因子画着画着就理解了。这一步不能省树是空间结构光在脑子里想很容易乱。第二步手写代码。先写递归版的遍历和增删查再改成非递归版。写的时候不参考任何资料写完再对照标准答案检查。注意“写”不只是敲键盘先在纸上写伪代码理清栈的进出顺序再上机调试效果最好。第三步刷题验证。去网上随便找一套树相关的算法题从LeetCode 94二叉树的中序遍历、102层序遍历、105前序中序重建、236LCA开始刷。这几题覆盖面很广基本把树的遍历、递归、分治都练到了。刷完这些再做二叉搜索树和平衡树的题目你会觉得顺手很多。如果你是在准备考研或期末我建议把严蔚敏教材的二叉树章节和习题刷两遍第一遍快速过概念第二遍重点做代码题和画图题。王道系列的“数据结构”笔记也整理得不错特别是知识点框架和易错点总结适合冲刺阶段使用。信息学奥赛的同学如果刷到“家谱树”这种题本质上就是树的先根遍历或拓扑排序不要被名字吓住。树的知识点一旦串起来你会发现变种再多底层的递归栈队列三板斧是不变的。最后再分享一个小经验调试树算法时把每一步递归的输入输出打出来。比如前序遍历打印每次进入函数时的节点值、当前栈内容你会亲眼看到递归是怎么一层层展开、一层层收回的。这个习惯帮我解决了很多莫名其妙的段错误和死循环也推荐你试一试。树这个数据结构学的时候你可能会觉得它绕但一旦把它变成你的思维的一部分后续学图、学动态规划、学各种复杂算法都会顺很多。