第5章树与二叉树（自学增强版）¶

章节定位：树结构主干章

这一章承接线性结构之后的层次化组织方式，是树、二叉树、哈夫曼树和并查集的集中入口。
建议优先吃透二叉树遍历、线索二叉树和树森林转换，再回头做应用题和代码阅读。

1. 本章定位¶

这一章是整本书里真正“从线性走向层次”的转折点。
如果说前面的线性表、栈、队列，核心是“排成一条线”；那么这一章开始，数据之间的关系不再只是前后，而是父子、祖先、兄弟、层次、分支。

所以这章难，不是因为公式多，而是因为思维方式变了：

线性结构是“一路往后看”。
树形结构是“从一个点分出很多方向”。

这一章也是考研数据结构里非常核心的一章：

树的基本概念会进选择题。
二叉树遍历会进选择题，也可能直接进算法题。
线索二叉树、树与森林转换、哈夫曼树、并查集，都属于高频考点。

2. 学习目标¶

学完本章后，你应该能做到：

说清楚树、森林、结点的度、树的度、层次、深度、高度、祖先、子孙这些概念。
理解二叉树为什么不是“度为 2 的树”那么简单。
分清满二叉树、完全二叉树以及一般二叉树的性质。
会写二叉树的先序、中序、后序、层序遍历。
会在遍历基础上做统计类和改造类算法。
理解线索二叉树是在解决什么问题。
看懂树、森林与二叉树之间的转换关系。
理解哈夫曼树、哈夫曼编码、并查集这些应用结构的核心思想。

3. 本章结构总览¶

第 5 章可以按下面这条主线来理解：

先认识一般树的概念和性质。
再把注意力收缩到更重要的“二叉树”。
接着学习二叉树遍历，因为遍历是后面几乎所有算法的基础。
再看树、森林与二叉树之间如何互相转换。
最后看应用：哈夫曼树、并查集、堆。

如果把这章讲成一句话，那就是：

先搞清树长什么样，再学怎么走，最后学怎么用。

4. 5.1 树的基本概念¶

4.1 树的定义¶

树是 n (n >= 0) 个结点的有限集。

当 n = 0 时，称为空树。
当树非空时，有且仅有一个根结点。
其余结点可以分成若干个互不相交的子树。

这里最关键的一点是：

树的定义本身就是递归的。

因为：

一棵树由若干棵子树组成。
每棵子树本身又是一棵树。

这也是为什么树相关算法特别适合递归。

4.2 树适合表示什么¶

树最适合表示“有分支层次关系”的数据。

例如：

文件夹目录
组织架构
家谱
编译语法树
网页 DOM 结构

这类数据的共同点是：

有根
有层次
一个结点下面可以带多个后继

4.3 基本术语¶

这一部分不建议死背，而建议结合图去理解。

4.3.1 双亲、孩子、兄弟¶

一个结点的直接上层结点叫双亲。
一个结点的直接下层结点叫孩子。
拥有相同双亲的结点互为兄弟。

4.3.2 祖先、子孙¶

从根到某结点路径上的所有前驱结点，都是它的祖先。
某结点子树中的所有结点，都是它的子孙。

4.3.3 结点的度与树的度¶

一个结点的度：它的孩子个数。
一棵树的度：整棵树中所有结点度的最大值。

4.3.4 叶结点与分支结点¶

度为 0 的结点叫叶结点。
度大于 0 的结点叫分支结点。

4.3.5 层次、深度、高度¶

这几个词最容易混。

结点层次：从根开始数，第几层。
结点深度：通常等于它所在层次。
结点高度：以这个结点为根的子树高度。
树的高度：整棵树的最大层数。

一句话记忆：

深度是“从上往下看你在第几层”
高度是“从你往下看还能撑多高”

4.3.6 路径与路径长度¶

路径：两个结点之间经过的结点序列。
路径长度：路径上边的条数。

注意树中的路径默认是从上往下的。

4.4 树的性质¶

性质1：树中结点数与边数¶

在一棵有 n 个结点的树中，边数一定是：

n - 1

为什么？

除根结点外，每个结点都有且仅有一个双亲。
每个非根结点都恰好对应一条来自双亲的边。
所以总边数就是非根结点数，也就是 n - 1。

性质2：所有结点度数之和¶

树中所有结点的度数之和，等于边数总和，所以也等于：

n - 1

这条性质特别重要，因为很多题目都用它列方程。

性质3：m 叉树第 i 层最多有多少结点¶

度为 m 的树，第 i 层最多有：

m^(i - 1)

这和满二叉树每层最多有 2^(i-1) 个结点是同一类思想。

性质4：高度与结点数的上下界¶

树的高度最小，意味着每层尽量满。
树的高度最大，意味着每层尽量瘦。

这类题的本质就是：

最小高度：让树尽量“胖”
最大高度：让树尽量“瘦”

5. 5.2 二叉树的概念¶

5.1 二叉树的定义¶

二叉树是每个结点至多只有两棵子树的有序树，并且这两棵子树有左右之分。

关键词有两个：

至多两棵
左右有别

这意味着：

一个结点可以没有孩子。
可以只有左孩子。
可以只有右孩子。
可以同时有左右孩子。

5.2 二叉树为什么不等于“度为 2 的树”¶

这是选择题特别爱考的点。

区别在于：

度为 2 的树至少有 3 个结点，而二叉树可以为空。
一般树中如果某结点只有一个孩子，不必强调它是“左”还是“右”。
二叉树中哪怕只有一个孩子，也必须区分左孩子还是右孩子。

所以：

二叉树不是“孩子数最多为 2”这么简单。
它本质上还是一种有序结构。

5.3 特殊二叉树¶

5.3.1 满二叉树¶

如果一棵二叉树每一层都达到最大结点数，那么它就是满二叉树。

它的特点：

所有分支结点度都为 2
所有叶子都在同一层

5.3.2 完全二叉树¶

完全二叉树可以理解成：

在相同高度下，尽量像满二叉树，只允许最底层右边缺一些结点。

它的典型性质：

叶子只可能出现在最后两层
若有度为 1 的结点，最多只有一个，且只有左孩子
按层序编号后，编号大的结点不会跑到前面去“插空”

5.3.3 顺序存储时的编号关系¶

如果按层序从 1 开始编号：

结点 i 的双亲是 floor(i / 2)
左孩子是 2i
右孩子是 2i + 1

这就是为什么完全二叉树特别适合顺序存储。

6. 5.3 二叉树的遍历¶

6.1 为什么遍历是本章核心¶

很多树算法表面不同，本质其实都是：

按某种次序访问所有结点
在访问过程中顺手做统计、判断、修改

所以遍历就是树算法的“母模板”。

6.2 三种深度优先遍历¶

设：

N 表示根
L 表示左子树
R 表示右子树

则有：

先序：NLR
中序：LNR
后序：LRN

区分方法不要死背字母，而要看：

根结点是在左子树和右子树之间的哪个时刻被访问的

6.3 层序遍历¶

层序遍历不是递归优先，而是按层从上往下、从左往右访问。
它最自然的实现方式是队列。

因为：

先访问的上层结点
需要先把它的孩子排到后面
这正好符合先进先出

6.4 原书伪代码与真实代码对照：先序遍历¶

原书思路版伪代码¶

PreOrder(T)
if T != NULL
    visit(T)
    PreOrder(T->lchild)
    PreOrder(T->rchild)

对应真实代码¶

void PreorderTraversal(BiTree tree) {
    if (tree == NULL) {
        return;
    }

    VisitNode(tree);
    PreorderTraversal(tree->lchild);
    PreorderTraversal(tree->rchild);
}

这段代码的位置在：

第5章普通代码版（约第118行）

理解重点¶

空树直接返回，这是递归出口。
根先访问，所以叫先序。
后面只是把同样的规则递归地作用到左右子树上。

6.5 原书伪代码与真实代码对照：中序遍历¶

原书思路版伪代码¶

InOrder(T)
if T != NULL
    InOrder(T->lchild)
    visit(T)
    InOrder(T->rchild)

对应真实代码¶

void InorderTraversal(BiTree tree) {
    if (tree == NULL) {
        return;
    }

    InorderTraversal(tree->lchild);
    VisitNode(tree);
    InorderTraversal(tree->rchild);
}

源码位置：

第5章普通代码版（约第129行）

中序最特别的地方是：

根在中间

这也是为什么在二叉搜索树里，中序遍历能得到有序序列。

6.6 原书伪代码与真实代码对照：后序遍历¶

原书思路版伪代码¶

PostOrder(T)
if T != NULL
    PostOrder(T->lchild)
    PostOrder(T->rchild)
    visit(T)

对应真实代码¶

void PostorderTraversal(BiTree tree) {
    if (tree == NULL) {
        return;
    }

    PostorderTraversal(tree->lchild);
    PostorderTraversal(tree->rchild);
    VisitNode(tree);
}

源码位置：

第5章普通代码版（约第140行）

后序最适合做的事包括：

删除整棵树
先处理子树，再处理根的场景

6.7 层序遍历：伪代码与真实代码¶

原书思路版伪代码¶

LevelOrder(T)
初始化队列 Q
若 T 非空，则根结点入队
while Q 非空
    出队一个结点 p
    visit(p)
    若 p 有左孩子，左孩子入队
    若 p 有右孩子，右孩子入队

对应真实代码¶

void LevelOrderTraversal(BiTree tree) {
    BiTreeQueue queue;
    BiTree current;

    if (tree == NULL) {
        return;
    }

    InitBiTreeQueue(&queue);
    EnqueueBiTree(&queue, tree);

    while (!IsBiTreeQueueEmpty(&queue)) {
        DequeueBiTree(&queue, &current);
        VisitNode(current);

        if (current->lchild != NULL) {
            EnqueueBiTree(&queue, current->lchild);
        }
        if (current->rchild != NULL) {
            EnqueueBiTree(&queue, current->rchild);
        }
    }
}

源码位置：

第5章普通代码版（约第151行）

理解重点：

队列保证“先到上一层，再到下一层”
左右孩子入队的先后顺序，决定同层中从左到右的访问顺序

7. 遍历基础上的高频算法¶

二叉树考算法题时，经常不是让你“纯遍历”，而是让你“在遍历过程中顺手做事”。

本章代码里已经落地了几类高频操作：

统计结点总数：第5章普通代码版（约第174行）
统计叶子个数：第5章普通代码版（约第182行）
统计度为 1 的结点个数：第5章普通代码版（约第193行）
统计度为 2 的结点个数：第5章普通代码版（约第205行）
求二叉树高度：第5章普通代码版（约第217行）
查结点所在层次：第5章普通代码版（约第234行）
交换左右孩子：第5章普通代码版（约第257行）

这些函数的共同点是：

递归框架几乎一样
差别只在“访问当前结点时你做什么事”

这就是你真正要学会的：

不是死记 10 个函数
而是看懂“遍历模板 + 当前处理动作”的组合关系

