主题
字号
CHAPTER 03 ≈ 53 MIN READ

树与二叉树

3.1 为什么需要树：在「快查」和「快改」之间找平衡

回顾前面线性结构的灵魂矛盾：顺序表查得快（O(1)）但增删慢（O(n)），链表增删快但查得慢（O(n)）。有没有一种结构，查找、插入、删除都能做到不快不慢的 O(log n)，三者兼顾？有，就是树。

树之所以能做到这点，靠的是它的层次分叉结构。想象你查字典：不是从第一页翻到最后一页（那是线性的 O(n)），而是先翻到大概的字母区，再缩小到某几页，再定位——每一步都排除掉一大批不可能的选项。树就是把数据组织成这种「层层分叉、每下一层就砍掉一大片」的形状，于是查找路径长度只和「树有多高」有关，而一棵安排得当的树，n 个节点高度只有 log n 左右。这就是树的全部威力来源：用层次结构把线性的 n 压成对数的 log n。

树同时也是现实世界大量「层次关系」的天然模型：文件系统的目录、公司的组织架构、家谱、书的章节目录、HTML 的标签嵌套——它们都是「一个父亲带多个孩子」的一对多结构。所以树既实用又重要，是这门课最大的考点聚集地。

3.2 树的基本概念与术语（一堆名词，必须分清）

树（Tree） 的定义：n（n≥0）个节点组成的有限集合。当 n=0 时是空树；当 n>0 时，有且仅有一个特殊的节点叫根（root），其余节点又可分成若干个互不相交的子集，每个子集本身又是一棵树，称为根的子树（subtree）。

注意这个定义是递归的——树的子树还是树。这种递归性贯穿整章，树的几乎所有算法都是递归的，因为结构本身就是递归定义的。把这点记牢：树的问题，优先想递归。

下面这堆术语是后面一切的语言，必须一个个搞清楚。配合想象一棵家谱树来记：

学习建议：把上面术语对着一张画出来的树，逐个指认一遍（这是根、这是叶子、这个节点的度是 2、这两个是兄弟、树高是 4……）。术语不熟，后面题目读都读不懂。

3.3 二叉树：为什么单独拎出来讲

一般的树每个节点孩子数不定（有的 3 个有的 5 个），存储和操作都麻烦。二叉树做了一个关键限制：每个节点最多两个孩子，且明确区分「左孩子」和「右孩子」（有序，不能互换）。这个限制看似削弱了能力，实则带来巨大好处——结构规整、便于存储、性质丰富、算法简洁。而且后面会看到，任何普通树/森林都能转换成二叉树，所以研究二叉树就够了。整章 80% 的内容都在二叉树上。

3.3.1 二叉树的定义与五种基本形态

二叉树：n≥0 个节点的有限集合，要么空（n=0），要么由一个根和两棵互不相交的、分别称为左子树和右子树的二叉树组成。同样是递归定义。

有 n 个节点的二叉树，注意「空」也是一种形态。一个节点的二叉树有 5 种基本形态：空树、只有根、只有左子树、只有右子树、左右子树都有。强调「左、右是分开的」——只有左孩子的树和只有右孩子的树是两棵不同的二叉树（这是二叉树「有序」的体现，普通树里这俩没区别）。

3.3.2 两种特殊二叉树（必须分清，性质题的基础）

为什么单独强调完全二叉树？因为它有一个无敌的好性质：可以用数组紧凑存储，且父子节点的下标有简洁公式（见 5.5 和堆）。它是「堆」的结构基础，极其重要。

区分口诀：满二叉树是「每层都满」；完全二叉树是「最后一层可以缺，但只能从右边缺、不能从中间缺」。满一定是完全，完全不一定满。

3.4 二叉树的性质（必背，高频选择/填空）

这几条性质几乎每年必考，要背下来并理解为什么。设节点总数为 n。

性质 1：第 i 层最多有 2^(i-1) 个节点（i≥1）。 理解：第 1 层 1 个（2⁰），第 2 层最多 2 个（2¹），每往下一层节点数最多翻倍，所以第 i 层最多 2^(i-1)。

性质 2：高度为 k 的二叉树最多有 2^k - 1 个节点。 理解：把每层的最大节点数加起来，2⁰ + 2¹ + ... + 2^(k-1) = 2^k - 1（等比数列求和）。取到这个最大值时就是满二叉树。

性质 3（超高频，重点）：叶子节点数 n₀ = 度为 2 的节点数 n₂ + 1，即 n₀ = n₂ + 1。

这条最爱考，必须会推。推导（很经典，理解后忘不掉）：

设度为 0、1、2 的节点数分别是 n₀、n₁、n₂。从两个角度数节点总数和边数：

令两个边数相等：n₁ + 2n₂ = n - 1 = (n₀ + n₁ + n₂) - 1。两边消去 n₁、整理得 n₂ = n₀ - 1，即 n₀ = n₂ + 1。证毕。

性质 4：有 n 个节点的完全二叉树，高度为 ⌊log₂ n⌋ + 1。（⌊⌋ 是向下取整） 理解：完全二叉树尽可能「矮胖」，n 个节点压成最低的高度，约 log₂n。

