第三章 树形心法：二叉树、平衡、堆与前缀树

第三章 · 树形心法：二叉树、平衡、堆与前缀树

本章要回答的三个问题：把链表的"一个后继"放开成"多个后继"，结构获得了什么新力量？为什么二叉搜索树的效率承诺会随插入顺序崩溃、又靠什么修复？堆明明长在数组里，凭什么自称树？

为什么会有这一章

第二章的链表是一根线：每个节点一个后继，走到哪算哪。树把后继放开成多个，立刻出现两个新东西——层次（根到叶有深浅之分）与分支（同一层各走各路）。这两个维度合起来，让"逐步缩小搜索范围"有了几何载体：满二叉树每往下一层，候选集合减半，对数级的复杂度从此有了着落。

但树的效率承诺有前提：树得"长得均衡"。按顺序插入会让二叉搜索树退化成一条链，对数级承诺作废——平衡树（AVL、红黑树）就是修复这门心法的代价与方案。堆则反其道而行：不追求全序，只保证"父胜于子"，恰好够用优先级调度，还顺便赢得数组存储的紧凑。Trie 把"逐字符比较"变成"逐层定位"，是字符串前缀问题的专属兵器。五种树形结构，五种不同的心法侧重。

值得先记住一个全局判断：树的所有对数级承诺，源头都是"每往下一层、候选减半"这一个动作。后面无论 AVL 的旋转、堆的上浮下沉，还是第七章线段树的区间二分，翻来覆去都是在守护或利用这条性质。抓住它，本章就不散。

读完能解决什么

对照开头的问题，本章的知识点清单如下：

• 能说出度、深度、高度、满与完全二叉树的定义，并解释"高度 h 的二叉树至多 2 的 h 次方减 1 个节点"；
• 能手写前序、中序、后序的递归与迭代版本，层序的队列版本，并用"前序加中序"重建二叉树；
• 能陈述并运用 BST 不变量（左小右大于根），写出插入、查找、删除（含双子节点情形），并复现顺序插入导致的退化实验；
• 能演示 AVL 的四种失衡与旋转修复，对比 AVL 与红黑树的旋转频次与适用场景；
• 能把堆映射到数组下标（父 i、子 2i+1 与 2i+2），实现上浮与下沉，说明建堆线性复杂度的直觉；
• 能实现 Trie 的插入、精确查找与前缀查找，估出其空间代价。

各节怎么分工

先决条件

• 第二章的链表（节点与引用）与队列（层序遍历要用）；
• 第一章的递归（树遍历天然递归）与复杂度推导（对数级来自每层减半）；
• 不需要任何图论基础。

往下走到哪

本章出口有三条线：BST 与平衡树的"有序结构"线，延伸到第五章二分查找与有序容器选型；堆的"半序结构"线，直接支撑第五章堆排序与优先队列应用；树的遍历范式则被第四章整体继承——图的深度优先、广度优先就是树遍历的推广（再加一个 visited 集合防绕圈）。第七章线段树更是把"数组下标树"玩到极致。树形心法是全册承上启下的中盘。练完本章做个小检验：任取一组数，手工按 BST 规则插入、再按堆规则建堆，两棵树画在一起对照——能说清"为什么同样的数据长出完全不同的两棵树"，本章的心法就分明了。

树形结构知识全景