8. 5.3.2 线索二叉树¶

这一部分在本章里概念很重要，但初学时最容易绕。

8.1 为什么需要线索二叉树¶

普通二叉链表有很多空指针域。
这些空指针如果直接浪费掉，会丢失很多“遍历关系信息”。

线索二叉树的思路就是：

把原来空着的左指针，改指向某种遍历下的前驱
把原来空着的右指针，改指向某种遍历下的后继

这样做的目的，是让某些遍历或前驱后继查找更方便。

8.2 这一节最该掌握什么¶

初学阶段先抓这两点：

线索不是“新的孩子关系”，而是“借空指针补充遍历关系”
中序线索二叉树最常考，也最基础

这一部分我在第 5 章后续加厚时，会专门再展开成细讲版。

9. 5.4 树、森林与二叉树的转换¶

这部分的核心不是背结论，而是理解“左孩子右兄弟”。

9.1 为什么树能转成二叉树¶

一般树一个结点可能有很多孩子，二叉树一个结点最多两个孩子。
那怎么转？

办法是：

第一个孩子保留成左孩子
同一层的兄弟改用右孩子串起来

这就是著名的：

左孩子右兄弟表示法

9.2 对应关系¶

转换后：

树的先根遍历，对应二叉树的先序遍历
树的后根遍历，对应二叉树的中序遍历

这两个对应关系很容易进选择题。

10. 5.5 树与二叉树的应用¶

10.1 哈夫曼树¶

哈夫曼树的关键词不是“二叉树”，而是：

带权路径长度 WPL 最小

也就是说：

权大的叶子尽量靠近根
权小的叶子可以更深一些

构造过程的核心规则是：

每次从当前森林中选权值最小的两棵树
合并成一棵新树
新根权值等于两棵子树根权值之和

本章真实代码¶

我已经把哈夫曼树的基础构造落成真实 C 代码：

选择最小两棵树：第5章普通代码版（约第341行）
构造哈夫曼树：第5章普通代码版（约第370行）
计算 WPL：第5章普通代码版（约第408行）
打印数组结构：第5章普通代码版（约第431行）

当前代码里已经用权值集合：

{5, 2, 3, 6, 8, 9}

构造并验证出了：

Huffman WPL = 81

10.2 并查集¶

并查集本质上是在维护：

若干个互不相交集合的合并与查找

它最经典的两个操作是：

Find：查某个元素属于哪个集合
Union：把两个集合合并起来

为什么它放在这章？

因为它底层常用“树形关系”来表示集合归属。

本章真实代码¶

当前已经落地：

初始化并查集：第5章普通代码版（约第286行）
查找根结点：第5章普通代码版（约第302行）
合并集合：第5章普通代码版（约第318行）

并且已经做了演示输出，能看到哪些元素被并到了同一个集合里。

11. 真实代码运行结果与对应知识点¶

本章代码文件：

第5章普通代码版

构建脚本：

本章构建脚本

可执行文件：

本章示例程序

已经真实编译并运行通过。

当前验证过的内容包括：

根据先序字符串递归建树
先序 / 中序 / 后序 / 层序遍历
结点数、叶子数、度为 1 / 2 的结点数统计
二叉树高度计算
查找某结点所在层次
左右孩子交换
并查集的查找与合并
哈夫曼树构造与 WPL 计算

其中一个很适合自学观察的样例是：

先序建树串：ABD##E##CF###

它对应输出了：

Preorder: A B D E C F
Inorder: D B E A F C
Postorder: D E B F C A
Level order: A B C D E F

这能直接帮助你建立“同一棵树在不同遍历下顺序完全不同”的直觉。

12. 本章第一阶段易错点¶

12.1 树的高度和结点的高度混淆¶

树的高度：整棵树最大层数
结点的高度：以该结点为根的子树高度

12.2 二叉树和度为 2 的树混淆¶

二叉树强调：

最多两个孩子
且必须区分左右

12.3 遍历顺序死背字母，不理解根何时访问¶

正确理解应是：

先序：根最先访问
中序：根夹在左右子树之间
后序：根最后访问

12.4 做算法题时忘了“遍历模板”¶

很多题其实就是：

先确定遍历框架
再在框架里加统计或判断逻辑

15. 5.2 二叉树再讲透一点¶

15.1 二叉树最容易被低估的地方¶

很多同学第一次看二叉树，会觉得它只是“每个结点最多两个孩子”。
但真正重要的是：

它有左右之分
左右不能随便交换成“同一棵树”
它的递归结构非常强

所以二叉树的难点不在“两个孩子”，而在：

左右有序
递归定义
遍历方式多
很多性质都和编号、层次、空位置有关

15.2 五种基本形态¶

教材里强调二叉树的五种基本形态，其实是想让你先接受一个事实：

空树也是二叉树
只有根也可以
只有左子树可以
只有右子树也可以
左右子树同时存在当然也可以

这里最容易错的是：

只有一个孩子时，左孩子和右孩子不是一回事

比如：

A 只有左孩子 B

和

A 只有右孩子 B

在二叉树里是两棵不同的树。

15.3 满二叉树与完全二叉树¶

满二叉树¶

满二叉树就是“每层都满”。

它的特点：

第 i 层恰好有 2^(i-1) 个结点
高度为 h 时，共有 2^h - 1 个结点
只有最后一层是叶子层
除叶子外，其余结点度都为 2

形象理解：

满二叉树像一个完全撑开的三角形

完全二叉树¶

完全二叉树没有要求“每层都满”，而是要求：

除最后一层外都满，最后一层从左到右连续排布，中间不能插空。

这个“不能插空”非常关键。

它带来的高频性质有：

叶子只可能出现在最后两层
若存在度为 1 的结点，则最多只有一个
并且这个度为 1 的结点只能有左孩子
若按层序编号，编号更大的结点不会出现在编号更小结点的左边空位之前

15.4 完全二叉树编号关系为什么重要¶

完全二叉树按层序从 1 开始编号时：

双亲：floor(i / 2)
左孩子：2i
右孩子：2i + 1

这组关系非常重要，因为：

它能直接把树的结构关系压进数组下标里
所以完全二叉树特别适合顺序存储

反过来说：

如果一棵普通二叉树很稀疏，还硬用顺序存储，就会浪费很多空间。

15.5 二叉树存储结构¶

顺序存储¶

顺序存储适合：

满二叉树
完全二叉树
近似完全的二叉树

优点：

编号关系直接
找双亲、孩子非常快
很适合堆这种结构

缺点：

对普通稀疏二叉树不友好
会出现很多空位浪费

链式存储¶

链式存储通常用二叉链表：

typedef struct BiTNode {
    char data;
    struct BiTNode *lchild;
    struct BiTNode *rchild;
} BiTNode, *BiTree;

它的优点是：

结构自然
稀疏树不浪费大量空位置
特别适合递归算法

当前真实代码就采用的是这种方式：

第5章普通代码版（约第9行）

15.6 二叉链表里的每个指针到底在表示什么¶

看二叉链表时，必须形成这个直觉：

lchild 指向左子树根
rchild 指向右子树根
空指针并不代表“出错”，而是代表“这里没有对应子树”

这也是为什么递归遍历时第一句几乎总是：

if (tree == NULL) return;

因为：

空指针本来就是树结构的一部分
递归必须承认“空树也是合法子结构”

16. 5.3 遍历真正怎么学¶

16.1 不要把遍历当成四个死记的序列¶

更好的理解方式是：

每个结点都有三次“理论上的经过机会”
第一次到达根前，可以叫“先”
夹在左右子树之间，可以叫“中”
左右都处理完再离开，可以叫“后”

于是：

先序：第一次经过时访问
中序：中间经过时访问
后序：最后离开时访问

这比死记 NLR / LNR / LRN 更容易真的理解。

16.2 为什么遍历模板这么重要¶

二叉树算法题里，很多题其实只是遍历模板的变形：

求结点数
求叶子数
求高度
交换左右子树
求某类结点数量
找某结点所在层次

这些题表面不同，但骨架都差不多。

所以你真正该会的是：

看到题目，先判断该把逻辑挂到哪个遍历模板上

16.3 先序遍历：适合“根先处理”¶

先序的顺序是：

根 -> 左 -> 右

它特别适合：

输出树的结构轮廓
建树时与空结点标记配合
先处理根，再递归子树的场景

当前代码中的真实实现：

第5章普通代码版（约第140行）

原书思路版伪代码¶

PreOrder(T)
if T != NULL
    visit(T)
    PreOrder(T->lchild)
    PreOrder(T->rchild)

真代码¶

void PreorderTraversal(BiTree tree) {
    if (tree == NULL) {
        return;
    }

    VisitNode(tree);
    PreorderTraversal(tree->lchild);
    PreorderTraversal(tree->rchild);
}

一句话理解¶

先序就是“刚见到根就先记下来”

16.4 中序遍历：适合“左根右”的结构关系¶

中序的顺序是：

左 -> 根 -> 右

它最重要的应用直觉是：

在二叉搜索树里，中序序列是有序的
所以中序天然适合处理“大小有序”关系

当前代码中的真实实现：

第5章普通代码版（约第151行）

原书思路版伪代码¶

InOrder(T)
if T != NULL
    InOrder(T->lchild)
    visit(T)
    InOrder(T->rchild)

真代码¶

void InorderTraversal(BiTree tree) {
    if (tree == NULL) {
        return;
    }

    InorderTraversal(tree->lchild);
    VisitNode(tree);
    InorderTraversal(tree->rchild);
}

一句话理解¶

中序就是“左边看完，再回来看根，最后看右边”

16.5 后序遍历：适合“孩子先处理完”¶

后序的顺序是：

左 -> 右 -> 根

它特别适合：

删除整棵树
求子树信息后再处理根
自底向上归并信息

当前代码中的真实实现：

第5章普通代码版（约第162行）

原书思路版伪代码¶

PostOrder(T)
if T != NULL
    PostOrder(T->lchild)
    PostOrder(T->rchild)
    visit(T)

真代码¶

void PostorderTraversal(BiTree tree) {
    if (tree == NULL) {
        return;
    }

    PostorderTraversal(tree->lchild);
    PostorderTraversal(tree->rchild);
    VisitNode(tree);
}

一句话理解¶

后序就是“孩子都交代完了，最后再处理根”

16.6 层序遍历：和前三种不是一条路子¶

层序遍历不是深度优先，而是广度优先。

它的访问顺序是：

先上一层
再下一层
同层内从左到右

所以最适合的辅助结构是：

队列

当前代码中的真实实现：

第5章普通代码版（约第173行）

原书思路版伪代码¶

LevelOrder(T)
初始化队列 Q
根结点入队
while Q 非空
    p 出队
    visit(p)
    若有左孩子，则左孩子入队
    若有右孩子，则右孩子入队

真代码核心理解¶

出队的是“当前该访问的结点”
入队的是“下一层等待访问的结点”
这样自然就形成按层推进