性质 5（完全二叉树的编号规律，堆的基础，重点）： 对一棵 n 个节点的完全二叉树，从上到下、从左到右按 1 到 n 编号，则对编号为 i 的节点：

这条是用数组存储完全二叉树/堆的根基：节点存在数组下标 i，要找它的孩子和双亲，只需简单乘除，不需要任何指针。后面堆排序全靠它。

这五条性质建议默写到能闭眼写出，特别是性质 3（n₀=n₂+1）和性质 5（2i、2i+1、⌊i/2⌋），是送分点。

3.4.1 性质类填空题的标准套路（必考，照着套）

这类「给几个数求另一个数」的填空/选择题年年考，掌握下面几个套路就能秒杀：

套路一：已知总数求叶子数（用性质 3）。

套路二：完全二叉树「第 i 个节点」相关（用性质 5）。

套路三：已知节点数求高度（用性质 4）。

套路四：满二叉树。 高度 k 的满二叉树：节点数 2^k−1，叶子数 2^(k-1)，第 k 层（最底层）全是叶子。

3.5 二叉树的存储结构

3.5.1 顺序存储（数组）——适合完全二叉树

利用性质 5：把节点按层序编号，编号 i 的节点存在数组下标 i（一般从下标 1 开始用，下标 0 空着，这样 2i、2i+1 的公式才对）。找孩子找双亲全靠下标公式，无需指针，紧凑高效。

但顺序存储有个大问题：只适合完全二叉树。如果是一棵「歪脖子」树（比如只有右孩子的单支树），按编号存进数组会出现大量空洞（编号不连续，中间空的位置也得占着），最坏一棵高度 k 的单支树要开 2^k - 1 大小的数组却只存 k 个节点，浪费惊人。所以普通二叉树一般用链式存储，顺序存储主要用于完全二叉树和堆。

3.5.2 链式存储（二叉链表）——通用方案

每个节点存数据 + 两个指针（指向左孩子、右孩子），这叫二叉链表，是二叉树最常用的存储方式。本章所有遍历、BST、AVL 代码都基于它。

typedef int ElemType;

typedef struct BiTNode {
    ElemType         data;     // 数据域
    struct BiTNode  *lchild;   // 指向左孩子
    struct BiTNode  *rchild;   // 指向右孩子
} BiTNode, *BiTree;            // BiTree = 指向节点的指针,代表一棵(子)树

一个有用的数字：有 n 个节点的二叉链表，一共有 2n 个指针域（每节点 2 个），其中只有 n-1 个用来指向孩子（n 个节点 n-1 条边），剩下 2n - (n-1) = n+1 个指针是空的（NULL）。这 n+1 个空指针「浪费」了——后面「线索二叉树」就是来废物利用这些空指针的。这个「n+1 个空指针」是考点，记住。

若需要频繁找一个节点的「双亲」，可以再加一个 parent 指针，叫三叉链表。看需求选用。

3.6 二叉树的遍历（绝对重点，大题常客）

遍历就是按某种规则，把树里每个节点不重不漏地访问一遍，把立体的树「拍平」成一个线性序列。这是二叉树最核心的操作，后面几乎所有算法（求高度、求节点数、复制树、表达式树……）都是在遍历的框架上改出来的。务必吃透。

二叉树的结构是「根 + 左子树 + 右子树」三部分。遍历无非是决定这三部分的访问顺序。「根」相对于「左、左」的位置有三种选择（左子树永远在右子树前），于是有三种深度优先遍历，外加一种按层走的层序遍历。

3.6.1 前序、中序、后序（看「根」在什么时候被访问）

记忆诀窍：「序」字指的是「根」被访问的时机——前序=根在前，中序=根在中，后序=根在后。左子树永远先于右子树。

每个定义都是递归的（遍历子树时又用同样的规则），所以代码极其简洁，三行核心：

// 前序遍历:根 -> 左 -> 右
void PreOrder(BiTree T) {
    if (T == NULL) return;        // 递归的"出口":空树啥也不做
    visit(T);                     // 访问根(比如打印 T->data)
    PreOrder(T->lchild);          // 递归遍历左子树
    PreOrder(T->rchild);          // 递归遍历右子树
}

// 中序遍历:左 -> 根 -> 右。只是把 visit 挪到中间
void InOrder(BiTree T) {
    if (T == NULL) return;
    InOrder(T->lchild);
    visit(T);
    InOrder(T->rchild);
}

// 后序遍历:左 -> 右 -> 根。把 visit 挪到最后
void PostOrder(BiTree T) {
    if (T == NULL) return;
    PostOrder(T->lchild);
    PostOrder(T->rchild);
    visit(T);
}

看清楚了吗——三个函数代码几乎一模一样，唯一区别是 visit(T) 这句放在三句递归的哪个位置。这就是「序」的含义。把这个对应关系焊死，手算遍历就不会错。

手动求遍历序列（必考，务必练熟）

给一棵画好的二叉树，求它的前/中/后序序列，是必考题。方法就是严格按递归定义在脑子里走。以这棵树为例：

        A
       / \
      B   C
     / \   \
    D   E   F

练习建议：自己多画几棵树，三种序都写一遍，再对照递归定义检查。熟练后看着树能直接「读」出三种序。这是机械送分题。

3.6.2 由遍历序列还原二叉树（高频大题，规律必记）

