Sherfiter's wiki for fun

第 5 章 · 树与二叉树

链表是一维的,树把数据「竖」了起来。这一竖,查找从 O(n) 变成 O(log n) 成为可能,文件系统、数据库索引(第 9 章的 B+ 树就是多叉版)、编译器的语法树、DOM,全是树的形态。本章按「会走 → 会用 → 会平衡」三层推进:先把四种遍历练熟(递归思维的圣地),再学二叉搜索树(树为什么快),最后看两个平衡选手(AVL 管住高度,堆换个姿势二叉)。

5.1 存储:两个指针的孩子

二叉树节点比链表多一个指针:

typedef struct TNode {
    int val;
    struct TNode *left, *right;
} TNode;

全课最优雅的代码模板在这里:任何二叉树问题,先写递归三段式(空树返回什么、处理当前节点、递归左右子树),八成题目当场解掉。

5.2 四种遍历:一棵树的四种读法

遍历顺序典型用途
先序根 → 左 → 右复制树、序列化
中序左 → 根 → 右BST 中序得有序序列
后序左 → 右 → 根释放树、计算依赖
层序一层一层求高度、BFS

前三种的递归写法是三行互换(打印语句的位置决定是哪种):

void inorder(TNode *r) {
    if (!r) return;
    inorder(r->left);       // 先左
    printf("%d ", r->val);  // 中(放最前=先序,最后=后序)
    inorder(r->right);      // 后右
}

层序遍历不用递归,用的是第 3 章的队列:出队一个,访问,把左右孩子入队。队列在这里的角色是「按层排队」,和 DFS 用栈「一条路走到黑」形成分野,这个「BFS 用队列、DFS 用栈」的对偶是图论章的前置知识。遍历的非递归版本(显式栈模拟)是面试常客,写一遍中序非递归,你对「递归 = 隐式栈」的理解会落到实处(计组第 10 章的栈帧,就是那口隐式栈)。

5.3 BST:有序性换来 O(log n)

二叉搜索树给二叉树加了纪律:左子树全部小于根,根小于右子树全部。这条纪律让查找变成「每次丢一半」的猜数字:比根小往左,比根大往右,期望 O(log n):

TNode *insert(TNode *r, int v) {
    if (!r) return new_node(v);
    if (v < r->val)      r->left  = insert(r->left, v);
    else if (v > r->val) r->right = insert(r->right, v);
    return r;                      // 相等:按业务决定拒绝或计数
}

删除是 BST 的精华,三种情况:叶子直接摘;独子让儿子顶替;两个孩子,取中序后继(右子树最左节点,即「比它大的里面最小的」)的值顶上,再去删那个后继(它最多一个右孩子,落回前两种)。这个「找继承人」的思路保证了删除后 BST 的纪律不破。

BST 的软肋在同一行代码里:如果数据恰好递增插入,每次都往右走,树退化成链表,高度 n,一切操作回到 O(n)。有序数据插入 BST 是真实会发生的(按时间戳导入日志),所以需要自动平衡。

5.4 AVL:旋转的艺术

AVL 树在每个节点记平衡因子(左高减右高),插入删除后若某处因子绝对值超过 1,就地旋转修正,硬保证高度 O(log n)。四种失衡用「哪条腿长」记:LL(左子树的左边)和 RR 单旋一次;LR、RL 两次。旋转的图像感比公式重要:

RR 失衡(右腿长),左旋:
      8                12
       \              /  \
        12    →      8    15
       /  \            \
      10   15           10

动手推一次旋转,胜过看十张静态图(推荐去 VisuAlgo 网站拖一遍)。AVL 的性格是「严格」:任何节点失衡立刻修,查找路径最短;代价是插入删除时的旋转次数多。它的近亲红黑树(放宽到「最长路径不超过最短两倍」)旋转少,成了 STL map、Linux CFS(操作系统课第 3 章)、epoll 内部的选择,两种平衡性格对应两种负载,面试问到「为什么内核用红黑树不用 AVL」,答「更新频繁,红黑树调整便宜」就到位了。

5.5 堆:换个目标函数的二叉树

堆放弃「全序」,只要一条:父 ≥ 子(大顶堆),而且必须是完全二叉树(每层从左到右填满)。完全这个约束送出一个大礼:可以用数组存,不用指针!父下标 i,孩子 2i+1 和 2i+2:

void sift_up(int *h, int i) {          // 新元素在末尾,向上浮
    while (i > 0 && h[(i - 1) / 2] < h[i]) {
        int t = h[i]; h[i] = h[(i - 1) / 2]; h[(i - 1) / 2] = t;
        i = (i - 1) / 2;
    }
}

插入 O(log n)(上浮一条路径),取最值 O(1)(就在 h[0]),删除 O(log n)(末尾元素顶上来再下沉)。堆不承诺「中序有序」,它只回答一个问题:当前最大(小)的是谁。这正是优先队列的定义,操作系统的调度队列(第 3 章)、Dijkstra 的「下一个最近的点」(第 6 章)、定时器管理,全是它的用户。堆排序(第 8 章)就是「建堆 + 反复取顶」,原地 O(n log n),那时这章的代码原样复用。

一张决策表收束:要有序遍历和前驱后继,选 BST 系(AVL/红黑树);只要反复取最值,堆更省(数组存储、常数小);要范围查询和磁盘友好,那是第 9 章 B+ 树的故事。

常见错误

  • 递归释放树写成先释放根。后序才能安全 free(先摘叶子再摘根),写成先序 free 完左孩子指针已悬空,直接 use-after-free。
  • BST 删除双孩子时用左子树最大值后忘删原节点。替换值后,「删后继」那一步不能漏,否则树里出现重复键。
  • 堆的数组下标从 0 起还是 1 起混用。从 1 起(父 i/2,孩子 2i、2i+1)公式更整齐,从 0 起(父 (i-1)/2)与 malloc 习惯配套;同一份代码里必须统一,混用就是数组越界。

练习

  1. 实现:BST 删除的完整版本(三种情况 + 递归),然后按顺序插入 5,3,8,1,4,7,9,再删 8,画出每次的树形。
  2. 手算:给序列 [4,2,7,1,3,6] 依次建 BST 和大顶堆,分别画出最终形态;再对两个结构各做一次「取最值」,对比操作过程。
  3. 动手:用 10 万个随机数分别插入 BST 和 AVL(旋转版),统计最终高度;再按有序序列插入 BST,验证退化。这个实验能让你终身记住「平衡」的必要性。
  4. 思考:文件系统目录树是「多叉」的,用「左孩子右兄弟」的技巧可以把它编码成二叉树。画一棵三层的目录树转成二叉树,并想想为什么这个编码不丢失任何信息。
豫ICP备2026027944号