16.7 四种遍历应该怎么区分¶

记忆顺序建议不要靠字母，而靠“根什么时候被访问”：

根最早：先序
根居中：中序
根最晚：后序
根按层推进：层序

如果还是容易混，就抓住这句：

先中后，都是在问“根结点何时被访问”

17. 遍历基础上的算法模板¶

17.1 求结点总数¶

思路：

空树结点数是 0
非空树结点数 = 左子树结点数 + 右子树结点数 + 1

真代码：

第5章普通代码版（约第198行）

17.2 求叶子结点数¶

思路：

空树返回 0
左右孩子都空，返回 1
否则递归统计左右子树

真代码：

第5章普通代码版（约第206行）

17.3 求高度¶

思路：

空树高度为 0
非空树高度 = max(左子树高度, 右子树高度) + 1

真代码：

第5章普通代码版（约第241行）

这题特别值得背下来，因为它几乎就是“树形递归”的标准模板。

17.4 交换左右孩子¶

思路：

先交换当前根的左右孩子
再分别递归左右子树

真代码：

第5章普通代码版（约第257行）

这题很适合用来检验你是不是真的理解“递归会自动把同一规则传下去”。

18. 第5章代码阅读入口¶

如果你想把这部分代码真正读顺，建议按这个顺序：

先看结点定义和建树函数
再看四种遍历
再看统计与高度这类递归函数
最后看并查集和哈夫曼树

推荐顺序如下：

CreateBiTreeByPreorder：第5章普通代码版（约第92行）
PreorderTraversal：第5章普通代码版（约第140行）
InorderTraversal：第5章普通代码版（约第151行）
PostorderTraversal：第5章普通代码版（约第162行）
LevelOrderTraversal：第5章普通代码版（约第173行）
CountNodes / CountLeaves / GetBiTreeHeight
InitUnionFind / FindSet / UnionSets
BuildHuffmanTree

这样读的好处是：

先把树的基本操作读顺
再去看应用结构

19. 5.2 和 5.3 的高频易错点¶

19.1 二叉树不一定是满的，也不一定是完全的¶

这个是基本坑。

19.2 完全二叉树里“只可能有一个度为 1 的结点”¶

而且它只能有左孩子，没有右孩子。

19.3 中序遍历不是所有树都有特别强的性质¶

只有在二叉搜索树这类特殊结构里，中序才会直接得到有序序列。

19.4 层序遍历不是递归首选¶

层序遍历最自然是队列，不是普通递归。

19.5 算法题别急着写代码，先判断属于哪类模板¶

先问自己：

是统计题吗
是改造题吗
是查找题吗
是要先处理根，还是先处理孩子

这个判断做对了，代码会容易很多。

22. 线索二叉树¶

22.1 为什么会有线索二叉树¶

普通二叉链表里有一个很显眼的问题：

很多结点的左指针为空
很多结点的右指针也为空

这些空指针如果什么都不存，就被浪费掉了。
而从遍历角度看，这些空位其实很有价值，因为它们可以补充：

某结点在某种遍历下的前驱是谁
某结点在某种遍历下的后继是谁

于是就有了线索二叉树。

一句话理解：

线索二叉树就是把原来浪费掉的空指针，改造成“遍历关系指针”。

22.2 什么叫“线索”¶

在线索二叉树里：

若一个结点原本没有左孩子
就可以让它的左指针指向某种遍历序列中的前驱
若一个结点原本没有右孩子
就可以让它的右指针指向某种遍历序列中的后继

这里的“前驱”和“后继”必须带一个前提：

是在某一种指定遍历序列下说的

所以会有：

先序线索二叉树
中序线索二叉树
后序线索二叉树

其中最常见、最基础、最爱考的是：

中序线索二叉树

22.3 为什么还要有标志位¶

如果一个指针既可能指向孩子，又可能指向前驱/后继，那程序怎么知道它现在到底代表谁？

所以必须加标志位。

常见设计是：

ltag = 0：lchild 指向左孩子
ltag = 1：lchild 指向前驱线索
rtag = 0：rchild 指向右孩子
rtag = 1：rchild 指向后继线索

这一步很重要，因为：

线索不是“孩子”
只是借指针域临时保存的遍历关系

如果没有标志位，程序就会分不清“这条边到底是真孩子还是假线索”。

22.4 中序线索二叉树最值得掌握什么¶

对初学者来说，先把这三点抓住就够了：

中序序列是“左 -> 根 -> 右”
若一个结点没有左孩子，则它的左线索指向中序前驱
若一个结点没有右孩子，则它的右线索指向中序后继

也就是说，中序线索化之后，很多原本需要回溯或借栈才能找到的前驱/后继关系，被直接缝进了指针里。

22.5 线索二叉树到底解决了什么问题¶

它主要解决的是：

如何更方便地按某种序列找前驱/后继
如何减少遍历时对栈或递归回溯的依赖

你可以把它理解成：

普通二叉链表更像“只存结构”
线索二叉树更像“结构 + 一部分遍历导航”

22.6 中序线索化的直觉流程¶

中序线索化时，可以想成我们在做一件事：

按中序遍历不断访问结点
每访问到一个新结点，就看看它和“刚访问过的上一个结点”之间能不能补线索

更具体地说：

若当前结点没有左孩子
它的左指针就指向刚访问过的那个结点，也就是中序前驱
若上一个访问过的结点没有右孩子
那个结点的右指针就指向当前结点，也就是中序后继

这里最核心的变量通常叫：

pre

它表示：

“刚刚在中序遍历里访问过的前一个结点”

所以线索化本质上是：

一边中序遍历
一边补前驱/后继关系

22.7 先序 / 后序线索为什么更绕¶

因为中序有一个天然好记的结构：

左 -> 根 -> 右

而且前驱/后继关系相对直观。
后序线索尤其复杂，因为：

后序里根最后访问
某结点后继有时需要借助双亲信息才能快速判断

这也是为什么教材里通常会强调：

中序线索最基础
后序线索找后继更复杂
某些情况下需要三叉链表或带双亲信息的结构辅助

22.8 线索二叉树高频易错点¶

错点1：把线索当孩子¶

线索不是子树连接，它只是遍历关系。

错点2：忘了看 tag¶

无论访问 lchild 还是 rchild，都必须先看它到底是孩子还是线索。

错点3：前驱后继没说明是哪种遍历¶

前驱和后继一定要带前提：

是先序的？
中序的？
还是后序的？

不加限定，这个说法是不完整的。

错点4：只会背定义，不会从遍历过程理解¶

最稳的方法还是：

先写出遍历序列
再看每个结点的前后是谁
最后再去理解线索指向

23. 树、森林与二叉树转换¶

23.1 为什么这三者可以互相转¶

一般树看起来一个结点能有很多孩子，好像和二叉树差得很远。
但只要我们换一种表达方式，就能把“多孩子”压缩成二叉树结构。

这个转换的核心思想就是：

左孩子右兄弟

意思是：

一个结点的第一个孩子，接到左指针
这个孩子的下一个兄弟，接到右指针
再往后的兄弟继续沿右指针串起来

这样一来：

左边表示“往下一层”
右边表示“同一层兄弟关系”

多叉树就被翻译成了二叉树。

23.2 树转二叉树的三步规则¶

教材里常讲成三句话：

加线：把兄弟结点从左到右依次相连
去线：每个结点只保留与第一个孩子的连线
旋转：整体按某种方向调整后，就能看成一棵二叉树

但更推荐你记成这句更直观的话：

第一个孩子接左边，其余兄弟沿右边排开

这句基本够你做大部分题。

23.3 二叉树转回树怎么想¶

反过来时也一样：

左指针表示“第一个孩子”
右指针表示“后续兄弟”

所以恢复一般树时，你要做的事就是：

顺着左边往下认孩子层次
顺着右边把同层兄弟一个个接回来

所以这个转换不是死记图形，而是看懂：

左边是纵向孩子链
右边是横向兄弟链

23.4 森林为什么也能转二叉树¶

森林本质上是“多棵树并列”。

那怎么转成一棵二叉树？

思路是：

把森林的第一棵树当成二叉树根所在的主干
第一棵树的根的右边，接剩余森林对应的二叉树

所以可以把森林看成：

第一棵树
剩余森林

这其实又是递归结构。

23.5 遍历对应关系特别重要¶

这部分很爱出选择题。

你要记住：

树的先根遍历，对应其转换后二叉树的先序遍历
树的后根遍历，对应其转换后二叉树的中序遍历

对于森林也是类似的：

森林的先序遍历，对应转换后二叉树的先序遍历
森林的中序遍历，对应转换后二叉树的中序遍历

这里最容易混的点是：

树的后根遍历，不是对应二叉树的后序，而是对应中序

这是高频坑点。

23.6 为什么这个转换很有价值¶

因为很多看起来属于“树”和“森林”的问题，转换成二叉树后就能直接借用：

二叉树遍历
二叉链表存储
递归算法模板

所以转换的意义不是“图形游戏”，而是：

把复杂多叉结构，压成我们已经熟悉的二叉树结构来处理

23.7 树 / 森林转换高频易错点¶

错点1：把所有孩子都接到左边¶

不对。
只有第一个孩子接左边，后续兄弟要沿右边串。

错点2：兄弟关系和孩子关系分不清¶

左边是“下去” 右边是“同层横移”

这两个方向一定不要搞反。

错点3：遍历对应关系记错¶

最容易错的是：

树的后根遍历对应的是二叉树中序

不是后序。

24. 第5章题型索引¶

为了后面复习时查得更快，我把第 5 章先按高频题型分成下面几类。

24.1 树的基本概念与性质类¶

常见考法：

结点数、边数、度数和之间的关系
树高的最小值或最大值
m 叉树某层最多结点数
已知各度结点数，求叶子数或总结点数

这类题最常用的核心关系是：

边数 = 结点数 - 1
所有结点度数之和 = 边数

优先回看：

本书第5章正文 的 4.4 树的性质

24.2 二叉树概念辨析类¶

常见考法：

二叉树与度为 2 的树的区别
满二叉树、完全二叉树的性质判断
顺序编号关系
完全二叉树里度为 1 结点的特征

优先回看：

本书第5章正文 的 15. 5.2 二叉树再讲透一点

24.3 存储结构类¶

常见考法：

顺序存储适合什么树
链式存储的优缺点
编号和数组下标的对应关系
普通二叉树用顺序存储为什么浪费空间

优先回看：

本书第5章正文 的 15.5 二叉树存储结构
第5章普通代码版

24.4 遍历序列判断类¶

常见考法：

给出树形，求先中后层序
比较某个结点在两种遍历中的相对位置
叶结点在不同遍历中的顺序关系
给定遍历规则判断编号方式

优先回看：

本书第5章正文 的 16. 5.3 遍历真正怎么学
第5章普通代码版（约第140行）
第5章普通代码版（约第151行）
第5章普通代码版（约第162行）
第5章普通代码版（约第173行）