反过来——给两个遍历序列，唯一确定（还原）出整棵二叉树。这是大题常客。关键规律：

为什么必须有中序？ 因为还原的关键是「找到根，然后分出左右子树两拨节点」。前序的第一个、后序的最后一个都能告诉你根是谁，但只有中序能把节点分成左右两半（中序里根的左边全是左子树节点，右边全是右子树节点）。前序+后序都只能定根、都不能分左右，所以凑一起也分不开，无法唯一确定。

还原方法（以前序+中序为例，递归）：

  1. 看前序的第一个元素 → 它就是整棵树的根。
  2. 在中序里找到这个根 → 它左边的所有元素是左子树的节点，右边的所有元素是右子树的节点。这样就知道左右子树各有几个节点了。
  3. 回到前序：根之后，按上一步数出的左子树节点个数，前面一段是左子树的前序，剩下一段是右子树的前序。
  4. 对左子树（它的前序段+中序段）和右子树（同理）递归做 1-3，直到分完。

走一个完整例子：前序 A B D E C F，中序 D B E A C F，还原：

后序+中序还原同理，只是「根」要看后序的最后一个。考试两种都可能考，方法一致：定根（前序首/后序尾）→ 中序分左右 → 递归。

3.6.3 层序遍历（用队列，重点）

前面三种是「深度优先」（一头扎到底再回头）。层序遍历是「广度优先」——一层一层、从上到下、每层从左到右访问。比如上面那棵树层序是 A B C D E F。

层序遍历不能用递归自然表达，要借助一个队列：

void LevelOrder(BiTree T) {
    if (T == NULL) return;
    Queue Q;                       // 一个能存节点指针的队列
    InitQueue(&Q);
    EnQueue(&Q, T);                // 根入队
    while (!QueueEmpty(&Q)) {
        BiTNode *p;
        DeQueue(&Q, &p);           // 队头出队
        visit(p);                  // 访问它
        if (p->lchild) EnQueue(&Q, p->lchild);   // 它的左孩子入队(若有)
        if (p->rchild) EnQueue(&Q, p->rchild);   // 它的右孩子入队(若有)
    }
}

为什么用队列？ 因为队列 FIFO，保证「先被访问的节点，它的孩子也先被处理」，正好实现「上一层处理完才轮到下一层、左边先于右边」的顺序。这和第 6 章图的 BFS 是同一套机制——层序遍历就是树上的 BFS。记住这个对应。

3.6.4 遍历的应用：树的算法都是遍历的变体

很多树的问题，本质就是「在某种遍历里顺手做点事」。举几个让你建立感觉（思路即可）：

// 例:求二叉树高度。典型的"后序"递归——先求左右子树高度,再合成自己的
int TreeHeight(BiTree T) {
    if (T == NULL) return 0;                 // 空树高 0
    int lh = TreeHeight(T->lchild);          // 左子树高度
    int rh = TreeHeight(T->rchild);          // 右子树高度
    return (lh > rh ? lh : rh) + 1;          // 取较高的 + 自己这一层
}

体会这种「把问题拆成左右子树的子问题，再合并」的递归套路。一旦熟练，绝大多数树的题目你都能现场写出来——这比背具体代码重要得多。

3.6.5 表达式二叉树（中频考点，遍历与表达式的桥梁）

表达式二叉树：把一个算术表达式用二叉树表示——叶子是操作数，内部节点是运算符，运算符的左右子树就是它的两个操作数（子表达式）。例如 a + b * c 对应：

        +
       / \
      a   *
         / \
        b   c

⭐ 核心结论（必考的对应关系）：对表达式二叉树做三种遍历，正好得到三种表达式形式——

遍历 得到 例子（上图）
前序（根左右） 前缀表达式（波兰式） + a * b c
中序（左根右） 中缀表达式（需补括号） a + b * c
后序（左右根） 后缀表达式（逆波兰式） a b c * +

记法：前缀=前序、中缀=中序、后缀=后序，一一对应。这是把「二叉树遍历」和「第2章栈的表达式求值」串起来的关键考点。注意中序遍历得到的中缀式可能丢失优先级信息，所以严格中缀输出时要给每棵子树加括号。

构建（中缀→表达式树）：用双栈法——一个操作数栈（存子树根指针）、一个运算符栈。扫描中缀式：操作数就建一个叶子节点压入操作数栈；运算符按优先级决定是入栈还是先「弹出运算符 + 弹出两个操作数子树、建一棵新子树、压回操作数栈」。规则和第2章「中缀转后缀」完全同构，只是把「输出」换成「建节点」。

求值：对表达式树做后序遍历递归——值 = (左子树的值) 运算符 (右子树的值)，叶子直接返回操作数的值。这就是后缀表达式求值的树形版本。

3.6.6 非递归遍历（了解思路）

前/中/后序也能不用递归，改用一个栈手动模拟系统递归栈（回顾第2章：递归本质就是栈）。比如中序非递归：一路往左走、沿途节点入栈，走到底就弹栈访问、再转向右子树。层序则是用队列（上面已讲）。考试以递归版为主，非递归知道「用栈模拟」这个思路即可，细节用到再深究。

3.7 线索二叉树（废物利用空指针，了解+会画）

3.7.1 动机

