开篇聊两句数据结构这课学的时候最怕什么不是数组不是链表而是学到“树”这一章突然感觉前面的全白学了——指针本来就绕结果树还得“指来指去”递归遍历更是让人脑子打结。其实树这个东西没那么玄乎。你手机里的文件目录、公司组织架构、网页的DOM节点、编译器怎么解析表达式、数据库索引底层长什么样全是树。可以说只要涉及“层级关系”和“一对多关系”树就是最自然、最省事的一种组织方式。这篇文章我把树这块从头到尾捋一遍树的本质到底是什么、那一堆术语到底在说什么、各种树二叉树、平衡树、B树、哈夫曼树、字典树各自解决什么问题、树的存储和遍历怎么做顺带把考研408里最爱考的细节也埋进去讲。不管是期末突击、考研复习还是刷LeetCode前想先把底层概念打牢这篇都够你看一阵子。1. 树的本质递归生长出来的层级结构1.1 为什么线性表不够用在数组和链表的世界里每个元素只有一个前驱、一个后继这种结构处理“排队”“有序列表”这类问题很顺手。但现实里大量关系是一对多的一个部门下面有多个员工一个文件夹下面有多个子文件夹一个网页标签里嵌套着多个子标签。这种结构天生就是“从根上分叉出去”的叫层级结构或树形结构。所以树的本质就一句话n个结点的有限集合满足两个条件——有且仅有一个根结点除根结点外其余结点被分成m个互不相交的有限集合每个集合又是一棵树。注意第二句话它是在“递归地定义树本身”。这也是初学者最容易忽略的点树不是“画出来”的是“自己定义自己”定义出来的。这种递归的定义方式直接决定了后面所有遍历算法都天然适合用递归去写。1.2 树与线性表的结构差异线性表和树的区别我用四个字概括线、面、体、网。数组和链表是“线性”的栈和队列是受限制的线性表它们解决的是“一维”的问题。树就是“二维”的有上下层级有兄弟结点但还没有跨层级之间的回路。到了图那就是“三维”的任意两个结点之间都可能拉一条边所以图比树更复杂树其实是图的一种特例——无环连通图。这个认知很重要因为后面学图的时候你会发现很多算法比如DFS、BFS、最短路径本质上都是“在树上怎么走”的推广。现在把树的递归思维扎根了后面学图就不会那么痛苦。1.3 一个例子帮你把“递归定义”焊死在脑子里我当年理解递归定义靠的是Windows的文件目录。C盘是根目录它下面有Program Files、Users、Windows三个顶层目录。点开Users里面又有Administrator、Public。再点开Administrator里面有Desktop、Documents。每一次“点开”的动作看到的其实还是一棵小树只不过它的根变成了你点开的那个文件夹。这就是树的递归本质任何一棵非空树把它的根结点去掉剩下的若干子树仍然各自是一棵树。写算法的时候你永远只需要关心“当前结点怎么处理、左右子树怎么递归处理”剩下的交给递归自己去做这比在脑子里硬模拟一个深层的调用栈要轻松得多。2. 树的专业术语体系树的术语一堆背起来容易混。我在给学生讲的时候喜欢用“家谱”打比方——树里很多术语天生就是家族用语这么一对照就好记了。术语含义家族类比根结点树顶那个唯一没有前驱的结点老祖宗叶子结点度为0的结点没有孩子没有后代的人分支结点度大于0的结点有后代的人双亲结点某个结点的直接上层爹妈孩子结点某个结点的直接下层子女兄弟结点同一个父结点的多个孩子亲兄弟姐妹祖先结点从根到某结点路径上的所有结点往上数一辈一辈的全算子孙结点某结点下面的所有结点往下数一辈一辈的全算结点的度结点拥有的子树个数有几个孩子树的度所有结点度的最大值整个家族里孩子最多的人有几个娃结点的层次根为第1层根的孩子为第2层……第几代人树的深度所有结点层次的最大值这个家族最多传了几代森林m棵互不相交的树的集合多个家族放一起真正考试和面试常考的隐藏考点有两个。第一个是“度为m的树”和“m叉树”的区别。度为m的树至少有一个结点的度等于m它强调的是“这棵树最大分叉数是m”m叉树则要求每个结点最多m个孩子不强求必须出现m度结点。前者由这棵树的实际形态决定后者是定义时就框死的两者不能混为一谈。第二个是“结点的深度和高度”的区别。深度是从根开始往下数根是第1层越往下数字越大反映的是“你离根有多远”高度是从叶子结点开始往上数叶子结点高度为1越往上数字越大反映的是“你离最远的叶子有多远”。整棵树的高度自然等于根结点的高度也等于所有结点深度的最大值。3. 树、森林与二叉树的转换逻辑3.1 为什么要强行转成二叉树树的孩子个数不固定有的结点两个孩子有的五个有的一个都没有这给存储和遍历都带来了很大麻烦——你要么每个结点预留最大度数的指针位浪费空间要么用动态列表存孩子实现复杂。而二叉树所有结点最多两个孩子存储和操作都规范化了所以教材里几乎都默认先把普通树转成二叉树再研究它的存储和遍历。这种“把不规整的问题转成规整的问题”的思路在计算机领域特别常见。你真去写代码处理一棵树的时候第一步往往不是直接遍历它而是先考虑它能不能用更规整的方式表达出来。3.2 孩子兄弟表示法的记忆口诀树转二叉树的规则教材上说的“左孩子右兄弟”六个字就是全部。实际操作里我加一句口诀“亲儿子放左边亲兄弟放右边。”拿一棵普通的树举例根结点A有三个孩子B、C、D。转成二叉树后A的左孩子不再是原来的B而是A的长子BB的右孩子是谁是B的二弟CC的右孩子是谁是三弟D。就这样原来的兄弟关系被“压”成了右链。这个转换对不对有个很妙的验证方法转换前后树的深度不变如果原树只有一个孩子且那个孩子没有后代深度会差但考试一般不会出这种极端题而且二叉树的右链上的结点在原树里都有同一个爸爸。反过来看二叉树转回树就是“右链拆开兄弟归位”。3.3 森林与二叉树的互相转换森林是m棵互不相交的树的集合。森林转二叉树三句话每棵树先各自转成二叉树把第二棵树的根接到第一棵树根的右孩子上第三棵、第四棵依次往右边接。最后得到的二叉树根没有右子树不根一定会有右子树因为森林里所有树的根最后全变成了整棵二叉树根结点右边的一条链。二叉树转森林就是逆操作先看根有没有右孩子有右孩子说明原森林里不止一棵树一直沿右链拆下去把每一棵拆出来的二叉树再还原成树。这个逆操作很多同学考试时容易漏了“根结点右边沿右链拆到最后”这一步记住森林转二叉树的时候右链上有几个结点原来就有几棵树逆过去拆就能数清楚。4. 二叉树树结构里的绝对主角4.1 二叉树不是“每个结点最多两个孩子”这么简单二叉树定义听起来人畜无害——要么空树要么左子树和右子树都是二叉树。但这里面藏着一个不少老手都容易忽略的点二叉树的左右子树是有顺序的左子树和右子树是两棵不同的树即使交换后结点的连接关系一样它们也是两棵不同的二叉树。这是二叉树和普通树最本质的区别。普通树的子树是无序的树B和树C换一下位置树还是那棵树二叉树不行左是左、右是右变了位置就是另一棵树。这个特性在后面讲遍历序列还原二叉树的时候特别关键——知道中序和另一种遍历序列能唯一确定一棵二叉树靠的就是“左右有顺序”这个性质。4.2 满二叉树与完全二叉树满二叉树每一层的结点数都拉满。深度为k的满二叉树结点总数为2^k - 1第i层有2^(i-1)个结点。这是二叉树里“最胖”的形态。完全二叉树只有最下面两层可以不满而且最下一层的叶子结点必须靠左连续排列倒数第二层如果有叶子结点必须集中在右侧连续排列。一句话记忆法编号为1到n的结点和同样深度的满二叉树前n个结点的位置一一对应。完全二叉树有个超实用的编号特性对编号为i的结点它的左孩子编号是2i如果存在右孩子编号是2i1如果存在双亲编号是⌊i/2⌋向下取整。这个性质是堆排序和优先队列的地基——数组里存着堆通过下标计算就能在树上跳来跳去不需要任何指针。顺带一提二叉树的顺序存储就是用这个编号来映射数组下标的。但普通二叉树用数组存很浪费空间比如一棵深度为4、每层只有一个结点的“斜树”数组得开15个位置才能放下4个结点大量空间空着。所以完全二叉树适合顺序存储普通二叉树一般用链式存储这是教材里反复强调的选择逻辑。4.3 二叉树的性质与推导考研408和期末考试都很喜欢考这几个性质非空二叉树的叶子结点数等于度为2的结点数加1即n₀ n₂ 1。推导很简单设结点总数为n度为0、1、2的结点数分别为n₀、n₁、n₂则n n₀ n₁ n₂从边的角度看n个结点的树有n-1条边而边的总数又等于n₁ 2n₂。联立两式就能得到n₀ n₂ 1。二叉树的第i层最多有2^(i-1)个结点。深度为k的二叉树最多有2^k - 1个结点。具有n个结点的完全二叉树的深度为⌊log₂n⌋ 1。这些性质看着多其实不用死背。第1个最常考我建议把它当结论记住第2、3个是等比数列求和现场能推第4个记公式就行。这些推导过程比结论本身重要因为题目稍微变形你要是只记了公式不会推很容易掉坑。5. 树的存储方式从指针到数组的思路演变5.1 双亲表示法每个结点除了存数据还存一个“父结点的下标”。这种存法找爸爸特别快但找孩子得遍历全表。我用一个二维数组就能实现#define MAX_TREE_SIZE 100 typedef struct { char data; int parent; } PTNode; typedef struct { PTNode nodes[MAX_TREE_SIZE]; int n; } PTree;这个方案用在“并查集”这种只需要快速找根、偶尔合并的场合很合适因为并查集的操作基本集中在“找爸爸”上。5.2 孩子表示法每个结点存一个孩子链表的头指针。找孩子方便了但找爸爸得遍历整棵树。这个方案的变种在操作系统文件系统、编译器语法树里用得比较多因为自顶向下遍历是常态。typedef struct ChildNode { int childIndex; struct ChildNode *next; } ChildNode; typedef struct { char data; ChildNode *firstChild; } CTNode;5.3 孩子兄弟表示法最推荐的通用方案每个结点只存两个指针firstChild第一个孩子和 nextSibling下一个兄弟。这就是前面说的“左孩子右兄弟”的存储实现。typedef struct CSNode { char data; struct CSNode *firstChild, *nextSibling; } CSNode;这个方案最优雅的地方在于一棵多叉树用这套结构存下来本质上就是一棵二叉树。你在内存里操作的是一棵二叉树但逻辑上是原来的多叉树这就把存储和算法从“多叉”这个麻烦概念里解放出来了。我看到不少初学者写树的相关代码一上来就去定义“每个结点最多有若干孩子”的通用结构写到最后满屏的for循环遍历孩子列表复杂度上去了不说还特别容易错。其实用孩子兄弟表示法很多操作都能直接套二叉树的现成逻辑。6. 树的遍历前序、中序、后序、层序6.1 递归遍历的记忆方法二叉树的四种遍历前中后序的区别在于“什么时候访问根结点”。前序先序根左右。先访问根再遍历左子树最后遍历右子树。中序左根右。先遍历左子树再访问根最后遍历右子树。后序左右根。先遍历左子树再遍历右子树最后访问根。层序从上到下、从左到右一层一层扫过去。初学者最怕的就是递归遍历的回溯过程一递归就晕。我的建议是画一棵三层的树把递归调用过程一层一层拆开每访问一个结点就在结点上标出“第几步访问”完整走一遍你对递归的理解就到位了。递归代码非常固定我直接给个模板void PreOrder(BiTree T) { if (T ! NULL) { visit(T); // 访问根 PreOrder(T-lchild); // 遍历左子树 PreOrder(T-rchild); // 遍历右子树 } }中序和后序只是把visit(T)那一行的位置换一下其他完全一样。6.2 层序遍历的核心套路队列层序遍历靠的是队列不是递归。思路是根结点先入队然后循环——出队一个结点访问它再把它左右孩子非空依次入队直到队列为空。这个套路刷LeetCode时特别好用二叉树的层序遍历、树的之字形遍历、求每层最大值、求树的宽度全是这个框架改出来的。之字形遍历也叫锯齿形遍历就是在层序基础上加了一个“层号奇数从左往右、偶数从右往左”的标志用双端队列或者普通队列反转就能实现。6.3 由遍历序列反推二叉树知道了前序中序或者后序中序就能唯一确定一棵二叉树但前序后序不能唯一确定。原因前面提过前序和后序不能区分左右子树。具体反推方法前序序列的第一个结点一定是根找到它在中序序列中的位置左边就是左子树的中序序列右边就是右子树的中序序列再看前序序列中对应长度的部分就能把左、右子树的前序序列也切出来递归做下去。这个考点是408的常客也是“递归思维”最典型的应用场景。我自己刷题时的一个习惯是拿到这类题先别急着想代码先手推两三遍推熟练了再写递归代码效率反而高很多。7. 树家族全览从二叉排序树到B树树这个家族太大了这里列一个对比表帮大家快速建立整体认知。树类型核心规则主要用途二叉排序树/二叉搜索树BST左子树所有结点小于根右子树所有结点大于根查找、排序平衡二叉树AVL每个结点左右子树高度差不超过1高频查找场景红黑树五条染色规则保证最长路径不超过最短路径2倍底层实现如关联容器B树多路平衡查找树一个结点存多个关键字数据库、文件系统索引B树B树变体数据全在叶子叶子间有指针数据库索引的主流实现哈夫曼树带权路径长度最小的二叉树哈夫曼编码、压缩算法字典树Trie按字符前缀分叉的多叉树字符串匹配、自动补全线段树用树维护区间信息区间查询、区间更新并查集用双亲表示法维护集合关系连通性问题四叉树递归划分二维空间碰撞检测、地图索引7.1 二叉排序树的查找效率为什么不稳定BST的查找效率取决于树的高度。理想情况下n个结点的BST高度是O(log n)查找一次很便宜但如果插入的顺序是升序或降序BST会退化成一个“链表”高度变成n查找效率直接掉到O(n)。这也就是为什么光有BST远远不够——它的形态不受控制退化风险太大。AVL树就是来解决这个问题的它规定了每个结点左右子树高度差不能超过1插入、删除后一旦失衡就通过旋转LL型、RR型、LR型、RL型四种旋转方式恢复平衡。这样做让树高度始终保持在O(log n)量级代价是插入、删除时的旋转操作稍微费点时间。7.2 红黑树平衡不是目的性能才是AVL是严格平衡的树特别“平整”红黑树则是“近似平衡”的——它牺牲了一点点严格性换来了更少的旋转次数。红黑树用颜色标记结点红或黑通过五条性质保证从根到叶子的最长路径不超过最短路径的2倍。红黑树的五条性质每个结点非红即黑根必须是黑叶子NIL结点是黑红结点的孩子必须是黑不能有连续两个红结点从任一结点到其每个叶子的所有路径都包含相同数目的黑结点。咋一看规则很绕但我建议大家这样记忆红黑树的本质是在“AVL严格平衡”和“懒散保存”之间找一个平衡点——它不追求左右子树高度严格相等只要求“黑路一样长、红路不连续”这样旋转次数少了插入删除整体变快了。Java的TreeMap、C的std::map底层都是红黑树都是因为它整体性能最稳。7.3 磁盘上的树B树与B树B树和B树是“磁盘友好型”的树。内存里我们追求低高度因为内存随机访问便宜但磁盘不一样一次磁盘I/O可能要几毫秒比内存慢好几个数量级所以我们要尽量减少I/O次数。B树的一个结点可以存很多关键字同时有多个孩子这样整棵树的高度可以压得非常低比如几百万条数据B树可能只需要3~4层。B树和B树最大的区别在于B树的所有结点都存数据B树只有叶子结点存数据内部结点只存索引B树的叶子结点通过指针串成链表范围查询特别高效。数据库索引选B树而不是B树主要是因为B树对范围查询友好、磁盘I/O次数稳定而且叶子结点存数据的特性让查询更规整。7.4 哈夫曼树与哈夫曼编码哈夫曼树最优二叉树解决的是“怎么让带权路径长度WPL最小”的问题。WPL是所有叶子结点的权值乘以路径长度之和。构造方法很机械每次从结点集合中选两个权值最小的结点把它们合并成一个新结点新结点的权值等于两棵树权值之和再把这个新结点放回集合重复到只剩一棵树。比如权值分别为2、3、5、7的四个叶子先选2和3合并成5集合变成5、5、7再选两个5合并成10集合变成10、7最后合并成17。WPL就是 2×3 3×3 5×2 7×1 32。这套东西在数据压缩里就是哈夫曼编码的底子。7.5 字典树、线段树与并查集字典树Trie按字符前缀分叉插入、查找单词都是O(len)跟数据量无关是搜索引擎自动补全的经典方案。前几年“CTFHub技能树”这类CTF平台特别喜欢考Trie的变体常见的就是让你实现一个字典树支持插入、搜索、前缀匹配。线段树是竞赛选手的必备工具专门处理区间查询和区间修改问题。它的思想是“把区间递归二分成树”每个结点维护一段区间的信息比如和、最大值查询和修改都是O(log n)。并查集没有严格意义的“树形存储”外观但底层原理就是双亲表示法——每个集合用一棵树表示树的根是集合的代表元素。它支持两个操作查Find找根和并Union把两棵树合在一起。优化时用路径压缩和按秩合并代码短到极致但功能强大刷连通分量类题目时属于“无脑套模板”的存在。8. 树的实操应用场景很多同学学完树觉得抽象不知道学了干嘛。这里列几个最直观的应用场景文件系统Linux的目录结构、Windows的资源管理器都是典型的树形结构挂载点、符号链接本质上就是对树结点的操作。编译器表达式树是编译器把中缀表达式转成语法树、生成中间代码的基础。比如a b * c的表达式树根是左孩子是a右孩子是以*为根的子树。后缀表达式求值也和表达式树的遍历密切相关。数据库索引MySQL的InnoDB引擎索引就是B树这也是为什么“树的索引”和“数据库性能优化”总被放在一起讨论。路由器与交换机的转发前缀树Trie在网络路由表里用来做最长前缀匹配查找目的IP对应的转发端口。游戏开发四叉树和八叉树用来做碰撞检测和空间管理把地图递归划分大大减少碰撞检测的计算量。机器学习决策树、随机森林、XGBoost这些模型核心结构就是树——回归树CART用树结构做回归拟合特征分裂的过程本质上就是“建树”。可以说树结构是贯穿计算机系统、算法、数据库、人工智能、网络的全能型基石。你要是把树学透了后面学任何一门计算机专业课都会轻松很多。9. 常见问题与误区我踩过的坑和总结的诀窍9.1 一道经典坑题2011个结点的树叶子结点有116个网上讨论度很高的一道题“已知一棵有2011个结点的树其叶结点个数是116该树对应的二叉树中无右孩子的结点个数是多少”这题难倒过一大片人因为它把“树转二叉树”和“结点计数”两个知识点搅在一起考。解析思路设树中度为1、2、3的结点数分别为n₁、n₂、n₃……叶子结点n₀116。由边的数量关系可知 n 1 n₁ 2n₂ 3n₃ ...所有结点的度数之和 边数 结点数-1。再用树转二叉树的规律原树中每个结点的“长子”第一个孩子在二叉树中变成左孩子其余孩子通过右链连接。最终二叉树中“无右孩子”的结点主要对应原树中的叶子结点除长子外、没有兄弟的结点等。这类题出错的根源是大家把“无右孩子”误当成“右孩子为空就一定是叶子”。其实在树转二叉树后原树里没有“右兄弟”的结点转出来右孩子就是空。做题前先在草稿纸上画一棵三层的树标好转换过程再套计数公式出错率会大幅下降。9.2 递归层数为何难把握先学会画递归树很多同学写树的递归遍历代码模板背得很熟但一旦遇到“求二叉树的直径”“判断是否是平衡二叉树”这类需要返回多个值或全局变量的题就不知道怎么写。我的建议是动手画递归树。把递归调用想象成树的分支每一层就是一个函数栈帧。递归的终止条件想清楚——什么时候返回空、什么时候返回0、什么时候返回一个特殊标记剩下的“当前层该干什么”看清楚代码就出来了。写过三遍以上你就不需要再画了。9.3 关于递归转迭代树的递归遍历很简单但面试官偶尔会问“不用递归怎么实现前序遍历/中序遍历”这时就要用显式栈模拟系统栈。前序是入栈右孩子再入栈左孩子中序是“一路向左入栈弹出访问后再处理右子树”。层序遍历天然是迭代的用队列就行。之字形遍历在层序基础上用双端队列控制头尾插入的方向这就是LeetCode上那道经典题目的核心思路。9.4 数据结构期末复习的一个高效方法期末复习最怕“什么都知道一点什么都不会做”。我给一个笨但有效的方法把每种数据结构的底层层层拷问三连——“它的逻辑结构是什么存储结构是什么支持哪些操作每个操作的时间复杂度是多少”树这一章也不例外。能把这四个问题对答如流期末考基本稳了。408的数据结构代码题树的代码题无非就是遍历、求高度、求宽度、判断平衡、构建二叉树、最近公共祖先这几类。每种题型固定思路我把这些当成“套路模板”反复练不仅能应付考试后面做项目看过一些源码的实现也能更快看懂别人写的树结构相关代码。10. 写在最后的几点体会树这种结构真正让人舒服的地方不在于它有多少变种、多少术语而在于它给“层级关系”提供了一套优雅的表达方式。我见过很多初学者花大量时间死记红黑树的旋转过程却搞不定最简单的递归遍历这是本末倒置。先把一棵普通树、一棵二叉树用最土的方式实现一遍、遍历一遍再往上加平衡、加颜色、加多路每一步都踏踏实实树的体系才算是真正长在你自己脑子里了。最后提一个我个人测试过的方法学完树之后试着用树结构去重新审视你电脑里的一个文件夹或者把一本教材的目录画成一棵树你会发现——知识体系和文件系统本质上都在用同一种思维组织信息。这种感觉很奇妙也是从“背概念”到“用结构”的真正分水岭。祝大家写树不再晕头转向调试不再无限递归。 树结构完全指南：从二叉树、递归遍历到B+树与哈夫曼树
开篇聊两句数据结构这课学的时候最怕什么不是数组不是链表而是学到“树”这一章突然感觉前面的全白学了——指针本来就绕结果树还得“指来指去”递归遍历更是让人脑子打结。其实树这个东西没那么玄乎。你手机里的文件目录、公司组织架构、网页的DOM节点、编译器怎么解析表达式、数据库索引底层长什么样全是树。可以说只要涉及“层级关系”和“一对多关系”树就是最自然、最省事的一种组织方式。这篇文章我把树这块从头到尾捋一遍树的本质到底是什么、那一堆术语到底在说什么、各种树二叉树、平衡树、B树、哈夫曼树、字典树各自解决什么问题、树的存储和遍历怎么做顺带把考研408里最爱考的细节也埋进去讲。不管是期末突击、考研复习还是刷LeetCode前想先把底层概念打牢这篇都够你看一阵子。1. 树的本质递归生长出来的层级结构1.1 为什么线性表不够用在数组和链表的世界里每个元素只有一个前驱、一个后继这种结构处理“排队”“有序列表”这类问题很顺手。但现实里大量关系是一对多的一个部门下面有多个员工一个文件夹下面有多个子文件夹一个网页标签里嵌套着多个子标签。这种结构天生就是“从根上分叉出去”的叫层级结构或树形结构。所以树的本质就一句话n个结点的有限集合满足两个条件——有且仅有一个根结点除根结点外其余结点被分成m个互不相交的有限集合每个集合又是一棵树。注意第二句话它是在“递归地定义树本身”。这也是初学者最容易忽略的点树不是“画出来”的是“自己定义自己”定义出来的。这种递归的定义方式直接决定了后面所有遍历算法都天然适合用递归去写。1.2 树与线性表的结构差异线性表和树的区别我用四个字概括线、面、体、网。数组和链表是“线性”的栈和队列是受限制的线性表它们解决的是“一维”的问题。树就是“二维”的有上下层级有兄弟结点但还没有跨层级之间的回路。到了图那就是“三维”的任意两个结点之间都可能拉一条边所以图比树更复杂树其实是图的一种特例——无环连通图。这个认知很重要因为后面学图的时候你会发现很多算法比如DFS、BFS、最短路径本质上都是“在树上怎么走”的推广。现在把树的递归思维扎根了后面学图就不会那么痛苦。1.3 一个例子帮你把“递归定义”焊死在脑子里我当年理解递归定义靠的是Windows的文件目录。C盘是根目录它下面有Program Files、Users、Windows三个顶层目录。点开Users里面又有Administrator、Public。再点开Administrator里面有Desktop、Documents。每一次“点开”的动作看到的其实还是一棵小树只不过它的根变成了你点开的那个文件夹。这就是树的递归本质任何一棵非空树把它的根结点去掉剩下的若干子树仍然各自是一棵树。写算法的时候你永远只需要关心“当前结点怎么处理、左右子树怎么递归处理”剩下的交给递归自己去做这比在脑子里硬模拟一个深层的调用栈要轻松得多。2. 树的专业术语体系树的术语一堆背起来容易混。我在给学生讲的时候喜欢用“家谱”打比方——树里很多术语天生就是家族用语这么一对照就好记了。术语含义家族类比根结点树顶那个唯一没有前驱的结点老祖宗叶子结点度为0的结点没有孩子没有后代的人分支结点度大于0的结点有后代的人双亲结点某个结点的直接上层爹妈孩子结点某个结点的直接下层子女兄弟结点同一个父结点的多个孩子亲兄弟姐妹祖先结点从根到某结点路径上的所有结点往上数一辈一辈的全算子孙结点某结点下面的所有结点往下数一辈一辈的全算结点的度结点拥有的子树个数有几个孩子树的度所有结点度的最大值整个家族里孩子最多的人有几个娃结点的层次根为第1层根的孩子为第2层……第几代人树的深度所有结点层次的最大值这个家族最多传了几代森林m棵互不相交的树的集合多个家族放一起真正考试和面试常考的隐藏考点有两个。第一个是“度为m的树”和“m叉树”的区别。度为m的树至少有一个结点的度等于m它强调的是“这棵树最大分叉数是m”m叉树则要求每个结点最多m个孩子不强求必须出现m度结点。前者由这棵树的实际形态决定后者是定义时就框死的两者不能混为一谈。第二个是“结点的深度和高度”的区别。深度是从根开始往下数根是第1层越往下数字越大反映的是“你离根有多远”高度是从叶子结点开始往上数叶子结点高度为1越往上数字越大反映的是“你离最远的叶子有多远”。整棵树的高度自然等于根结点的高度也等于所有结点深度的最大值。3. 树、森林与二叉树的转换逻辑3.1 为什么要强行转成二叉树树的孩子个数不固定有的结点两个孩子有的五个有的一个都没有这给存储和遍历都带来了很大麻烦——你要么每个结点预留最大度数的指针位浪费空间要么用动态列表存孩子实现复杂。而二叉树所有结点最多两个孩子存储和操作都规范化了所以教材里几乎都默认先把普通树转成二叉树再研究它的存储和遍历。这种“把不规整的问题转成规整的问题”的思路在计算机领域特别常见。你真去写代码处理一棵树的时候第一步往往不是直接遍历它而是先考虑它能不能用更规整的方式表达出来。3.2 孩子兄弟表示法的记忆口诀树转二叉树的规则教材上说的“左孩子右兄弟”六个字就是全部。实际操作里我加一句口诀“亲儿子放左边亲兄弟放右边。”拿一棵普通的树举例根结点A有三个孩子B、C、D。转成二叉树后A的左孩子不再是原来的B而是A的长子BB的右孩子是谁是B的二弟CC的右孩子是谁是三弟D。就这样原来的兄弟关系被“压”成了右链。这个转换对不对有个很妙的验证方法转换前后树的深度不变如果原树只有一个孩子且那个孩子没有后代深度会差但考试一般不会出这种极端题而且二叉树的右链上的结点在原树里都有同一个爸爸。反过来看二叉树转回树就是“右链拆开兄弟归位”。3.3 森林与二叉树的互相转换森林是m棵互不相交的树的集合。森林转二叉树三句话每棵树先各自转成二叉树把第二棵树的根接到第一棵树根的右孩子上第三棵、第四棵依次往右边接。最后得到的二叉树根没有右子树不根一定会有右子树因为森林里所有树的根最后全变成了整棵二叉树根结点右边的一条链。二叉树转森林就是逆操作先看根有没有右孩子有右孩子说明原森林里不止一棵树一直沿右链拆下去把每一棵拆出来的二叉树再还原成树。这个逆操作很多同学考试时容易漏了“根结点右边沿右链拆到最后”这一步记住森林转二叉树的时候右链上有几个结点原来就有几棵树逆过去拆就能数清楚。4. 二叉树树结构里的绝对主角4.1 二叉树不是“每个结点最多两个孩子”这么简单二叉树定义听起来人畜无害——要么空树要么左子树和右子树都是二叉树。但这里面藏着一个不少老手都容易忽略的点二叉树的左右子树是有顺序的左子树和右子树是两棵不同的树即使交换后结点的连接关系一样它们也是两棵不同的二叉树。这是二叉树和普通树最本质的区别。普通树的子树是无序的树B和树C换一下位置树还是那棵树二叉树不行左是左、右是右变了位置就是另一棵树。这个特性在后面讲遍历序列还原二叉树的时候特别关键——知道中序和另一种遍历序列能唯一确定一棵二叉树靠的就是“左右有顺序”这个性质。4.2 满二叉树与完全二叉树满二叉树每一层的结点数都拉满。深度为k的满二叉树结点总数为2^k - 1第i层有2^(i-1)个结点。这是二叉树里“最胖”的形态。完全二叉树只有最下面两层可以不满而且最下一层的叶子结点必须靠左连续排列倒数第二层如果有叶子结点必须集中在右侧连续排列。一句话记忆法编号为1到n的结点和同样深度的满二叉树前n个结点的位置一一对应。完全二叉树有个超实用的编号特性对编号为i的结点它的左孩子编号是2i如果存在右孩子编号是2i1如果存在双亲编号是⌊i/2⌋向下取整。这个性质是堆排序和优先队列的地基——数组里存着堆通过下标计算就能在树上跳来跳去不需要任何指针。顺带一提二叉树的顺序存储就是用这个编号来映射数组下标的。但普通二叉树用数组存很浪费空间比如一棵深度为4、每层只有一个结点的“斜树”数组得开15个位置才能放下4个结点大量空间空着。所以完全二叉树适合顺序存储普通二叉树一般用链式存储这是教材里反复强调的选择逻辑。4.3 二叉树的性质与推导考研408和期末考试都很喜欢考这几个性质非空二叉树的叶子结点数等于度为2的结点数加1即n₀ n₂ 1。推导很简单设结点总数为n度为0、1、2的结点数分别为n₀、n₁、n₂则n n₀ n₁ n₂从边的角度看n个结点的树有n-1条边而边的总数又等于n₁ 2n₂。联立两式就能得到n₀ n₂ 1。二叉树的第i层最多有2^(i-1)个结点。深度为k的二叉树最多有2^k - 1个结点。具有n个结点的完全二叉树的深度为⌊log₂n⌋ 1。这些性质看着多其实不用死背。第1个最常考我建议把它当结论记住第2、3个是等比数列求和现场能推第4个记公式就行。这些推导过程比结论本身重要因为题目稍微变形你要是只记了公式不会推很容易掉坑。5. 树的存储方式从指针到数组的思路演变5.1 双亲表示法每个结点除了存数据还存一个“父结点的下标”。这种存法找爸爸特别快但找孩子得遍历全表。我用一个二维数组就能实现#define MAX_TREE_SIZE 100 typedef struct { char data; int parent; } PTNode; typedef struct { PTNode nodes[MAX_TREE_SIZE]; int n; } PTree;这个方案用在“并查集”这种只需要快速找根、偶尔合并的场合很合适因为并查集的操作基本集中在“找爸爸”上。5.2 孩子表示法每个结点存一个孩子链表的头指针。找孩子方便了但找爸爸得遍历整棵树。这个方案的变种在操作系统文件系统、编译器语法树里用得比较多因为自顶向下遍历是常态。typedef struct ChildNode { int childIndex; struct ChildNode *next; } ChildNode; typedef struct { char data; ChildNode *firstChild; } CTNode;5.3 孩子兄弟表示法最推荐的通用方案每个结点只存两个指针firstChild第一个孩子和 nextSibling下一个兄弟。这就是前面说的“左孩子右兄弟”的存储实现。typedef struct CSNode { char data; struct CSNode *firstChild, *nextSibling; } CSNode;这个方案最优雅的地方在于一棵多叉树用这套结构存下来本质上就是一棵二叉树。你在内存里操作的是一棵二叉树但逻辑上是原来的多叉树这就把存储和算法从“多叉”这个麻烦概念里解放出来了。我看到不少初学者写树的相关代码一上来就去定义“每个结点最多有若干孩子”的通用结构写到最后满屏的for循环遍历孩子列表复杂度上去了不说还特别容易错。其实用孩子兄弟表示法很多操作都能直接套二叉树的现成逻辑。6. 树的遍历前序、中序、后序、层序6.1 递归遍历的记忆方法二叉树的四种遍历前中后序的区别在于“什么时候访问根结点”。前序先序根左右。先访问根再遍历左子树最后遍历右子树。中序左根右。先遍历左子树再访问根最后遍历右子树。后序左右根。先遍历左子树再遍历右子树最后访问根。层序从上到下、从左到右一层一层扫过去。初学者最怕的就是递归遍历的回溯过程一递归就晕。我的建议是画一棵三层的树把递归调用过程一层一层拆开每访问一个结点就在结点上标出“第几步访问”完整走一遍你对递归的理解就到位了。递归代码非常固定我直接给个模板void PreOrder(BiTree T) { if (T ! NULL) { visit(T); // 访问根 PreOrder(T-lchild); // 遍历左子树 PreOrder(T-rchild); // 遍历右子树 } }中序和后序只是把visit(T)那一行的位置换一下其他完全一样。6.2 层序遍历的核心套路队列层序遍历靠的是队列不是递归。思路是根结点先入队然后循环——出队一个结点访问它再把它左右孩子非空依次入队直到队列为空。这个套路刷LeetCode时特别好用二叉树的层序遍历、树的之字形遍历、求每层最大值、求树的宽度全是这个框架改出来的。之字形遍历也叫锯齿形遍历就是在层序基础上加了一个“层号奇数从左往右、偶数从右往左”的标志用双端队列或者普通队列反转就能实现。6.3 由遍历序列反推二叉树知道了前序中序或者后序中序就能唯一确定一棵二叉树但前序后序不能唯一确定。原因前面提过前序和后序不能区分左右子树。具体反推方法前序序列的第一个结点一定是根找到它在中序序列中的位置左边就是左子树的中序序列右边就是右子树的中序序列再看前序序列中对应长度的部分就能把左、右子树的前序序列也切出来递归做下去。这个考点是408的常客也是“递归思维”最典型的应用场景。我自己刷题时的一个习惯是拿到这类题先别急着想代码先手推两三遍推熟练了再写递归代码效率反而高很多。7. 树家族全览从二叉排序树到B树树这个家族太大了这里列一个对比表帮大家快速建立整体认知。树类型核心规则主要用途二叉排序树/二叉搜索树BST左子树所有结点小于根右子树所有结点大于根查找、排序平衡二叉树AVL每个结点左右子树高度差不超过1高频查找场景红黑树五条染色规则保证最长路径不超过最短路径2倍底层实现如关联容器B树多路平衡查找树一个结点存多个关键字数据库、文件系统索引B树B树变体数据全在叶子叶子间有指针数据库索引的主流实现哈夫曼树带权路径长度最小的二叉树哈夫曼编码、压缩算法字典树Trie按字符前缀分叉的多叉树字符串匹配、自动补全线段树用树维护区间信息区间查询、区间更新并查集用双亲表示法维护集合关系连通性问题四叉树递归划分二维空间碰撞检测、地图索引7.1 二叉排序树的查找效率为什么不稳定BST的查找效率取决于树的高度。理想情况下n个结点的BST高度是O(log n)查找一次很便宜但如果插入的顺序是升序或降序BST会退化成一个“链表”高度变成n查找效率直接掉到O(n)。这也就是为什么光有BST远远不够——它的形态不受控制退化风险太大。AVL树就是来解决这个问题的它规定了每个结点左右子树高度差不能超过1插入、删除后一旦失衡就通过旋转LL型、RR型、LR型、RL型四种旋转方式恢复平衡。这样做让树高度始终保持在O(log n)量级代价是插入、删除时的旋转操作稍微费点时间。7.2 红黑树平衡不是目的性能才是AVL是严格平衡的树特别“平整”红黑树则是“近似平衡”的——它牺牲了一点点严格性换来了更少的旋转次数。红黑树用颜色标记结点红或黑通过五条性质保证从根到叶子的最长路径不超过最短路径的2倍。红黑树的五条性质每个结点非红即黑根必须是黑叶子NIL结点是黑红结点的孩子必须是黑不能有连续两个红结点从任一结点到其每个叶子的所有路径都包含相同数目的黑结点。咋一看规则很绕但我建议大家这样记忆红黑树的本质是在“AVL严格平衡”和“懒散保存”之间找一个平衡点——它不追求左右子树高度严格相等只要求“黑路一样长、红路不连续”这样旋转次数少了插入删除整体变快了。Java的TreeMap、C的std::map底层都是红黑树都是因为它整体性能最稳。7.3 磁盘上的树B树与B树B树和B树是“磁盘友好型”的树。内存里我们追求低高度因为内存随机访问便宜但磁盘不一样一次磁盘I/O可能要几毫秒比内存慢好几个数量级所以我们要尽量减少I/O次数。B树的一个结点可以存很多关键字同时有多个孩子这样整棵树的高度可以压得非常低比如几百万条数据B树可能只需要3~4层。B树和B树最大的区别在于B树的所有结点都存数据B树只有叶子结点存数据内部结点只存索引B树的叶子结点通过指针串成链表范围查询特别高效。数据库索引选B树而不是B树主要是因为B树对范围查询友好、磁盘I/O次数稳定而且叶子结点存数据的特性让查询更规整。7.4 哈夫曼树与哈夫曼编码哈夫曼树最优二叉树解决的是“怎么让带权路径长度WPL最小”的问题。WPL是所有叶子结点的权值乘以路径长度之和。构造方法很机械每次从结点集合中选两个权值最小的结点把它们合并成一个新结点新结点的权值等于两棵树权值之和再把这个新结点放回集合重复到只剩一棵树。比如权值分别为2、3、5、7的四个叶子先选2和3合并成5集合变成5、5、7再选两个5合并成10集合变成10、7最后合并成17。WPL就是 2×3 3×3 5×2 7×1 32。这套东西在数据压缩里就是哈夫曼编码的底子。7.5 字典树、线段树与并查集字典树Trie按字符前缀分叉插入、查找单词都是O(len)跟数据量无关是搜索引擎自动补全的经典方案。前几年“CTFHub技能树”这类CTF平台特别喜欢考Trie的变体常见的就是让你实现一个字典树支持插入、搜索、前缀匹配。线段树是竞赛选手的必备工具专门处理区间查询和区间修改问题。它的思想是“把区间递归二分成树”每个结点维护一段区间的信息比如和、最大值查询和修改都是O(log n)。并查集没有严格意义的“树形存储”外观但底层原理就是双亲表示法——每个集合用一棵树表示树的根是集合的代表元素。它支持两个操作查Find找根和并Union把两棵树合在一起。优化时用路径压缩和按秩合并代码短到极致但功能强大刷连通分量类题目时属于“无脑套模板”的存在。8. 树的实操应用场景很多同学学完树觉得抽象不知道学了干嘛。这里列几个最直观的应用场景文件系统Linux的目录结构、Windows的资源管理器都是典型的树形结构挂载点、符号链接本质上就是对树结点的操作。编译器表达式树是编译器把中缀表达式转成语法树、生成中间代码的基础。比如a b * c的表达式树根是左孩子是a右孩子是以*为根的子树。后缀表达式求值也和表达式树的遍历密切相关。数据库索引MySQL的InnoDB引擎索引就是B树这也是为什么“树的索引”和“数据库性能优化”总被放在一起讨论。路由器与交换机的转发前缀树Trie在网络路由表里用来做最长前缀匹配查找目的IP对应的转发端口。游戏开发四叉树和八叉树用来做碰撞检测和空间管理把地图递归划分大大减少碰撞检测的计算量。机器学习决策树、随机森林、XGBoost这些模型核心结构就是树——回归树CART用树结构做回归拟合特征分裂的过程本质上就是“建树”。可以说树结构是贯穿计算机系统、算法、数据库、人工智能、网络的全能型基石。你要是把树学透了后面学任何一门计算机专业课都会轻松很多。9. 常见问题与误区我踩过的坑和总结的诀窍9.1 一道经典坑题2011个结点的树叶子结点有116个网上讨论度很高的一道题“已知一棵有2011个结点的树其叶结点个数是116该树对应的二叉树中无右孩子的结点个数是多少”这题难倒过一大片人因为它把“树转二叉树”和“结点计数”两个知识点搅在一起考。解析思路设树中度为1、2、3的结点数分别为n₁、n₂、n₃……叶子结点n₀116。由边的数量关系可知 n 1 n₁ 2n₂ 3n₃ ...所有结点的度数之和 边数 结点数-1。再用树转二叉树的规律原树中每个结点的“长子”第一个孩子在二叉树中变成左孩子其余孩子通过右链连接。最终二叉树中“无右孩子”的结点主要对应原树中的叶子结点除长子外、没有兄弟的结点等。这类题出错的根源是大家把“无右孩子”误当成“右孩子为空就一定是叶子”。其实在树转二叉树后原树里没有“右兄弟”的结点转出来右孩子就是空。做题前先在草稿纸上画一棵三层的树标好转换过程再套计数公式出错率会大幅下降。9.2 递归层数为何难把握先学会画递归树很多同学写树的递归遍历代码模板背得很熟但一旦遇到“求二叉树的直径”“判断是否是平衡二叉树”这类需要返回多个值或全局变量的题就不知道怎么写。我的建议是动手画递归树。把递归调用想象成树的分支每一层就是一个函数栈帧。递归的终止条件想清楚——什么时候返回空、什么时候返回0、什么时候返回一个特殊标记剩下的“当前层该干什么”看清楚代码就出来了。写过三遍以上你就不需要再画了。9.3 关于递归转迭代树的递归遍历很简单但面试官偶尔会问“不用递归怎么实现前序遍历/中序遍历”这时就要用显式栈模拟系统栈。前序是入栈右孩子再入栈左孩子中序是“一路向左入栈弹出访问后再处理右子树”。层序遍历天然是迭代的用队列就行。之字形遍历在层序基础上用双端队列控制头尾插入的方向这就是LeetCode上那道经典题目的核心思路。9.4 数据结构期末复习的一个高效方法期末复习最怕“什么都知道一点什么都不会做”。我给一个笨但有效的方法把每种数据结构的底层层层拷问三连——“它的逻辑结构是什么存储结构是什么支持哪些操作每个操作的时间复杂度是多少”树这一章也不例外。能把这四个问题对答如流期末考基本稳了。408的数据结构代码题树的代码题无非就是遍历、求高度、求宽度、判断平衡、构建二叉树、最近公共祖先这几类。每种题型固定思路我把这些当成“套路模板”反复练不仅能应付考试后面做项目看过一些源码的实现也能更快看懂别人写的树结构相关代码。10. 写在最后的几点体会树这种结构真正让人舒服的地方不在于它有多少变种、多少术语而在于它给“层级关系”提供了一套优雅的表达方式。我见过很多初学者花大量时间死记红黑树的旋转过程却搞不定最简单的递归遍历这是本末倒置。先把一棵普通树、一棵二叉树用最土的方式实现一遍、遍历一遍再往上加平衡、加颜色、加多路每一步都踏踏实实树的体系才算是真正长在你自己脑子里了。最后提一个我个人测试过的方法学完树之后试着用树结构去重新审视你电脑里的一个文件夹或者把一本教材的目录画成一棵树你会发现——知识体系和文件系统本质上都在用同一种思维组织信息。这种感觉很奇妙也是从“背概念”到“用结构”的真正分水岭。祝大家写树不再晕头转向调试不再无限递归。