24.5 遍历基础算法题类¶

常见考法：

求结点数
求叶子数
求度为 1 / 2 的结点个数
求高度
交换左右子树
求某结点所在层次

这类题最本质的能力是：

会把“当前处理动作”挂到递归遍历模板上

优先回看：

本书第5章正文 的 17. 遍历基础上的算法模板
第5章逐行注释版代码

24.6 线索二叉树类¶

常见考法：

线索的含义
中序线索前驱 / 后继判断
标志位含义
为什么后序线索找后继更复杂

优先回看：

本书第5章正文 的 22. 线索二叉树

24.7 树 / 森林转换类¶

常见考法：

树转二叉树
森林转二叉树
左孩子右兄弟规则
遍历对应关系

优先回看：

本书第5章正文 的 23. 树、森林与二叉树转换

24.8 哈夫曼树类¶

常见考法：

哈夫曼树构造过程
WPL 计算
哈夫曼编码性质
前缀编码判断
与最优合并问题结合

优先回看：

本书第5章正文 的 10.1 哈夫曼树
第5章普通代码版（约第401行）
第5章普通代码版（约第440行）

24.9 并查集类¶

常见考法：

Find / Union 的作用
双亲表示法
路径压缩
连通性判断
最小生成树中的应用

优先回看：

本书第5章正文 的 10.2 并查集
第5章普通代码版（约第304行）
第5章普通代码版（约第320行）

26. 刷题路径¶

第 5 章体量大、概念密、题型杂，不适合乱刷。
更稳的办法是分轮推进。

26.1 基础训练：只抓树与二叉树的基本概念¶

这一部分的目标不是做难题，而是先把最容易混的概念压稳：

树、森林、二叉树分别是什么
结点的度、树的度、层次、深度、高度分别是什么意思
二叉树为什么不等于“度为 2 的树”
满二叉树、完全二叉树的区别

如果这一部分没稳，后面性质题和选择题会一直出错。

26.2 进阶训练：专刷树和二叉树的性质题¶

这一部分重点练：

n 个结点的树为什么有 n - 1 条边
所有结点度数之和为什么等于 n - 1
m 叉树第 i 层最多有多少个结点
已知各度结点数，求叶子数或总结点数
完全二叉树编号关系

这部分的训练目的，是把“公式不是背的，而是结构推出来的”这个意识建立起来。

26.3 强化训练：专刷遍历¶

这一部分建议只干一件事：

画树
写先序、中序、后序、层序
再反过来看某个遍历序列对应什么结构特征

重点要练到：

看树能写遍历
看遍历能判断根在什么位置
知道哪些遍历适合什么操作

这是第 5 章最核心的一轮。

26.4 第四轮：遍历模板迁移到算法题¶

这一部分建议围绕下面这些题型练：

求结点数
求叶子数
求度为 1 / 2 的结点数
求高度
交换左右子树
求某结点所在层次

这里的重点不是刷量，而是练一种能力：

看到题目后，能迅速判断它该挂到哪个递归模板上

26.5 第五轮：线索二叉树 + 转换关系¶

这一部分建议不要急着上最难题，而是先稳住：

线索是什么
tag 是什么
中序线索前驱后继怎么理解
左孩子右兄弟怎么画
树 / 森林与二叉树遍历对应关系

这部分属于“概念不算多，但很容易想反”的类型。

26.6 第六轮：应用题¶

最后再刷：

哈夫曼树构造
WPL 计算
哈夫曼编码和前缀编码
并查集的 Find / Union
并查集在连通性、最小生成树中的应用

这轮的目标是把“树”从结构知识推进到“会用”。

27. 自学检查清单¶

如果你想判断自己第 5 章到底学到了什么程度，可以用这份清单自查。

27.1 概念层¶

你应该能不看书直接说清：

树和森林的定义
祖先、子孙、兄弟、堂兄弟
结点的度、树的度
层次、深度、高度
二叉树为什么不是“度为 2 的树”

27.2 性质层¶

你应该能独立推出：

树中边数 = 结点数 - 1
所有结点度数之和 = 边数
m 叉树第 i 层最多有 m^(i-1) 个结点
满二叉树和完全二叉树的高频性质
完全二叉树编号下的双亲 / 左右孩子关系

27.3 遍历层¶

你应该能熟练写出：

先序
中序
后序
层序

而且不只是会写顺序，还应该知道：

根在什么时刻被访问
哪类问题更适合哪种遍历

27.4 算法层¶

你应该至少能自己写出或读懂：

求结点总数
求叶子数
求度为 1 / 2 的结点数
求高度
交换左右子树
求某结点层次

27.5 线索层¶

你应该能清楚解释：

线索为什么会出现
什么叫中序前驱 / 中序后继
ltag / rtag 的作用
为什么后序线索找后继更麻烦

27.6 转换层¶

你应该能独立说清：

树转二叉树怎么转
森林转二叉树怎么转
左孩子右兄弟到底在表达什么
树和二叉树遍历之间的对应关系

27.7 应用层¶

你应该能说清：

哈夫曼树为什么能让 WPL 最小
哈夫曼编码为什么是前缀编码
并查集适合做什么
Find 和 Union 分别在做什么

如果这些都能比较顺地回答出来，第 5 章就已经不只是“看懂了”，而是基本进入“会做题、会讲解、会写代码”的状态。

28. 原书试题区整理版¶

这一部分不逐题机械照抄，而是按“原书常考点”重新组织成更适合自学和刷题的结构。

28.1 树的基本概念与性质题¶

这部分原书高频考的是：

树最适合表示什么数据
树中结点数、边数、度数和之间的关系
m 叉树的层数、结点数和高度极值
已知各度结点数，求叶子数和总结点数
森林中的树个数

做这类题最重要的不是背结果，而是抓住两个核心关系：

边数 = 结点数 - 1
所有结点度数之和 = 边数

只要这两个关系稳了，很多题都能列方程做出来。

典型题1：有 n 个结点的树，所有结点度数之和是多少¶

直接结论：

n - 1

原因：

除根外，每个结点都对应一条来自双亲的边
所以边数就是 n - 1
树中所有结点度数之和又等于总边数

典型题2：森林有 25 个结点、15 条边，问有多少棵树¶

思路：

一棵树满足：结点数 = 边数 + 1
对森林来说，每棵树都多出 1
所以森林中树的棵数 = 结点数 - 边数

于是：

25 - 15 = 10

典型题3：度为 3 的树有 50 个结点，最小高度是多少¶

本质思路：

要让高度最小，就让每层尽量满
也就是尽量接近完全三叉树
逐层累加 1 + 3 + 9 + 27 = 40
第 5 层还需要再放 10 个结点

所以最小高度是：

28.2 二叉树概念与性质题¶

这部分原书高频考的是：

满二叉树、完全二叉树的定义和性质
编号后双亲、左孩子、右孩子的下标关系
二叉树顺序存储适合什么场景
二叉树与度为 2 的树有什么区别

典型题：完全二叉树里度为 1 的结点有什么特点¶

结论：

最多只有一个
且只能有左孩子

这个结论特别爱在选择题里出现。

28.3 遍历题¶

这部分是第 5 章最核心的出题区。

原书常见考法包括：

给树形求遍历序列
比较某结点在不同遍历下的先后
由题目要求判断用哪种遍历编号
遍历基础上的算法设计题

做遍历判断题的固定思路¶

先找根
再看左子树和右子树
然后判断根是在前、中、后哪个时刻访问

不要一上来就背序列，先抓“根何时访问”会更稳。

高频结论：叶子在三种深度优先遍历中的相对顺序¶

这类题很容易出选择题。
一般要靠画局部结构来判断，不能只凭印象。

所以建议：

先自己画一棵小树
分别写出前中后序
再观察叶子相对顺序到底有没有变

28.4 线索二叉树题¶

原书这部分高频考点主要有：

线索的定义
标志位的含义
中序线索的前驱 / 后继
后序线索找后继为什么更复杂

高频结论¶

线索二叉树不是改变树的逻辑结构
它只是利用空指针补充遍历关系
中序线索最基础，后序线索找后继最绕

做题时一定要先问自己：

现在说的是哪种线索
当前这个指针是孩子还是线索

28.5 树 / 森林转换题¶

这部分原书高频考的是：

树怎么转成二叉树
森林怎么转成二叉树
遍历之间的对应关系

最核心的一句¶

左孩子右兄弟

只要这句真懂了，大部分图形题都能做。

高频对应关系¶

树的先根遍历 = 对应二叉树的先序遍历
树的后根遍历 = 对应二叉树的中序遍历

这个第二条是特别容易记错的地方。

28.6 哈夫曼树与哈夫曼编码题¶

这部分原书高频考：

哈夫曼树的定义
哈夫曼树的构造过程
WPL 计算
哈夫曼编码和前缀编码
最优合并问题

典型题：为什么最优合并问题会联想到哈夫曼树¶

因为：

越早参与合并的对象，后面会被反复带着参与比较
所以应该优先合并“最小的两个”
这和哈夫曼树构造的贪心过程一模一样

所以：

多个有序表最优合并
文件最优合并
某些最小代价归并问题

都可以往哈夫曼树上想。

28.7 并查集题¶

原书这部分高频考的是：

并查集的存储结构
Find 和 Union 的意义
路径压缩
判断连通性
在最小生成树中的应用

典型题：为什么并查集适合判连通 / 判成环¶

因为并查集特别擅长回答这个问题：

两个元素现在是不是已经属于同一个集合？

于是：

若一条边连接的两个顶点已经在同一集合
再加这条边就会成环

这就是它在图算法里特别常见的原因。

30. 原书试题逐题详细解答：5.1 - 5.3¶

第 5 章整章题量较大，这里先把前半章最核心、最爱丢分的试题区做成详细解答版。
重点覆盖：

5.1 树的基本概念与性质
5.2 二叉树的概念
5.3 二叉树的遍历和线索二叉树

后文继续补入 5.4 和 5.5 的详细解答。

30.1 5.1 树的基本概念与性质¶

选择题 1¶

题目本质：

树最适合表示什么类型的数据关系。

正确答案：

D. 元素之间具有分支层次关系

详细思路：

树不是为了表示线性先后关系。
它也不是为了表示任意网状复杂关系。
它最擅长的是“一个结点往下分叉”的层次结构。

所以像：

目录
组织结构
家谱

都更适合用树来描述。

易错提醒：

若元素之间关系是“任意点都可能互相连”，那更像图，不是树。

选择题 2¶

题目本质：

有 n 个结点的树，所有结点的度数之和是多少。

正确答案：

A. n - 1

详细思路：

树中有 n 个结点时，边数一定是 n - 1。
每一条边都对应某个结点引出的一条分支。
所以所有结点的度数之和 = 总边数 = n - 1。

这个结论非常重要，整章都在反复用。

选择题 3¶