回顾 5.5.2：n 个节点的二叉链表有 n+1 个空指针白白浪费。同时，普通二叉树有个不便：知道一个节点，想直接找它在中序序列里的前驱/后继，得重新遍历，很慢。线索二叉树一举解决这两件事：把那些空指针利用起来，指向遍历序列中的前驱或后继，这些指向前驱后继的指针就叫「线索」。

3.7.2 做法

以中序线索二叉树为例：遍历过程中，

但这带来一个问题：现在左/右指针可能指向「孩子」，也可能指向「线索（前驱/后继）」，怎么区分？所以每个节点要额外加两个标志位 ltag、rtag：tag=0 表示该指针指向的是孩子，tag=1 表示指向的是线索。

typedef struct ThreadNode {
    ElemType            data;
    struct ThreadNode  *lchild, *rchild;
    int                 ltag, rtag;   // 0=指向孩子, 1=指向线索(前驱/后继)
} ThreadNode, *ThreadTree;

3.7.3 具体示例：画中序线索二叉树

拿这棵 5 节点树举例：

        A
       / \
      B   C
     / \
    D   E

第一步：写出中序序列（左根右）：D → B → E → A → C

第二步：逐节点检查哪些指针是空的，把空指针改成线索：

节点 左指针 ltag 右指针 rtag
D 中序前驱不存在→NULL（或头节点） 1 中序后继 B 1
B 左孩子 D 0 右孩子 E 0
E 中序前驱 B 1 中序后继 A 1
A 左孩子 B 0 右孩子 C 0
C 中序前驱 A 1 中序后继不存在→NULL（或头节点） 1

一共加了 6 条线索（= n+1 = 5+1，与前面结论吻合）。

画图时：实线箭头画孩子，虚线箭头画线索，序列首节点的左线索和末节点的右线索通常画成指向头节点（一个辅助节点，不存数据）。

3.7.4 找中序前驱/后继的规则（会问）

找中序后继（更常考）：

找中序前驱：

记法：有线索直接读；没线索去对面子树的「极端节点」。

3.7.5 前序 / 后序线索一句话

3.7.6 好处与考点

线索化之后，不用栈、不用递归就能完成遍历，且能 O(1) 找中序前驱/后继。

考点清单（按频率）：

  1. 给一棵树，画出中序线索（最常见，照着上面表格流程来）
  2. 数线索条数（= 空指针数 = n+1）
  3. 问某节点的中序后继是谁（套上面的规则）
  4. 理解 ltag/rtag 的含义
  5. 前序/后序线索（会画即可，不用深究代码）

3.8 二叉搜索树 BST（必考重点）

前面的二叉树只是「形状」，不对数据排列做要求。从这里开始，我们给二叉树加上有序的约束，让它真正变成高效查找的工具。

3.8.1 定义

二叉搜索树（Binary Search Tree，BST，又叫二叉排序树） 是满足以下性质的二叉树——对任意一个节点：

一句话：左 < 根 < 右，且对每个节点都成立。

由这个定义直接推出一条金科玉律：对 BST 做中序遍历（左根右），得到的一定是从小到大的有序序列！ 这是 BST 最重要的性质，反复用、必考。理由：中序是「左→根→右」，而 BST 恰好「左<根<右」，走出来自然递增。

3.8.2 查找（像二分一样高效）

在 BST 里找一个值 key，从根开始：key 比当前节点小就往左子树走，比它大就往右子树走，相等就找到了，走到空还没找到就是不存在。每一步都排除掉一棵子树，跟二分查找一个道理。

// 在 BST 中查找值 key,返回所在节点指针,找不到返回 NULL
BiTNode *BSTSearch(BiTree T, ElemType key) {
    while (T != NULL && T->data != key) {
        if (key < T->data) T = T->lchild;    // 目标更小,去左子树
        else               T = T->rchild;    // 目标更大,去右子树
    }
    return T;                                 // 找到则返回该节点,否则 T 已是 NULL
}

复杂度：每比较一次就下降一层，所以查找次数 = 走过的路径长度，最多等于树的高度。如果树比较「平衡」（左右均匀），高度约 log₂n，查找 O(log n)，非常快。但——见 5.8.5 的坑。

3.8.3 插入

插入一个新值，本质就是「先按查找的规则走，走到空位置（NULL）就把新节点接在那」。新节点总是作为叶子插入。

int BSTInsert(BiTree *T, ElemType key) {   // 注意 BiTree *T:要修改树(可能改根),传指针的指针
    if (*T == NULL) {                       // 走到空位置:新建节点放这
        *T = (BiTNode *)malloc(sizeof(BiTNode));
        (*T)->data = key;
        (*T)->lchild = (*T)->rchild = NULL;
        return 1;
    }
    if (key == (*T)->data) return 0;        // 已存在,不重复插
    if (key < (*T)->data)
        return BSTInsert(&(*T)->lchild, key);   // 递归插到左子树
    else
        return BSTInsert(&(*T)->rchild, key);   // 递归插到右子树
}

注意插入顺序会影响树的形状——同样一组数，按不同顺序插入，建出来的 BST 长得不一样（这点是 5.8.5 退化问题的根源）。

3.8.4 删除（分三种情况，必考！）

