第三章 树与高级结构的进化链
第三章 · 树与高级结构的进化链
章节摘要：本章跟着"哪个操作慢，就为它造个结构"的主线走——树把层级关系装进递归的框架，堆让反复取最值不再扫描全表，前缀树把逐字符比较压成单步查表，并查集用近乎常数时间的合并与查询统治动态连通性问题。
一条主线
前两章的策略大多默认数据是线性的；本章主线从一个新的追问开始：当数据天然带层级，或者操作请求非常特殊（反复取最值、按前缀检索、动态判断连通），线性结构还够用吗？答案是远远不够，而每一次不够，都催生了一个专门进化出来的结构。故事从二叉树讲起：遍历它就是递归思想的正式亮相，前序、中序、后序只是"处理当前节点"的时机不同，层序则借队列完成从深度到广度的切换。接着堆登场：它的诉求极纯粹——只保证堆顶是最值，其余靠完全二叉树的形状维持平衡，于是插入与取最值都只需对数时间，TopK 问题从平方级排序进化到 n 乘 log k 的堆解法。前缀树解决的是字符串领域的痛点：逐字符比较太浪费，把公共前缀合并成共享路径，查个单词只需走一条路。压轴的并查集更极端，它几乎只做两件事——合并两个集合、查询两个元素是否同集合，却能以近乎常数级的均摊开销处理海量查询。
这四站共享同一条进化逻辑：不追求万能结构，只为那个反复出现的昂贵操作定制最小代价的方案。这正是面试官欣赏的工程判断力——知道在什么场景下放弃通用、选择专用。
沿途站点
第一站二叉树遍历：用递归三行写出前中后序，理解它们只是访问时机的排列组合；再用队列实现层序遍历，处理逐层输出；最后讨论迭代化——用显式栈替代系统调用栈，以及莫里斯遍历如何把空间开销压到常数级。第二站堆与 TopK：从"完全二叉树存进数组"这个精妙表示讲起，掌握上浮与下沉两个基本操作；然后以"最大的前 k 个数"为例对比三种解法——全排序、维护小顶堆、快速选择，看清数据规模与 k 的关系如何决定胜负。第三站前缀树：实现插入、查找、前缀查询三个接口，用单词自动补全的场景解释节点结构，并讨论内存换速度的代价与压缩前缀树的改良方向。第四站并查集：从朴素的双亲表示出发，引出按秩合并与路径压缩两大优化，用"朋友圈数量"这道经典题演示完整流程，最后给出带复杂度反阿克曼函数的结论性说明——它慢得有底线、快得近乎常数。
拐点与结论
本章第一个拐点在堆那里：它不是用来排序的（虽然堆排序确实存在），而是用来维护"动态的最值"的——数据边进边出、随时要当前最值，堆才是主场，静态数组排一次序反而更划算。认清"动态还是静态"这个前提，才不会在面试中选错武器。第二个拐点在前缀树：它用空间买来了与字符串长度相关而与词典规模无关的查询速度，当词典越大、查询越频繁，这笔交易越划算；反之小词典用哈希表就够，硬上前缀树反而臃肿。最后一个拐点属于并查集：两条优化各自看似微小——查询时顺手把沿途节点直接挂到根、合并时把矮树挂到高树下——叠加之后却造就了算法史上最漂亮的均摊复杂度之一。微小的常数级改进积累成质变，这是"进化链"思维的极致体现。
读完你应该
- 用递归与迭代两种方式实现二叉树的前序、中序、后序遍历，并用队列实现层序遍历的逐层输出；
- 手写堆的上浮与下沉，解释为什么用数组就能表示完全二叉树；
- 对 TopK 问题说出全排序、小顶堆、快速选择三种方案的复杂度与适用条件；
- 实现前缀树的插入、查找与前缀查询接口，并说明其空间代价；
- 实现带路径压缩与按秩合并的并查集，解决朋友圈或省份数量问题，能口述其均摊复杂度为什么近乎常数。
下一章的接力
结构、策略都齐了，最后一章回到考场与真实工程：边界条件怎样守住才不丢分，空间复杂度还能怎样继续压，以及这些进化出来的结构如何在缓存淘汰、任务调度、海量数据统计等系统设计题里登场。进化链的终点不是更快，而是把"为什么快"讲给面试官听。