题目本质：

树的路径长度到底指什么。

正确答案：

A. 总和

详细思路：

树的路径长度是：

从树根到每个结点的路径长度之和

不是：

最大值
最小值
平均值

注意别把它和后面的“哈夫曼树带权路径长度 WPL”混在一起。

选择题 4¶

题目本质：

对一棵有 n 个结点、度为 4 的树，高度最多能有多大。

正确答案：

A. 树的高度至多是 n - 3

详细思路：

要让树的高度尽量大，就要让树尽量“瘦”。

但题目又要求“树的度为 4”，这说明：

至少有一个结点的度必须达到 4
这个结点一下子会贡献 4 个孩子

为了让高度最大：

先尽量形成单链
但某一层必须出现一个度为 4 的结点

因此会比纯单链少掉 3 层空间，得到最大高度：

n - 3

选择题 5¶

题目本质：

度为 4、高度为 h 的树，至少有多少个结点。

正确答案：

A. 至少有 h + 3 个结点

详细思路：

想让结点最少、但又满足：

树高度为 h
树的度为 4

就要：

除了必须出现的那个度为 4 的结点外
其他层尽量只放一个结点

这样得到的最小结点数是：

h + 3

这类题建议画草图，会比死算更快。

选择题 6¶

题目本质：

度为 3 的树有 50 个结点，最小高度是多少。

正确答案：

C. 5

详细思路：

要让高度最小，就让树尽量满。

对于三叉树：

第 1 层最多 1 个
第 2 层最多 3 个
第 3 层最多 9 个
第 4 层最多 27 个

前 4 层最多共有：

1 + 3 + 9 + 27 = 40

还差：

50 - 40 = 10

所以必须再开第 5 层，因此最小高度为：

选择题 7¶

题目本质：

已知度为 3 的结点数、度为 2 的结点数和叶子数，问总结点数。

正确答案：

按原书答案区，这题应选 D

详细思路：

设：

度为 3 的结点数 n3 = 2
度为 2 的结点数 n2 = 1
叶子数 n0 = 6
度为 1 的结点数记为 n1

则总结点数：

n = n0 + n1 + n2 + n3 = 6 + n1 + 1 + 2 = n1 + 9

而总度数之和又等于 n - 1：

n1 + 2*1 + 3*2 = n - 1
n1 + 8 = n - 1
n = n1 + 9

这个式子恒成立，说明：

无法唯一确定 n1
所以 n 也无法唯一确定

只能确定：

n >= 9

这题最值钱的地方不是算出某个数，而是看出“条件不够”。

选择题 8¶

题目本质：

已知各度结点数，求 m 叉树叶子数的一般关系。

正确结论：

叶子数满足：

N0 = 1 + Σ(i - 1)Ni

也就是：

N0 = 1 + N2 + 2N3 + ... + (m - 1)Nm

详细思路：

由：

总结点数 N = N0 + N1 + N2 + ... + Nm
总度数之和 = N - 1

可得：

N1 + 2N2 + 3N3 + ... + mNm = N0 + N1 + N2 + ... + Nm - 1

整理后：

N0 = 1 + N2 + 2N3 + ... + (m - 1)Nm

这是求叶子数的高频万能公式。

选择题 9¶

题目本质：

已知度为 1, 2, 3, 4 的结点数，求叶子数。

正确答案：

B. 82

详细思路：

设叶子数为 n0。

由“树中所有结点度数之和 = 结点数 - 1”：

n = n0 + 10 + 1 + 10 + 20

总度数之和为：

1*10 + 2*1 + 3*10 + 4*20 = 122

所以：

n - 1 = 122
n = 123

再代回去：

n0 + 41 = 123
n0 = 82

选择题 10¶

题目本质：

森林有 25 个结点、15 条边，问一共有多少棵树。

正确答案：

C. 10

详细思路：

对森林中每一棵树，都有：

结点数 = 边数 + 1

所以对整个森林：

树的棵数 = 结点数 - 边数 = 25 - 15 = 10

这个结论本质上也是“每棵树都比边数多 1”。

综合题 1¶

题目本质：

含 n 个结点的三叉树，最小高度是多少。

详细解答：

要让高度最小，就要让树尽量接近完全三叉树。

设高度为 h，则前 h 层最多有：

1 + 3 + 3^2 + ... + 3^(h-1) = (3^h - 1) / 2

要容纳 n 个结点，需满足：

(3^h - 1) / 2 >= n

整理得：

3^h >= 2n + 1

因此最小高度为：

ceil(log3(2n + 1))

这题的本质就是：

最小高度 = 让每层尽量满

综合题 2¶

题目本质：

已知度为 0,1,2,3 的结点数分别为 14,4,3,2
求总结点数和度为 4 的结点数

详细解答：

设度为 4 的结点数为 n4，总结点数为 n。

则：

n = 14 + 4 + 3 + 2 + n4 = 23 + n4

又因为：

n - 1 = 1*4 + 2*3 + 3*2 + 4*n4
n - 1 = 4 + 6 + 6 + 4n4 = 16 + 4n4
n = 17 + 4n4

联立：

23 + n4 = 17 + 4n4
6 = 3n4
n4 = 2

所以：

n = 25

结论：

度为 4 的结点数是 2
总结点数是 25

综合题 3¶

题目本质：

已知一棵度为 m 的树中，各度结点数分别为 N1, N2, ..., Nm
求叶子数 N0

详细解答：

由：

N = N0 + N1 + N2 + ... + Nm

又因为总度数之和等于 N - 1：

N1 + 2N2 + 3N3 + ... + mNm = N - 1

代入 N 并整理，得到：

N0 = 1 + N2 + 2N3 + ... + (m - 1)Nm

这条式子是树题里的核心万能式之一。

30.2 5.2 - 5.3 二叉树与遍历¶

选择题 1¶

题目本质：

判断某结点若是某子树中序序列最后一个结点，会不会也是该子树先序序列最后一个结点。

正确答案：

C

详细思路：

中序遍历最后一个结点，一定是：

从根出发
一路沿右孩子走到底
得到的最右结点

如果这个结点还是叶子，那么：

它没有左子树
也没有右子树
在先序里它也自然会落到该子树最后

所以题目中只有“叶结点 + 中序最后”这一种说法一定成立。

选择题 2¶

题目本质：

比较结点 b 和 c 在不同遍历序列中的先后关系。

详细思路：

这类题不要靠猜，要先看：

两结点的公共祖先是谁
b 在左子树还是右子树
是在先序、中序还是后序下比较

高频规律是：

左子树中的结点通常会先于右子树中的结点被访问
但根的位置会因遍历不同而变化

做题时建议：

先画局部结构
再按遍历规则手推

选择题 3¶

题目本质：

在中序遍历中，结点 n 在结点 m 前面的充分必要条件是什么。

正确答案：

C. n 在 m 左方

详细思路：

中序遍历遵循：

左 -> 根 -> 右

所以只要 n 位于 m 的左边那一侧，在中序中就会先被访问。

更准确地说：

若两者分处某公共祖先的左右子树
只要 n 落在左边、m 落在右边
中序下就必然是 n 在前

选择题 4¶

题目本质：

在后序遍历中，结点 n 在 m 前面的充分条件是什么。

正确答案：

D. n 是 m 的子孙

详细思路：

后序遍历是：

左 -> 右 -> 根

所以一个结点的子孙一定先于这个结点被访问。
因此若 n 是 m 的子孙，则 n 一定在 m 前面。

这题最稳的抓法就是：

后序里，孩子一定先于祖先

选择题 5¶

题目本质：

给顺序存储数组，求对应二叉树的后序遍历序列。

正确答案：

按原书答案区，应选 C

详细思路：

这类题固定步骤：

先把数组按完全二叉树下标关系还原成树形
再按后序规则 左 -> 右 -> 根 写序列

这题的关键不是会背答案，而是会从顺序存储反推出树形。

选择题 6¶

题目本质：

在前序、中序、后序中，所有叶结点的先后顺序是否相同。

正确答案：

B. 完全相同

详细思路：

这是一条非常经典的结论：

不论是前序、中序还是后序
所有叶结点出现的相对先后顺序都是相同的

为什么？

因为遍历虽然改变了根和内部结点的位置，
但叶子在整棵树里的从左到右结构并没有变。

这条结论很值得背下来。

选择题 7¶

题目本质：

对二叉树从 1 开始连续编号，要求双亲编号大于孩子编号，且左孩子编号小于右孩子编号。

正确答案：

C. 后序遍历

详细思路：

因为要求：

父结点编号要比左右孩子都大
说明父结点必须最后编号

这正对应：

左 -> 右 -> 根

也就是后序遍历。

选择题 8¶

题目本质：

根据编号规则反推使用的是哪种遍历。

详细思路：

遇到这类题，固定只问自己一件事：

根是在孩子之前访问，还是之后访问，还是夹在中间访问？

把这一点判断清楚，就能很快定位遍历类型。

线索二叉树类选择题¶

这部分原书高频考的主要是：

中序线索前驱 / 后继怎么找
标志位在表达什么
为什么后序线索找后继更复杂

详细抓法：

先明确是哪种线索
再看当前结点有没有真实孩子
最后根据遍历顺序判断前驱 / 后继

千万不要脱离“指定遍历序列”空谈前驱后继。

30.3 学习提示¶

如果你把这一部分题解真正吃透，说明你已经掌握了第 5 章前半段最核心的能力：

会用“边数 = 结点数 - 1”解树的性质题
会用“度数和 = 边数”解各度结点数题
能看懂满二叉树和完全二叉树的高频性质
能分清四种遍历的本质差异
能从遍历规则反推编号方式和结点相对位置
能理解线索二叉树和树 / 森林转换的核心思路

也就是说，第 5 章现在已经不只是“知识点齐了”，而是开始具备“刷题型章节”的骨架了。

31. 原书试题逐题详细解答版（进阶部分：5.4 - 5.5）¶

这里把第 5 章后半段也一并展开，重点覆盖：

5.4 树、森林
5.5 树与二叉树的应用

这样第 5 章就不再只是“前半章有题解”，而是整章都开始有详细解答层了。

31.1 5.4 树、森林¶

高频题 1：树与二叉树遍历的对应关系¶

题目本质：

问树转换成二叉树后，原来的遍历序列与二叉树哪种遍历序列对应。

核心结论：

树的先根遍历 = 对应二叉树的先序遍历
树的后根遍历 = 对应二叉树的中序遍历

详细思路：

树转二叉树的本质是：

第一个孩子接左边
兄弟沿右边串起来

也就是“左孩子右兄弟”。

这样转换后：

先根遍历先访问根，再访问子树
在二叉树里就对应“根 -> 左 -> 右”，也就是先序

而后根遍历是：

先访问子树
最后访问根

在这种转换下，恰好对应二叉树的中序。

易错提醒：

最容易错的是把“后根遍历”记成二叉树后序，实际上是对应中序。