删除是 BST 最难、最爱考的操作，因为删掉一个节点后还要保持「左<根<右」的性质。分三种情况，务必记牢：

情况一：被删节点是叶子（没有孩子）。 直接删掉，把它双亲指向它的指针置空即可。最简单。

情况二：被删节点只有一个孩子（左或右）。 让它的那个孩子顶替它的位置（直接接到它双亲下面），相当于「越级提拔」。因为只有一个孩子，提上来不会破坏有序性。

情况三：被删节点有两个孩子（最麻烦，重点）。 不能简单删，因为它走了会留下两个孩子无处安放。做法是找一个替身来顶替它的值，然后转化成删除那个替身。替身只能是这两个之一（这样替换后仍满足左<根<右）：

具体步骤：找到中序后继（或前驱）→ 把它的值复制到被删节点（值替换，节点不动）→ 然后去删除那个后继（前驱）节点。而那个后继/前驱节点必然最多只有一个孩子（它是某子树的最左/最右端），所以转化成了情况一或情况二，可以直接删。

为什么用中序前驱/后继当替身？因为它们是「最接近被删值的、紧挨着的数」，用它顶上来，能保证整棵树仍然满足 BST 的有序性（它比左子树都大、比右子树都小，正好接班）。

删除双子节点的两种策略（课件点名，简答可能问）

情况三（被删节点有两个孩子）其实有两种课本写法，名字常考，要分清：

两种策略删同一个节点，得到的树形状可能不同，但都合法。考试默认用复制删除画图；若题目或老师强调「连接/合并删除」，按上面拼接法走。

删除三种情况的完整画图演示

拿这棵 BST 当例子，三种删除都演示一遍（先按 50,30,70,20,40,60,80,65 依次插入得到）：

            50
          /    \
        30      70
       /  \    /  \
      20  40  60   80
              \
              65

删叶子 20（情况一）：20 没有孩子，直接摘掉，30 的左指针置空。

       50                    50
      /  \      删20         /  \
    30    70    ───→       30    70
    /\   / \                \   / \
   20 40 60 80              40 60  80
        \                      \
        65                     65

删只有一个孩子的 60（情况二）：60 只有右孩子 65，让 65 直接顶替 60 的位置（接到 70 的左边）。

      70                  70
     /  \      删60       /  \
   60    80    ───→     65    80
    \
    65

删有两个孩子的 30（情况三）：30 有左孩子 20、右孩子 40。找它的中序后继——右子树 40 里最小的（40 无左孩子，所以后继就是 40）；把 40 的值复制到 30 的位置，再删掉原来的 40（它是叶子，按情况一删）。

        50                      50
       /  \       删30          /  \
     30    70     ───→        40    70    （30 的位置被后继 40 顶替）
    /  \                      /
   20   40                   20

也可以用中序前驱（左子树 20 里最大的，这里是 20）替换，结果是另一棵合法 BST。两种都对。考试关键：① 判断属于哪种情况；② 情况三正确找到后继（右子树最左）或前驱（左子树最右）。

考点：给一棵 BST 和要删的值，画出删除后的树。三种情况都要会，尤其情况三要会找后继/前驱替身。多画几遍。

3.8.5 BST 的致命弱点：退化（引出平衡树的动机）

BST 的 O(log n) 是有前提的——树得长得均匀。但如果你按有序顺序插入（比如依次插入 1,2,3,4,5），会发生什么？1 当根，2 比 1 大放右边，3 比 2 大放 2 的右边……结果整棵树变成一条只往右伸的斜线，退化成了一个链表！此时查找要从头走到尾，O(n)，和链表一样慢，BST 的优势荡然无存。

这就是 BST 的致命弱点：形状依赖插入顺序，最坏会退化成链表。 怎么办？我们需要一种能在插入删除时自动保持平衡（不让它长歪）的 BST——这就是下一节的平衡二叉树 AVL。理解这个「为什么需要 AVL」的动机，比记 AVL 的旋转更重要。

3.9 平衡二叉树 AVL（高频，旋转必考）

3.9.1 动机与定义

为了防止 BST 退化，AVL 树（发明者 Adelson-Velsky 和 Landis 的缩写）给 BST 加了一条平衡约束：任意节点的左子树高度和右子树高度之差，绝对值不超过 1。

定义平衡因子（Balance Factor, BF）= 该节点左子树高度 − 右子树高度。则 AVL 树里每个节点的平衡因子只能是 −1、0、+1 三者之一。一旦插入/删除导致某个节点的平衡因子变成 +2 或 −2，就「失衡」了，必须通过旋转把它转回平衡。AVL 保证树高始终维持在 O(log n)，从而查找/插入/删除都稳定 O(log n)。

⭐ 高度为 h 的 AVL 树最少有多少个节点（必考填空）

这是 AVL 的经典填空题，结论和推导都要会。设高度为 h 的 AVL 树最少节点数为 N(h)。要让节点尽量少又保持平衡，就让左右子树高度差恰好为 1、且各自都是「最少节点的 AVL 树」，于是得到递推：

N(h) = N(h-1) + N(h-2) + 1        （左子树高 h-1、右子树高 h-2，再加根自己）
边界：N(0) = 0（空树）, N(1) = 1, N(2) = 2

逐项算出（必背前几项）：

h 0 1 2 3 4 5 6
N(h) 最少节点 0 1 2 4 7 12 20

这个递推和斐波那契几乎一样（N(h)=N(h-1)+N(h-2)+1，比斐波那契多个 +1）。典型考法：「高度为 4 的 AVL 树至少有几个节点？」→ 答 7。或反过来「n 个节点的 AVL 树最大高度是多少」，用上表反查。

3.9.2 失衡的四种情况与对应旋转（核心考点）

当插入一个新节点导致失衡时，从插入点往上找到第一个失衡的节点（平衡因子变成 ±2 的、离插入点最近的祖先），记为 A。根据新节点插在 A 的哪个方位，分四种情况，对应四种旋转。命名规则：两个字母分别表示「失衡是由 A 的哪一侧、那一侧的哪一侧」造成的。

① LL 型（左孩子的左子树插入导致）→ 右旋（单旋） 新节点插在 A 的左孩子的左子树里。处理：以 A 为轴向右旋转——A 的左孩子 B 上来当根，A 下去当 B 的右孩子，B 原来的右子树挂到 A 的左边。

② RR 型（右孩子的右子树插入导致）→ 左旋（单旋） LL 的镜像。新节点插在 A 的右孩子的右子树里。处理：以 A 为轴向左旋转——A 的右孩子上来当根，A 下去当它的左孩子。

③ LR 型（左孩子的右子树插入导致）→ 先左旋再右旋（双旋） 新节点插在 A 的左孩子的右子树里。这种「拐了个弯」的失衡单旋转不好使，要两步：先对 A 的左孩子做一次左旋（把它捋直成 LL 型），再对 A 做一次右旋。

④ RL 型（右孩子的左子树插入导致）→ 先右旋再左旋（双旋） LR 的镜像。新节点插在 A 的右孩子的左子树里。先对 A 的右孩子右旋，再对 A 左旋。

记忆口诀：LL 右旋、RR 左旋（单旋，方向和名字相反）；LR、RL 是双旋（先把它捋成单旋情况，再旋）。 双旋的第一步永远是处理「拐弯」的那个孙子，把它变成和儿子同方向。

3.9.3 四种旋转的图示

先把四种旋转各画一遍，看懂「轴」怎么转。下面 A 是失衡节点，新插入的节点用 ★ 标。

① LL → 右旋（A 的左孩子 B 上位，A 降为 B 的右孩子，B 的原右子树 βγ 挂到 A 左边）：

      A(BF=2)              B
     /                    / \
    B           ─右旋→   ★   A
   / \                       /
  ★   βγ                   βγ

② RR → 左旋（LL 的镜像，A 的右孩子上位）：

   A(BF=-2)                B
      \                   / \
       B        ─左旋→   A   ★
      / \                 \
    βγ   ★                βγ

③ LR → 先左旋（对 B）再右旋（对 A）：新节点插在左孩子 B 的右子树 C 上。先把 B 左旋（C 上来替 B），变成 LL，再对 A 右旋。最终是孙子 C 上位当根，B、A 分别成它的左右孩子。

     A              A             C
    /              /             / \
   B    ─左旋B→   C    ─右旋A→   B   A
    \            /
     C          B

④ RL → 先右旋（对 B）再左旋（对 A）：LR 的镜像，同样是孙子上位，结果对称。

单旋是「儿子上位」，双旋是「孙子上位」——这个区别记住就不会画错。

3.9.4 完整插入序列演示（必考大题，跟着画一遍）

题目：依次插入 3, 2, 1, 4, 5, 6, 7，画出 AVL 树的演变。

插3:        3                （只有一个节点，平衡）

插2,1:      3                2(BF=2,LL型)            2
           /     插1后→     /          右旋3→       / \
          2               2                        1   3
                         /
                        1
            ↑ 插入 1 时，节点 3 失衡(BF=2)，是 LL 型 → 对 3 右旋
            得到平衡树:   2
                        / \
                       1   3

插4:        2          插4后 3 的右边来了 4，仍平衡
           / \
          1   3
               \
                4

插5:        2(还平衡)        3 失衡(BF=-2,RR型)         2
           / \              对 3 左旋 →               / \
          1   3                                      1   4
               \                                        / \
                4                                      3   5
                 \
                  5
            ↑ 插 5 时节点 3 失衡(RR) → 左旋 3，4 上位
            得到:        2
                       / \
                      1   4
                         / \
                        3   5

插6:        2(BF=-2!根失衡,RR型)        4
           / \                        / \
          1   4          对2左旋→     2   5
             / \                     / \   \
            3   5                   1   3   6
                 \
                  6
            ↑ 插 6 后，根节点 2 失衡(BF=-2，RR型) → 对 2 左旋，4 成为新根
            得到:        4
                       / \
                      2   5
                     / \   \
                    1   3   6

插7:        4              5 失衡(BF=-2,RR型)        4
           / \             对5左旋→                / \
          2   5                                    2   6
         / \   \                                  / \ / \
        1   3   6                                1  3 5  7
                 \
                  7
            ↑ 插 7 后节点 5 失衡(RR) → 左旋 5，6 上位
            最终 AVL 树:      4
                           /   \
                          2     6
                         / \   / \
                        1   3 5   7   （完美平衡）