高频题 2：森林与二叉树遍历的对应关系¶

题目本质：

问森林转换成二叉树后，森林的先序 / 中序遍历与二叉树哪种遍历对应。

核心结论：

森林的先序遍历 = 对应二叉树的先序遍历
森林的中序遍历 = 对应二叉树的中序遍历

详细思路：

森林可以递归地拆成：

第一棵树
剩余森林

而转换后二叉树里：

第一棵树走左边主线
剩余森林沿右边延展

所以遍历对应关系会自然保留下来。

高频题 3：孩子兄弟链表中怎么求叶子数¶

题目本质：

已知树采用孩子兄弟表示法，要求叶子结点个数。

详细思路：

在孩子兄弟链表中：

firstchild 表示第一个孩子
nextsibling 表示下一个兄弟

一个结点是不是叶子，关键就看：

它有没有 firstchild

所以递归逻辑是：

空树返回 0
若当前结点没有孩子，则它自己算一个叶子，再去统计兄弟子树
若当前结点有孩子，则递归统计孩子子树和兄弟子树

这类题的关键不是记代码，而是先认清：

在孩子兄弟表示法里，“有没有孩子”只看 firstchild

高频题 4：孩子兄弟链表中怎么求树高¶

题目本质：

已知树采用孩子兄弟表示法，要求树高。

详细思路：

孩子兄弟表示法里，当前结点的高度取决于两部分：

它的孩子子树能有多高
它的兄弟子树能有多高

但这两部分含义不同：

走向孩子，是往下一层，所以高度要加 1
走向兄弟，是同一层横向移动，所以不额外加层数

因此递归思路是：

高度 = max(孩子子树高度 + 1, 兄弟子树高度)

这是孩子兄弟表示法里最容易被写错的一点。

易错提醒：

对兄弟递归时不要加 1，因为兄弟不在下一层。

31.2 5.5 树与二叉树的应用¶

选择题 1¶

题目本质：

已知哈夫曼树有 n 个叶子，问其分支结点数或合并次数。

正确答案：

原书答案为 A

核心结论：

哈夫曼树的分支结点数 = 叶子数 - 1

详细思路：

哈夫曼树本质上是一棵满二叉树式的最优二叉树：

每次合并两个最小权值结点
就会新建一个分支结点
若初始有 n 个叶子，就要合并 n - 1 次

所以：

共新建 n - 1 个分支结点
分支结点数就是 n - 1

选择题 2¶

题目本质：

判断某给定树形是否符合哈夫曼树构造规律。

正确答案：

原书答案为 C

详细思路：

哈夫曼树判断题通常抓三点：

每个新父结点的权值应等于左右孩子权值之和
哈夫曼树中没有度为 1 的结点
不是只看形状，而是看构造过程是否始终由最小两棵树合并

如果某个父结点权值不等于左右孩子权值之和，那就直接排除。

选择题 3¶

题目本质：

判断一组编码是不是前缀编码。

正确答案：

原书答案为 B

详细思路：

前缀编码的定义是：

任一字符编码都不是另一字符编码的前缀

所以判断方法很直接：

把所有编码两两比较
只要某个短编码刚好是某个长编码的前缀
那它就不是前缀编码

这类题不要只看第一位相不相同，而要看整个短码是否完整出现在长码开头。

选择题 4¶

题目本质：

已知编码长度受限，问最多还能安排多少个不同码字。

正确答案：

原书答案为 C

详细思路：

这类题本质上是在做“前缀编码容量分析”。

要点是：

某个短码一旦被占用
以它为前缀的所有更长编码都不能再用

所以做题时不能简单数“总共有多少个二进制串”，而要扣掉所有被短码封死的分支。

选择题 5¶

题目本质：

给定哈夫曼树的某些条件，求叶子数或总结点数。

详细思路：

这类题最常用的是：

哈夫曼树只有度为 0 和 2 的结点
在非空二叉树中，叶子数 n0 = n2 + 1

因此：

若已知叶子数，就能求分支结点数
总结点数 = 2n0 - 1

这是哈夫曼树题里的万能关系。

选择题 6¶

题目本质：

多个初始结点构造哈夫曼树时，高度能达到多少。

正确答案：

原书答案为 C

详细思路：

这类题考的是：

哈夫曼树虽然是最优二叉树
但其形状不一定平衡
在某些权值安排下，高度仍然可能比较大

做题时需要抓住：

初始有 n 个叶子
就会新建 n - 1 个分支结点
再根据最瘦可能结构估高度

选择题 7¶

题目本质：

关于哈夫曼树构造和性质的综合判断。

正确答案：

原书答案为 D

详细思路：

这类题常混合考：

哈夫曼树是否唯一
WPL 是否唯一
左右子树交换是否影响最优性

正确认识是：

哈夫曼树的具体形状不一定唯一
但最小 WPL 是唯一的
左右孩子谁在左谁在右，一般不影响 WPL

选择题 8¶

题目本质：

哈夫曼树有哪些必然性质。

正确答案：

原书答案为 C

详细思路：

原书这一题考查了几条经典性质：

哈夫曼树总结点数为 2n - 1
没有度为 1 的结点
WPL 可视为所有叶子带权路径长度之和
也可视为所有分支结点权值之和

这题最值钱的不是某个选项，而是把这几条性质同时串起来。

选择题 9¶

题目本质：

度为 m 的哈夫曼树，叶子数与分支结点数关系是什么。

正确答案：

原书答案为 C

详细思路：

设：

叶子数为 n0
度为 m 的分支结点数为 nm

由于总边数为：

N - 1

而所有分支恰好由度为 m 的结点引出：

m * nm = N - 1 = n0 + nm - 1

整理得：

(m - 1)nm = n0 - 1
nm = (n0 - 1) / (m - 1)

这是 m 叉哈夫曼树的通用关系。

选择题 10¶

题目本质：

并查集采用什么存储结构最合适。

正确答案：

原书答案为 B

详细思路：

并查集通常采用的是：

双亲表示法

因为它最关心的是：

当前元素的父是谁
一路往上能否找到集合代表元

所以双亲表示法最自然。

选择题 11¶

题目本质：

给出若干次合并与查找操作，问最后形成哪些集合。

正确答案：

原书答案为 C

详细思路：

这类题固定做法是：

一开始每个元素单独成集
每次 Union 就把两个集合并到一起
Find 只是问它们是否已属于同一集合

原书这题最后形成的集合为：

{0, 5, 6}
{1, 2, 7, 8, 9}
{3, 4}

所以选 C。

易错提醒：

这类题不要被查找操作打乱，Find 本身不增加新集合，只是查询归属。

选择题 12¶

题目本质：

并查集在图中能做什么、不能做什么。

正确答案：

原书答案为 D

详细思路：

并查集非常适合：

判断两个顶点是否已经连通
判断加一条边会不会成环
配合 Kruskal 算法构造最小生成树

但要注意：

未做路径压缩时，最坏查找复杂度并不小
不能夸大并查集的效率结论

这题的重点是：

明白并查集擅长“集合归属判断”，不是万能图算法。

选择题 14¶

题目本质：

关于哈夫曼树的真假判断。

正确答案：

原书答案为 A

详细思路：

常见判断点有：

哈夫曼树不一定是完全二叉树
哈夫曼树没有度为 1 的结点
每次选最小的两个权值合并
非叶结点权值等于左右孩子权值之和

因此若选项说“哈夫曼树一定是完全二叉树”，那就是错的。

选择题 15¶

题目本质：

判断某组编码是不是前缀编码。

正确答案：

原书答案为 D

详细思路：

只要某个编码是另一个编码的前缀，就不是前缀编码。
原书这一题中，110 是 1100 的前缀，所以直接排除。

选择题 17¶

题目本质：

已知一串编码，按哈夫曼编码规则译码。

正确答案：

原书答案为 D

详细思路：

哈夫曼编码是前缀编码，所以译码可以这样做：

从左到右扫描比特串
每次尽量匹配一个完整码字
匹配成功后立刻切断，再继续往后匹配

因为前缀不冲突，所以这种逐段匹配是唯一的。

这类题不要怕长，只要顺着切即可。

选择题 19¶

题目本质：

有 n 个不同符号做哈夫曼编码，若哈夫曼树共有 115 个结点，求 n。

正确答案：

原书答案为 C

详细思路：

哈夫曼树总结点数为：

2n - 1

所以：

2n - 1 = 115
2n = 116
n = 58

选择题 20¶

题目本质：

给 5 个叶子权值 10, 12, 16, 21, 30
求最小 WPL

正确答案：

原书答案为 B

最小 WPL：

详细思路：

按哈夫曼树构造：

先合并 10 和 12，得 22
再合并 16 和 21，得 37
再合并 22 和 30，得 52
再合并 37 和 52，得根

WPL 可由每个叶子的路径长度乘权值求和，
也可直接用“每次合并的新权值之和”来算：

22 + 37 + 52 + 89 = 200

这个“合并权值求和法”非常好用。

选择题 21¶

题目本质：

比较哈夫曼编码树与定长编码树的性质。

正确答案：

原书答案为 D

详细思路：

定长编码树的特点是：

所有字符都在同一层
叶子深度一致

而哈夫曼编码树里：

高频字符可能更靠近根
低频字符可能更深

所以“不同频次字符在定长编码树中处于相同层”这一说法正确。

选择题 22¶

题目本质：

频次为 3, 4, 5, 6, 8, 10
求哈夫曼编码的加权平均长度

正确答案：

原书答案为 B

即：

2.5

详细思路：

原书给出的构造结果表明：

有 4 个叶子编码长度为 3
有 2 个叶子编码长度为 2

所以加权平均长度为：

[(3 + 4 + 5 + 6) * 3 + (8 + 10) * 2] / (3 + 4 + 5 + 6 + 8 + 10)
= (18 * 3 + 18 * 2) / 36
= (54 + 36) / 36
= 90 / 36
= 2.5

综合题 1：构造权值集合 `{5, 2, 3, 6, 7, 8, 9}` 的哈夫曼树并求 WPL¶

详细解答：

按“每次取最小两个”原则：

合并 2 和 3，得 5
合并 5 和 5，得 10
合并 6 和 7，得 13
合并 8 和 9，得 17
合并 10 和 13，得 23
合并 17 和 23，得 40

于是：

WPL = 5 + 10 + 13 + 17 + 23 + 40 = 108

也就是说，直接把每一步新产生的父结点权值加起来，就能得到：

若按叶子深度算，也能得到同样结果：

(2 + 3) * 4 + (5 + 6 + 7) * 3 + (8 + 9) * 2 = 108

不过就考试而言，记住“每次合并新权值求和”最省力。

说明：

哈夫曼树形状不唯一，但最小 WPL 唯一。

综合题 2：6 个不同长度有序表最优合并¶

已知表长：

10, 35, 40, 50, 60, 200

题目要求：

给出最优合并过程
求最坏情况下总比较次数
总结一般策略