做题流程总结：

  1. 按 BST 规则插入每个数。
  2. 每插一个，从插入点往上回溯检查平衡因子。
  3. 一旦发现某节点失衡（±2），找到那个最近的失衡节点 A，判断 LL/RR/LR/RL，做对应旋转。
  4. 旋转后该子树恢复平衡，继续插下一个。

这是纯机械的送分大题。上面这个例子建议你自己再独立画一遍对答案。多练几个不同序列（特别是会触发 LR、RL 双旋的，比如插入 3,1,2 是 LR、1,3,2 是 RL），做到看一眼失衡类型就知道怎么转。

3.9.5 其它平衡/多路查找树（按大纲了解）

3.10 哈夫曼树（Huffman，必考）

3.10.1 动机：让常用的东西「路径最短」

哈夫曼树解决的是最优编码/压缩问题。直觉是：英文里 e、a 这种字母出现频率极高，z、q 极低。如果给所有字母都用等长编码（比如都 8 位），太浪费。何不给高频字母用短编码、低频字母用长编码，整体就能压缩。哈夫曼树就是用来构造这种「最优」编码方案的。

更一般地，哈夫曼树解决的是「带权路径长度最小」的树。给每个叶子一个权值（可理解为出现频率/重要性），我们希望权值大的叶子离根近（路径短）、权值小的离根远，使得整棵树的带权路径长度 WPL 最小。这样的树就是哈夫曼树（最优二叉树）。

WPL（Weighted Path Length，带权路径长度）= 所有叶子节点的（权值 × 它到根的路径长度）之和。 路径长度指从根到该叶子经过的边数（根到自己是 0）。WPL 越小越优。

3.10.2 构造算法（贪心，必考会手算）

每次都把当前权值最小的两个合并——这是贪心思想。步骤：

  1. 把所有给定权值各看成一个只有一个节点的树，放进一个集合。
  2. 从集合里取出权值最小的两棵树，合并成一棵新树：新建一个根，左右孩子就是这两棵树，新根的权值 = 两棵子树权值之和。
  3. 把这棵新树放回集合。
  4. 重复 2-3，直到集合里只剩一棵树——它就是哈夫曼树。

走一个例子：给字符 A B C D，权值（频率）{7, 5, 2, 4}。

合并过程：

得到的哈夫曼树（左0右1）：

              18
            0/  \1
            A    11          ← A 在第 1 层下，路径长 1
           (7) 0/  \1
                B    6        ← B 路径长 2
               (5) 0/ \1
                   C   D      ← C、D 路径长 3
                  (2) (4)

WPL 计算 = Σ(权值 × 路径长) = 7×1 + 5×2 + 2×3 + 4×3 = 7 + 10 + 6 + 12 = 35。

注意：哈夫曼树不唯一（合并时若有相等权值，选哪两个、谁左谁右都可能不同），但WPL 是唯一确定的最小值。考试算 WPL 一定对，画出来的树形状可能和标答略有不同但 WPL 相同，一般都给分。

3.10.3 哈夫曼编码（前缀码，必考）

构造好哈夫曼树后，给每条边标号：指向左孩子的边标 0，指向右孩子的边标 1（左0右1是约定，反过来也行，统一即可）。则从根到每个叶子的路径上的 0/1 序列，就是该叶子（字符）的哈夫曼编码。高频字符离根近、编码短，正是我们要的。

接着上面 {A:7, B:5, C:2, D:4} 那棵树，从根到各叶子的路径读出编码：

字符 路径（左0右1） 编码 码长
A 左 0 1
B 右左 10 2
C 右右左 110 3
D 右右右 111 3

可以验证 WPL（=编码总长）= 7×1 + 5×2 + 2×3 + 4×3 = 35，正是前面算的 WPL——WPL 的数值就是用这套编码压缩后的总位数，这解释了为什么 WPL 最小 = 压缩最优。高频的 A 只用 1 位，低频的 C、D 才用 3 位。

解码示范：收到 0 10 0 110，从根按位走树：0→A，10→B，0→A，110→C，解出 ABAC。全程不会有歧义。

哈夫曼编码有个关键性质：它是前缀码（前缀编码）——任何一个字符的编码，都不是另一个字符编码的前缀（看上表：0、10、110、111，没有谁是谁的开头）。为什么？因为所有字符都在叶子上，而从根到任一叶子的路径不可能是到另一叶子路径的「前一段」（叶子之间没有祖先后代关系）。前缀码保证了解码无歧义：一长串 0/1 拼起来，从头按位走树，走到叶子就解出一个字符、回到根继续，绝不会搞混。这是哈夫曼编码能用的根本保证。

3.10.4 考点总结与易错点

给一组权值（或字符频率）：① 构造哈夫曼树；② 计算 WPL；③ 写出每个字符的哈夫曼编码；④ 可能给一段编码让你解码。原理都在上面，多算两个例子即可熟练。

⚠️ 判断题易错点（高频）：

速算 WPL 的小技巧：不用读每个叶子的层数，WPL = 构造过程中所有「合并产生的新节点权值」之和。如 5.10.2 的例子，合并产生 6、11、18，6+11+18 = 35，正好等于 WPL。考试用这个验算又快又准。

3.11 B 树 / B+ 树（数据库相关，按大纲了解）

3.11.1 动机