详细解答：

最优合并过程¶

按哈夫曼思想，每次选最短两个表合并：

10 + 35 -> 45
40 + 45 -> 85
50 + 60 -> 110
85 + 110 -> 195
195 + 200 -> 395

最坏比较次数¶

合并两个长度分别为 m 和 n 的有序表，最坏比较次数为：

m + n - 1

所以：

第 1 次：10 + 35 - 1 = 44
第 2 次：40 + 45 - 1 = 84
第 3 次：50 + 60 - 1 = 109
第 4 次：85 + 110 - 1 = 194
第 5 次：195 + 200 - 1 = 394

总比较次数：

44 + 84 + 109 + 194 + 394 = 825

一般策略¶

多个不同长度有序表做两两合并时：

最先参与合并的表，后面会被多次带着继续比较
所以应该优先合并最短的两个
这与哈夫曼树构造完全同构

所以最优策略就是：

每次选当前最短的两个表合并

综合题 3：前缀编码的存储、译码与判定¶

题目本质：

哪种数据结构适合保存具有前缀特性的不等长编码
如何从 0/1 串译码
如何判定一组编码是否具有前缀特性

详细解答：

1. 适合的数据结构¶

最适合的是：

二叉树

因为：

编码每一位只有 0/1
天然对应“左 / 右”分支
从根到叶的一条路径就能表示一个编码

2. 译码过程¶

步骤如下：

从根开始
读一位比特
若是 0 就往左走，若是 1 就往右走
一旦走到叶子，就输出该叶子对应字符
再回到根继续处理后面的比特

为什么这样一定可行：

因为前缀编码保证不会出现“一个字符码字刚好是另一个的前缀”，所以切分是唯一的。

3. 怎么判定是否具有前缀特性¶

可以边建二叉树边判断：

初始只有根
依次插入每个编码
若在插入过程中提前遇到已有叶子，说明某已有码字是当前码字前缀，失败
若当前编码整段走完都没新建结点，说明当前码字本身是别人的前缀，失败
若所有编码都能合法插入，则具有前缀特性

这是最稳定、最程序化的判定方式。

31.3 学习提示¶

如果你把这一部分也吃透，说明第 5 章后半段的高频题型也基本接上了：

树 / 森林转换题不再只会背图
线索二叉树不再只停留在定义层
哈夫曼树会从“看懂”走向“会算”
WPL 和最优合并问题开始真正打通
并查集会从“知道名字”走向“会判断集合和成环”

这样一来，第 5 章就更接近一整章完整成品，而不是零散笔记了。

32. 深度复核与达标修订¶

这里不是简单续写，而是把第 5 章按完整章节标准重新复核了一遍，并补上最关键的缺口。

32.1 本轮复核发现的关键缺口¶

复核时我重点盯了三个问题：

线索二叉树原先讲得够多，但真实代码层不够完整。
这会导致学生“概念上懂了”，但一到代码实现就还是断档。
第 5 章已经有讲义、试题和代码，但检索入口还不够集中。
学生后面复习时，容易出现“知道讲过，但一时找不到”的情况。
章节已经很厚，但还缺一份明确的“达标验收清单”。
也就是说，学生读完后还不太容易判断自己到底是“看过了”，还是“真的能用了”。

32.2 已补的关键增强：线索二叉树真实代码落地¶

这里最重要的增强，是把“中序线索二叉树”补成了可运行的真实代码。

现在第 5 章代码里已经加入了这些函数：

CreateThreadNode
CloneBiTreeToThreadTree
DestroyThreadTree
InorderThreading
BuildInorderThreadedTree
FirstInorderThreadNode
NextInorderThreadNode
InorderThreadTraversal

也就是说，这部分已经不再停留在“定义”和“手算前驱后继”层，而是已经能落到：

把普通二叉树复制成线索二叉树结构
按中序规则完成线索化
不用递归、不用栈，直接完成中序遍历

原书思路版伪代码¶

InThread(T, pre):
    if T != NULL:
        InThread(T->lchild, pre)
        if T->lchild == NULL:
            T->ltag = 1
            T->lchild = pre
        if pre != NULL and pre->rchild == NULL:
            pre->rtag = 1
            pre->rchild = T
        pre = T
        InThread(T->rchild, pre)

对应真实代码¶

void InorderThreading(ThreadTree node, ThreadTree *pre) {
    if (node == NULL) {
        return;
    }

    if (node->lchild != NULL) {
        InorderThreading(node->lchild, pre);
    }

    if (node->lchild == NULL) {
        node->ltag = true;
        node->lchild = *pre;
    }

    if (*pre != NULL && (*pre)->rchild == NULL) {
        (*pre)->rtag = true;
        (*pre)->rchild = node;
    }

    *pre = node;

    if (node->rchild != NULL) {
        InorderThreading(node->rchild, pre);
    }
}

这一段最值得学生看懂什么¶

pre 不是“随便传一下的辅助变量”，而是“刚刚访问过的前一个结点”
ltag 和 rtag 的作用，是告诉你当前指针到底指向的是“孩子”，还是“线索”
线索化的核心不是多开了什么神秘结构，而是在原有空指针位置上把“前驱 / 后继”补进去

32.3 术语索引¶

为了让这一章后面更适合查阅，我把最常用术语重新收口如下：

树：一种一对多层次关系结构
结点的度：这个结点拥有的孩子个数
树的度：整棵树中所有结点度的最大值
叶结点：度为 0 的结点
分支结点：至少有一个孩子的结点
层次：从根往下数，根通常在第 1 层
结点深度：从根走到该结点经过的层级
结点高度：从该结点往下走到最深叶子所经历的层数
树的高度：整棵树的最大层数
路径长度：路径上边的条数
满二叉树：每一层都达到最大结点数的二叉树
完全二叉树：除最后一层外都满，最后一层结点尽量靠左的二叉树
线索：把空指针改接到某种遍历下的前驱或后继
线索二叉树：带 tag 标志位的“孩子 / 线索”混合结构
孩子兄弟表示法：左指针指向第一个孩子，右指针指向下一个兄弟
哈夫曼树：带权路径长度最小的二叉树
WPL：所有叶子结点“权值 × 路径长度”的总和
前缀编码：任一编码都不是另一个编码前缀的编码方案
并查集：支持“查代表元”和“并集合”的集合结构
路径压缩：查找根结点时顺手缩短路径
按规模合并：把小集合挂到大集合下，降低树高

32.4 代码函数索引¶

如果复习目标是“要写代码 / 要做题”，第 5 章最值得反复看的函数如下：

1. 基础遍历与建树¶

CreateBiTreeByPreorder：按先序字符串建树
PreorderTraversal：先序遍历模板
InorderTraversal：中序遍历模板
PostorderTraversal：后序遍历模板
LevelOrderTraversal：层序遍历模板

2. 遍历模板迁移出来的算法题¶

CountNodes：统计结点总数
CountLeaves：统计叶子数
CountDegreeOne：统计度为 1 的结点数
CountDegreeTwo：统计度为 2 的结点数
GetBiTreeHeight：求树高
FindNodeLevel：求指定结点层次
SwapChildren：交换左右子树

3. 线索二叉树¶

BuildInorderThreadedTree：把普通二叉树变成中序线索二叉树
InorderThreading：真正完成线索化的核心过程
FirstInorderThreadNode：找中序第一个结点
NextInorderThreadNode：在线索结构中找下一个结点
InorderThreadTraversal：不借助栈和递归完成中序遍历

4. 树 / 森林转换¶

CreateGTreeNode：创建普通树结点
PreRootTraversal：普通树先根遍历
PostRootTraversal：普通树后根遍历
PreorderForestTraversal：森林先序输出
ConvertTreeToBinaryTree：树转二叉树
ConvertForestToBinaryTree：森林转二叉树
ConvertBinaryTreeToGTree：二叉树还原回普通树

5. 并查集¶

InitUnionFind：初始化
FindSet：找集合代表元
UnionSets：合并集合
PrintUnionFindState：观察集合归并结果

6. 哈夫曼树¶

SelectTwoMinNodes：找当前最小的两棵树
BuildHuffmanTree：构造哈夫曼树
ComputeHuffmanWPL：求 WPL
PrintHuffmanTree：把数组形式的树结构打印出来

32.5 达标验收清单¶

如果我们把“第 5 章达标”拆开来看，这一章现在至少应当满足下面这些条件：

内容层¶

5.1 - 5.5 主干知识都已覆盖
不只是列定义，还补了直觉解释、关系辨析和常见误区
树、二叉树、线索二叉树、树 / 森林转换、哈夫曼树、并查集都已接上

自学层¶

有学习目标
有易错点
有刷题路径
有自学检查清单
有原书试题整理
有逐题详细解答

代码层¶

书里常见伪代码已经落到真实 C 代码
二叉树四种遍历、常见递归模板、并查集、哈夫曼树都已可运行
已补入中序线索二叉树真实代码
有逐行注释版代码，适合学生一点点对照阅读

验证层¶

代码已重新编译通过
运行结果已经能对应到遍历、统计、并查集、哈夫曼树、线索遍历等关键知识点

32.6 当前边界与使用建议¶

为了保持诚实，我也把当前边界讲清楚：

第 5 章现在已经足够作为“自学版章节成品”使用。
学生即使不回原 PDF，也可以把主干知识和高频题型学下来。
线索二叉树已经补到真实代码层。
所以这一块不再只是会背概念，而是已经能真正读代码、跑代码。
树 / 森林转换目前仍以“规则理解 + 遍历对应 + 题型训练”为主。
这部分对考试最重要的是会判断、会画图、会对应遍历；如果你后面想把它继续扩成完整代码专项，也完全可以再单独加一轮。
如果后面把第 6 章也按这个标准推进，那么整本材料的风格就会更统一：
不是“章节笔记”，而是“可独立学习、可查、可练、可运行”的增强版教材。

32.7 本轮复核结论¶

本轮复核后，第 5 章已经达到了我们当前设定的高标准：

结构完整
解释够细
代码可跑
题型够全
自学支持够强

所以现在的第 5 章，不再只是“树与二叉树的整理稿”，而是已经可以视作一份可直接投入学习和复习的章节成品。

33. 树 / 森林转换代码专项版¶

前面我们已经把“左孩子右兄弟”这个规则讲清楚了，但只讲规则还不够。
学生真正容易卡住的点是：

代码里到底要开什么结构
转换时左右指针到底怎么接
转完以后，遍历对应关系怎么在运行结果里体现出来

这里把这部分正式补成了真实代码专题。

33.1 真实代码覆盖能力¶

现在 第5章普通代码版 里已经新增了这一组函数：

CreateGTreeNode
DestroyGTree
PreRootTraversal
PostRootTraversal
PreorderForestTraversal
ConvertTreeToBinaryTree
ConvertForestToBinaryTree
ConvertBinaryTreeToGTree
BuildSampleGeneralTree
BuildSampleForest