前面的 BST/AVL 是「二叉」的，每个节点最多两个孩子。当数据量极大、必须存在磁盘上时，二叉树会很「高」（log₂n 层），而每下一层往往要读一次磁盘（磁盘 IO 极慢，是内存的成千上万倍）。树越高，IO 次数越多，性能就崩了。

B 树的思路：让每个节点存很多个键、有很多个孩子（多路），把树压得「又矮又胖」，从而大幅减少层数、减少磁盘 IO。这是数据库索引和文件系统的核心结构。

3.11.2 要点（了解）

考试对 B/B+ 树通常只要求理解动机（减少磁盘 IO）、知道「多路、矮胖、B+ 数据全在叶子且叶子成链」这些特征即可。具体的插入分裂、删除合并操作，按你们大纲深浅决定要不要细抠。

3.12 堆与优先队列（重要，连接排序）

3.12.1 什么是堆

堆（Heap） 是一种特殊的完全二叉树，满足堆序性：

注意堆只要求父子之间有序，不要求兄弟之间或左右子树整体有序（这点和 BST 不同，别混）。所以堆不是用来「查找任意值」的，它的拿手好戏是快速取出最大（或最小）值——根就是，O(1) 看到，O(log n) 取走并恢复。

3.12.2 堆为什么用数组存

因为堆是完全二叉树，正好套用 5.4 的性质 5！用一个数组（从下标 1 开始）按层序存，则：

无需任何指针，纯数组+下标运算，又快又省。这是堆高效的关键。

3.12.3 两个核心操作：上浮与下沉

3.12.4 建堆与堆排序（第5章会再用）

3.12.5 优先队列

回顾第 3 章提到的优先队列——出队的总是「优先级最高」的元素。堆正是它的高效实现：用大顶堆，取最大就是 O(log n) 出队，插入 O(log n)。操作系统调度、Dijkstra 优化、哈夫曼构造，底层都可以用堆做优先队列。

3.13 树、森林与二叉树的转换（了解）

前面说过「研究二叉树就够了，因为普通树/森林都能转成二叉树」。转换规则叫「左孩子右兄弟」表示法：

考点：会做树↔二叉树、森林↔二叉树的相互转换（画图），理解「左孩子右兄弟」规则。次重点，知道方法即可。

3.14 并查集（Union-Find，图章节会用到）

3.14.1 动机

有些问题反复问：「这两个元素是不是属于同一组（同一个集合/连通块）？」以及「把这两组合并成一组」。比如判断社交网络里两个人是否间接相连、Kruskal 算法里判断加一条边会不会成环。并查集就是专门高效干这两件事的结构。

3.14.2 两个操作

3.14.3 实现思路

用一个数组 parent[]，parent[x] 表示 x 的「父亲」。每个集合组织成一棵树，根的父亲是自己。Find 就是顺着 parent 一路往上找到根；Union 就是把一棵树的根挂到另一棵树的根下面。

int parent[MAXN];
void Init(int n) { for (int i = 0; i < n; i++) parent[i] = i; }  // 初始each自成一组

int Find(int x) {                       // 找根(代表元)
    while (parent[x] != x) x = parent[x];
    return x;
}
void Union(int x, int y) {              // 合并
    int rx = Find(x), ry = Find(y);
    if (rx != ry) parent[rx] = ry;      // 把 x 的根挂到 y 的根下
}

3.14.4 优化（让它快到几乎 O(1)）

两个优化一起用，单次操作的均摊复杂度接近常数 O(α(n))（α 是增长极慢的反阿克曼函数，实际可看作 O(1)）。

3.14.5 应用

判断图的连通分量、Kruskal 最小生成树里判环（加边前看两端点是否已在同一组，若是则加这条边会成环、跳过）。第 6 章会用到，记住它的两个操作和用途。

3.15 树与二叉树自测

  1. 树的「度」是什么？叶子节点、分支节点的区别？森林是什么？
  2. 满二叉树和完全二叉树的区别？完全二叉树为什么适合用数组存？
  3. 默写二叉树性质 3（n₀ 和 n₂ 的关系）并推导它。
  4. 完全二叉树里节点 i 的左孩子、右孩子、双亲编号公式？
  5. n 个节点的二叉链表有多少个空指针？这引出了什么结构？
  6. 前/中/后序遍历的定义？三段代码的唯一区别是什么？
  7. 给一棵树（自己画），写出它的前中后序和层序。
  8. 为什么前序+中序能还原树，前序+后序不能？还原的关键步骤？
  9. 层序遍历用什么数据结构？为什么？
  10. BST 的定义？为什么中序遍历 BST 得到升序序列？
  11. BST 删除节点的三种情况分别怎么处理？情况三的替身怎么找？
  12. BST 会在什么情况下退化成链表？这引出了什么？
  13. AVL 的平衡因子定义？四种失衡（LL/RR/LR/RL）各对应什么旋转？
  14. 哈夫曼树怎么构造？什么是 WPL？给权值 {1,2,3,4,5} 构造并算 WPL。
  15. 为什么哈夫曼编码是前缀码？前缀码有什么好处？
  16. 堆是什么？大顶堆的根是什么？堆为什么能用数组存？建堆的复杂度？
  17. 并查集的两个操作和典型应用？