它们对应的意义非常明确：

先用 first_child + next_sibling 表示普通树 / 森林
再把它们转换成二叉树
然后用真实遍历结果验证“先根 = 先序，后根 = 中序”这件事
最后再把二叉树还原回普通树，说明这个转换不是只会单向背规则

33.2 普通树结点长什么样¶

这部分最关键的不是代码多复杂，而是结点结构一定要想清楚：

typedef struct GTreeNode {
    char data;
    struct GTreeNode *first_child;
    struct GTreeNode *next_sibling;
} GTreeNode, *GTree;

这里的含义是：

first_child 指向当前结点的第一个孩子
next_sibling 指向当前结点的下一个兄弟

这就是“左孩子右兄弟”思想在普通树层面的直接落地。

33.3 树转二叉树：原书思路版伪代码¶

TreeToBinaryTree(T):
    if T == NULL:
        return NULL

    创建二叉树结点 B
    B.data = T.data
    B.lchild = TreeToBinaryTree(T.first_child)
    B.rchild = TreeToBinaryTree(T.next_sibling)
    return B

这段伪代码一定要盯住两句：

第一个孩子 -> 左孩子
下一个兄弟 -> 右孩子

这两句就是整块转换代码的灵魂。

33.4 对应真实代码¶

BiTree ConvertTreeToBinaryTree(GTree tree) {
    BiTree root;

    if (tree == NULL) {
        return NULL;
    }

    root = CreateNode(tree->data);
    if (root == NULL) {
        return NULL;
    }

    root->lchild = ConvertTreeToBinaryTree(tree->first_child);
    root->rchild = ConvertTreeToBinaryTree(tree->next_sibling);
    return root;
}

这段真代码和伪代码几乎是一一对应的，所以学生这时最应该学会的是：

先看结构映射
再看递归展开
不要一上来就盯着指针害怕

33.5 二叉树转回普通树¶

很多学生会有一个误区：

觉得“树转二叉树”只是考试里的画图技巧，代码里没法反过来还原

这里把反向转换也补上了：

GTree ConvertBinaryTreeToGTree(BiTree tree) {
    GTree root;

    if (tree == NULL) {
        return NULL;
    }

    root = CreateGTreeNode(tree->data);
    if (root == NULL) {
        return NULL;
    }

    root->first_child = ConvertBinaryTreeToGTree(tree->lchild);
    root->next_sibling = ConvertBinaryTreeToGTree(tree->rchild);
    return root;
}

你会发现它和前面的转换几乎完全对称：

左孩子还原成第一个孩子
右孩子还原成下一个兄弟

这就说明这部分知识不是“死记图形”，而是真能写成程序。

33.6 运行结果怎么验证遍历对应关系¶

在 main 中放了两组样例：

样例 1：普通树¶

树结构大意如下：

A
├─ B
│  ├─ E
│  └─ F
├─ C
└─ D
   └─ G

运行结果里你会看到：

General tree preorder: A B E F C D G
General tree postorder: E F B C G D A
Binary tree preorder converted from tree: A B E F C D G
Binary tree inorder converted from tree: E F B C G D A
Restored general tree preorder: A B E F C D G

这个结果非常重要，因为它把第 5 章最容易背混的两个关系直接跑出来了：

普通树先根遍历 = 对应二叉树先序遍历
普通树后根遍历 = 对应二叉树中序遍历

而且“还原后的普通树先根遍历”又回到了原结果，说明转换链条是闭合的。

样例 2：森林¶

同时补入了森林样例，运行结果如下：

Forest preorder: A B C X Y Z
Binary tree preorder converted from forest: A B C X Y Z

这有助于学生直观理解：

森林里的每一棵树，本质上就是根结点之间的兄弟链
森林转二叉树时，第一棵树作为开始，其余树通过“右兄弟链”继续接下去

33.7 这一块最容易错在哪¶

错点 1：把所有孩子都直接挂到左边¶

正确想法不是“所有孩子都挂左边”，而是：

第一个孩子挂左边
其余孩子顺着兄弟链往右挂

错点 2：把 `next_sibling` 当成“另一个孩子”¶

它不是第二个孩子。
它表示的是“和当前结点同一层、同一个父结点下的下一个兄弟”。

错点 3：记住了规则，却不会用遍历结果验算¶

这类题最稳的自查方式就是：

先写出普通树的先根 / 后根
再写出对应二叉树的先序 / 中序
对照是否一致

只要一致，你的转换大概率就是对的。

33.8 本节学习意义¶

补完这轮以后，第 5 章里“树 / 森林转换”这部分已经不再只是：

会背一句“左孩子右兄弟”

而是已经升级成：

会解释结构
会写真实代码
会看运行结果
会用遍历关系反向验算

到这一步，这部分就真正进入“能学、能写、能查、能复习”的状态了。

33.9 树 / 森林转换逐行拆解阅读入口¶

建议不要一上来就从头到尾硬看，而是按下面的顺序阅读。

第一步：先看普通树结点结构¶

先看：

第5章普通代码版（约第47行）

这里最重要的不是背代码，而是先把这两个指针彻底分清：

first_child：第一个孩子
next_sibling：下一个兄弟

如果这一步没吃透，后面所有转换代码都会看着像“指针乱连”。

第二步：看普通树本身怎么遍历¶

再看：

第5章普通代码版（约第482行）
第5章普通代码版（约第498行）
第5章普通代码版（约第514行）

这一部分重点不是记函数名，而是观察：

普通树先根遍历为什么是“先访问当前结点，再依次处理孩子”
普通树后根遍历为什么一定是“孩子都处理完，再访问当前结点”
森林其实就是“多棵树沿兄弟链并排放”

第三步：只盯树转二叉树这一件事¶

核心函数是：

第5章普通代码版（约第525行）

读这一段时，只问自己两个问题：

为什么 first_child 要转成 lchild
为什么 next_sibling 要转成 rchild

如果你能把这两个映射说顺，这个函数就已经理解了八成。

第四步：再看反向还原¶

接着看：

第5章普通代码版（约第548行）

这一步是最能建立信心的，因为它会让你发现：

左孩子右兄弟不是死记规则
它真的是一套能双向转换的结构映射

你会看到：

lchild -> first_child
rchild -> next_sibling

这和前面的转换是完全对称的。

第五步：最后再看样例构造和运行输出¶

最后去看：

第5章普通代码版（约第566行）
第5章普通代码版（约第605行）
第5章普通代码版（约第858行）
第5章普通代码版（约第884行）

这里最值得做的不是“看它输出了什么”，而是：

先自己手算普通树先根 / 后根结果
再自己猜转换后二叉树的先序 / 中序结果
最后和程序输出对照

这样你才会真正把“遍历对应关系”记牢。

如需查看逐行注释版¶

优先看：

第5章逐行注释版代码

如果本地编辑器编码兼容性一般，再看：

第5章兼容编码版逐行注释代码

最推荐的阅读节奏是：

先读本节讲义，知道这块在讲什么
再看普通代码版，抓整体结构
卡住时切到逐行注释版，一行一行过
最后跑 本章示例程序，把输出和遍历关系对上

这一块真正学会的标志¶

如果能做到下面这几件事，就说明树 / 森林转换这部分已经真正学进去了：

不看资料，能说出“左孩子右兄弟”到底是什么意思
能自己画一棵普通树，并写出对应二叉树的大致形状
能解释为什么普通树先根对应二叉树先序
能解释为什么普通树后根对应二叉树中序
能顺着 ConvertTreeToBinaryTree 和 ConvertBinaryTreeToGTree 把递归过程讲出来

站内代码入口¶

对应代码专题：第5章树与二叉树代码
如果你想逐行对照实现，建议把正文页和代码专题页一起打开。

第5章 树与二叉树（自学增强版）¶

1. 本章定位¶

2. 学习目标¶

3. 本章结构总览¶

4. 5.1 树的基本概念¶

4.1 树的定义¶

4.2 树适合表示什么¶

4.3 基本术语¶

4.3.1 双亲、孩子、兄弟¶

4.3.2 祖先、子孙¶

4.3.3 结点的度与树的度¶

4.3.4 叶结点与分支结点¶

4.3.5 层次、深度、高度¶

4.3.6 路径与路径长度¶

4.4 树的性质¶

性质1：树中结点数与边数¶

性质2：所有结点度数之和¶

性质3：m 叉树第 i 层最多有多少结点¶

性质4：高度与结点数的上下界¶

5. 5.2 二叉树的概念¶

5.1 二叉树的定义¶

5.2 二叉树为什么不等于“度为 2 的树”¶

5.3 特殊二叉树¶

5.3.1 满二叉树¶

5.3.2 完全二叉树¶

5.3.3 顺序存储时的编号关系¶

6. 5.3 二叉树的遍历¶

6.1 为什么遍历是本章核心¶

6.2 三种深度优先遍历¶

6.3 层序遍历¶

6.4 原书伪代码与真实代码对照：先序遍历¶

原书思路版伪代码¶

对应真实代码¶

理解重点¶

6.5 原书伪代码与真实代码对照：中序遍历¶

原书思路版伪代码¶

对应真实代码¶

6.6 原书伪代码与真实代码对照：后序遍历¶

原书思路版伪代码¶

对应真实代码¶

6.7 层序遍历：伪代码与真实代码¶

原书思路版伪代码¶

对应真实代码¶

7. 遍历基础上的高频算法¶

8. 5.3.2 线索二叉树¶

8.1 为什么需要线索二叉树¶

8.2 这一节最该掌握什么¶

9. 5.4 树、森林与二叉树的转换¶

9.1 为什么树能转成二叉树¶

9.2 对应关系¶

10. 5.5 树与二叉树的应用¶

10.1 哈夫曼树¶

本章真实代码¶

10.2 并查集¶

本章真实代码¶

11. 真实代码运行结果与对应知识点¶

12. 本章第一阶段易错点¶

12.1 树的高度和结点的高度混淆¶

12.2 二叉树和度为 2 的树混淆¶

12.3 遍历顺序死背字母，不理解根何时访问¶

12.4 做算法题时忘了“遍历模板”¶

15. 5.2 二叉树再讲透一点¶

15.1 二叉树最容易被低估的地方¶

15.2 五种基本形态¶

15.3 满二叉树与完全二叉树¶

满二叉树¶

完全二叉树¶

15.4 完全二叉树编号关系为什么重要¶

15.5 二叉树存储结构¶

顺序存储¶

链式存储¶

15.6 二叉链表里的每个指针到底在表示什么¶

16. 5.3 遍历真正怎么学¶

16.1 不要把遍历当成四个死记的序列¶

16.2 为什么遍历模板这么重要¶

16.3 先序遍历：适合“根先处理”¶

原书思路版伪代码¶

真代码¶

一句话理解¶

16.4 中序遍历：适合“左根右”的结构关系¶

第5章树与二叉树（自学增强版）¶