【王道考研·数据结构】第五章树与二叉树（整章完整版）

Austoin2026-03-252026-03-25

引言

第五章是数据结构里非常重要的一章，因为它把前面以“线性关系”为主的结构，进一步扩展到了“层次关系”和“集合划分关系”。这一章看似内容很多，实际上可以整理成三条主线：

树与二叉树的基本概念与性质
树与二叉树的存储、遍历、构造、转换
树结构的两个经典应用：哈夫曼树与并查集

如果前面线性表、栈、队列、串这些内容学的是“顺着一条线怎么组织数据”，那么这一章学的就是“怎么表示层级”和“怎么表示元素之间的归属关系”。

本篇会把第五章所有 PPT 内容合并成一篇完整文章，并且把 PPT 中只给结论、图示但没有讲透的地方一并补全。

图像化理解（Mermaid）

  mindmap
  root((第五章主线))
    树与二叉树（结构）
      定义/术语/性质
      存储（顺序/链式）
      遍历（先中后层）
      构造（前+中/后+中）
      转换（树/森林<->二叉树）
    树的应用（算法）
      哈夫曼树（最小 WPL）
      并查集（集合合并与查询）

一句话：前半章学“树怎么表示和遍历”，后半章学“树怎么拿来做最优编码与集合管理”。

一、树的定义、基本术语与性质

1. 树的定义

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

当 n = 0 时，称为空树
当 n > 0 时，在任意一棵非空树中必须满足：
1. 有且仅有一个根结点
2. 其余结点可以分成 m (m > 0) 个互不相交的有限集合，每个集合本身又是一棵树，并称为根结点的子树

这个定义非常关键，因为它揭示了树的本质：

树是一种递归定义的数据结构。

也就是说，一棵树由若干棵更小的树组成；而这些更小的树又继续由更小的树组成。

2. 树的几个直观特征

在非空树中：

有且仅有一个根结点
没有后继的结点称为叶子结点（终端结点）
有后继的结点称为分支结点（非终端结点）
除根结点外，任意结点都有且仅有一个前驱
每个结点可以有 0 个或多个后继

这几个特征和一般图结构不一样：树没有环，并且每个结点的“来源”是唯一的。

3. 基本术语

这一部分是选择题、填空题和大题都会反复考的基础。

（1）祖先、子孙、双亲、孩子、兄弟

对于树中的任意结点：

双亲结点（父结点）：它的直接前驱
孩子结点：它的直接后继
兄弟结点：同一个双亲的孩子之间互称兄弟
祖先结点：从根到该结点路径上经过的所有结点（不含自身时通常称祖先）
子孙结点：该结点子树中的所有后代结点

（2）路径与路径长度

路径：从一个结点到另一个结点所经过的结点序列
路径长度：路径上经过的边数

树中的路径默认是从上往下理解的，因为树的层次关系天然带方向。

（3）结点的度、树的度

结点的度：该结点孩子的个数
树的度：整棵树中各结点度的最大值

注意：

叶子结点的度为 0
树的度不是所有结点度的总和，而是最大值

（4）层次、高度、深度

这几个概念特别容易混。

结点的层次：从上往下数，根结点默认是第 1 层
结点的高度：从下往上数
树的高度（深度）：树中结点的最大层数

在很多教材里，“树的高度”和“树的深度”会混用；但在做题时只要明确都是“总层数”这个意思即可。

4. 有序树与无序树

有序树：结点的各子树从左到右有次序，不能交换
无序树：结点的各子树从左到右无次序，可以交换

是否有序，取决于左右位置是否承载了实际逻辑含义。

5. 森林

森林是 m (m >= 0) 棵互不相交的树的集合。

可以把森林理解为“多棵并列摆放的树”。

这个概念在第五章后半部分非常重要，因为：

森林和树可以互相转化
森林和二叉树也能互相转化

6. 树的常考性质

（1）结点数 = 总度数 + 1

这是树最重要的性质之一。

为什么成立？

一棵有 n 个结点的树共有 n - 1 条边
每条边都对应一个“孩子和双亲的连接”
所有结点的度数之和，恰好等于边数

所以：

1	结点数 = 总度数 + 1

（2）m 叉树与度为 m 的树的区别

这两者非常容易混淆。

m 叉树：每个结点最多只能有 m 个孩子
度为 m 的树：树的度是 m，说明至少有一个结点恰好有 m 个孩子

因此：

m 叉树可以没有任何结点的度达到 m
度为 m 的树一定至少有一个度为 m 的结点

（3）第 i 层至多有 `m^(i-1)` 个结点

默认根为第 1 层。

这是因为：

第 1 层最多 m^0 = 1 个结点
第 2 层最多 m^1 个结点
第 3 层最多 m^2 个结点

以此类推。

（4）高度为 h 的 m 叉树至多有 `(m^h - 1)/(m - 1)` 个结点

这是等比数列求和：

1	1 + m + m^2 + ... + m^(h-1)

（5）高度为 h 的 m 叉树至少有 h 个结点

最瘦的情况是一条链：每层一个结点，总共 h 个结点。

（6）高度为 h、度为 m 的树至少有 `h + m - 1` 个结点

这个结论的本质是：

要想树高达到 h，至少要有一条长度为 h 的链
要想树的度达到 m，至少要有一个结点多出 m - 1 个额外分支

（7）具有 n 个结点的 m 叉树最小高度

当树尽可能“丰满”时，高度最小：

1	ceil(log_m(n(m - 1) + 1))

这个公式一般以选择题形式出现，重点是要知道它描述的是“最小高度”。

二、二叉树的定义、特殊二叉树与性质

1. 二叉树的定义

二叉树是 n (n >= 0) 个结点的有限集合：

或者为空二叉树
或者由一个根结点和两个互不相交的左子树、右子树组成
左子树和右子树本身又分别是一棵二叉树

所以二叉树同样是一种递归定义的数据结构。

2. 二叉树的两个本质特征

每个结点至多只有两棵子树
左右子树不能颠倒

第二点特别重要，它说明：

二叉树不是“度为 2 的有序树”的简单口头替代，而是左右次序有明确含义的有序树。

3. 二叉树的五种状态

一个结点在二叉树中有五种可能形态：

空二叉树
只有根结点
只有左子树
只有右子树
同时有左、右子树

4. 特殊二叉树

（1）满二叉树

一棵高度为 h，且结点总数为 2^h - 1 的二叉树，称为满二叉树。

特点：

每一层都达到最大结点数
所有分支结点都有两个孩子
所有叶子都在最后一层

（2）完全二叉树

若一棵二叉树中每个结点都与同高度满二叉树中编号为 1 ~ n 的结点一一对应，则称为完全二叉树。

完全二叉树的常见特征：

只有最后两层可能有叶子结点
最多只有一个度为 1 的结点
如果某结点只有一个孩子，那么一定是左孩子

（3）二叉排序树

二叉排序树满足：

左子树所有结点关键字都小于根
右子树所有结点关键字都大于根
左右子树本身也都是二叉排序树

它常用于查找和排序。

（4）平衡二叉树

平衡二叉树要求：

任一结点的左、右子树深度之差不超过 1

它的意义是让树尽量“矮胖”，从而提高查找效率。

5. 二叉树的常考性质

（1）`n0 = n2 + 1`

设：

n0：度为 0 的结点数
n1：度为 1 的结点数
n2：度为 2 的结点数

对于非空二叉树：

1	n0 = n2 + 1

也就是说：

叶子结点数 = 双分支结点数 + 1

这是最经典的性质之一。

（2）二叉树第 i 层至多有 `2^(i-1)` 个结点

默认根结点位于第 1 层。

（3）高度为 h 的二叉树至多有 `2^h - 1` 个结点

当且仅当它是满二叉树时取到上界。

（4）完全二叉树高度

具有 n (n > 0) 个结点的完全二叉树高度为：

1	floor(log2 n) + 1

也可写成：

1	ceil(log2(n + 1))

（5）完全二叉树的编号关系（1 基）

按层序从 1 开始编号，则：

左孩子：2i
右孩子：2i + 1
父结点：floor(i / 2)

（6）完全二叉树的叶子与分支判定

i <= n / 2：分支结点
i > n / 2：叶子结点

（7）完全二叉树中 `n0、n1、n2` 的个数

若 n = 2k：

n1 = 1
n0 = k
n2 = k - 1

若 n = 2k - 1：

n1 = 0
n0 = k
n2 = k - 1

三、二叉树的存储结构

1. 顺序存储

二叉树顺序存储是把结点按完全二叉树编号顺序放入数组。

若根从下标 1 开始：

左孩子：2i
右孩子：2i + 1
父结点：floor(i / 2)

判断是否存在孩子：

有左孩子：2i <= n
有右孩子：2i + 1 <= n

2. 为什么顺序存储只适合完全二叉树

因为顺序存储的下标关系来自“完全二叉树编号”。

如果原树不是完全二叉树，但仍硬按层序往数组里塞：

数组下标就不能准确反映逻辑关系
无法直接通过 2i、2i+1、i/2 推出父子关系

所以：

二叉树顺序存储中，一定要把结点编号与完全二叉树对应起来。

若原树稀疏，则需要补很多空位置，会造成严重浪费。

最坏情况下：

一棵高度为 h 且只有 h 个结点的单支树
可能仍要占用 2^h - 1 个存储单元

结论：

顺序存储只适合完全二叉树。

3. 链式存储

普通二叉链表结点可表示为：

typedef struct BiTNode {
    ElemType data;
    struct BiTNode *lchild, *rchild;
} BiTNode;

特点：

找左右孩子很方便
找父结点不方便，通常只能从根开始遍历寻找
如果业务频繁查父结点，可以增加父指针，形成三叉链表

4. 空链域结论

n 个结点的二叉链表中共有：

1	n + 1 个空链域

这个结论是线索二叉树的理论基础。

四、二叉树的遍历

1. 什么是遍历

遍历就是：

按照某种次序，把所有结点访问一遍。

二叉树遍历有两种思路：

基于树的递归特性：先序、中序、后序
基于树的层次特性：层序遍历

2. 先序、中序、后序遍历

（1）先序遍历

规则：根左右（NLR）

void PreOrder(BiTree T) {
    if (T == NULL) return;
    visit(T);
    PreOrder(T->lchild);
    PreOrder(T->rchild);
}

（2）中序遍历

规则：左根右（LNR）

void InOrder(BiTree T) {
    if (T == NULL) return;
    InOrder(T->lchild);
    visit(T);
    InOrder(T->rchild);
}

（3）后序遍历

规则：左右根（LRN）

void PostOrder(BiTree T) {
    if (T == NULL) return;
    PostOrder(T->lchild);
    PostOrder(T->rchild);
    visit(T);
}

注意：原始 PPT 个别页把后序遍历误写成了 InOrder，这是笔误，正确写法应为 后序遍历 / PostOrder。

3. 层序遍历

层序遍历要用辅助队列：

初始化队列
根结点入队
若队列非空，则队头出队并访问
将该结点的左、右孩子依次入队（若存在）
重复直到队列为空

4. 遍历与表达式树

对表达式树来说：

先序遍历 -> 前缀表达式
中序遍历 -> 中缀表达式（必须加界限符）
后序遍历 -> 后缀表达式

5. 递归遍历的空间复杂度

三种递归遍历的空间复杂度都是：

O(h)

其中 h 为树高。

6. 手算技巧：路过三次法

把空结点也脑补出来，从根结点开始走一条“路”：

第一次路过访问 -> 先序
第二次路过访问 -> 中序
第三次路过访问 -> 后序

每个结点都会被“路过”三次，这个方法对手算遍历序列非常有用。

五、由遍历序列构造二叉树

1. 单独一个遍历序列不能唯一确定二叉树

PPT 通过前序、中序、后序、层序分别举例说明：

只给一个前序序列，不行
只给一个中序序列，不行
只给一个后序序列，不行
只给一个层序序列，也不行

也就是说：

若只给出一棵二叉树的一种遍历序列，不能唯一确定一棵二叉树。

2. 前序 + 中序

这是最经典的组合。

前序序列中：

第一个结点一定是根

中序序列中：

根左边是左子树的中序序列
根右边是右子树的中序序列

然后根据左子树长度、右子树长度，再去前序序列中切出对应部分。

3. 后序 + 中序

后序序列中：

最后一个结点一定是根

其余思路同样是靠中序序列划分左右子树范围，再在后序序列中切分对应区段。

4. 层序 + 中序

层序 + 中序也可以唯一确定。

做法是：

先在层序序列中找到根
再用中序序列把左右子树划开
然后继续从层序序列中找左右子树各自的根

5. 哪些两两组合仍不能唯一确定

必须记住：

前序 + 后序：不能唯一确定
前序 + 层序：不能唯一确定
后序 + 层序：不能唯一确定

6. 这一类题的核心思想

真正的关键并不是死记某几个例子，而是：

必须借助中序序列来划分左右子树。

因为中序序列天然把根放在中间，左边对应左子树，右边对应右子树，这正是“唯一确定结构”的关键。

六、线索二叉树

1. 为什么需要线索二叉树

在普通二叉链表中：

找一个指定结点的前驱、后继很不方便
做遍历通常必须从根开始
但是 n 个结点的二叉链表恰好有 n + 1 个空链域

于是就可以把这些空链域利用起来，记录遍历意义下的前驱、后继信息。

2. 基本概念

前驱线索：由左指针保存前驱
后继线索：由右指针保存后继

这些用于指向前驱、后继的指针，就称为“线索”。

3. 线索二叉树的存储结构

typedef struct ThreadNode {
    ElemType data;
    struct ThreadNode *lchild, *rchild;
    int ltag, rtag;
} ThreadNode;

含义：

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

4. 三种线索二叉树

中序线索二叉树：线索指向中序前驱、中序后继
先序线索二叉树：线索指向先序前驱、先序后继
后序线索二叉树：线索指向后序前驱、后序后继

5. 线索化的关键变量 `pre`

线索化过程中通常使用一个指针 pre：

表示“刚刚访问过的那个结点”
当前访问到结点 q 时，pre 就是它的前驱

因此：

若 q->lchild == NULL，可把 q->lchild 线索化为 pre
若 pre->rchild == NULL，可把 pre->rchild 线索化为 q

另外，处理完所有结点后，还要记得处理遍历序列最后一个结点的后继线索。

6. 中序线索树中找前驱和后继

这是最重要、最常考的部分。

找中序后继

设当前结点为 p：

若 p->rtag == 1，则后继就是 p->rchild
若 p->rtag == 0，则后继是 p 的右子树中最左下结点

找中序前驱

若 p->ltag == 1，则前驱就是 p->lchild
若 p->ltag == 0，则前驱是 p 的左子树中最右下结点

7. 三种线索树的对比

中序线索二叉树：找前驱、找后继都方便
先序线索二叉树：找后继方便，找前驱不方便
后序线索二叉树：找前驱方便，找后继不方便

原因本质上是：

先序遍历里，根在最前面，后继更容易推
后序遍历里，根在最后面，前驱更容易推
中序遍历中，前驱后继关系最自然对称

8. 先序 / 后序线索树中不方便的情况

对于先序线索树找前驱、后序线索树找后继，很多时候：

需要知道父结点
或者只能用“土办法”从根重新遍历去找

因此实际最常用、最常考的通常是中序线索二叉树。

七、树的存储结构

普通树的一个结点可以有多个孩子，因此不能像二叉树那样单纯依靠数组下标来反映逻辑关系。第五章介绍了三种经典表示方法。

1. 双亲表示法

每个结点保存：

data
parent

其中：

根结点的 parent = -1
非根结点的 parent 存的是其父结点在数组中的下标

优缺点

优点：找父结点非常方便
缺点：找孩子不方便，往往要从头到尾扫描整个数组

适用场景

适合“找父亲多、找孩子少”的场景，例如后面的并查集。

2. 孩子表示法

每个结点保存：

data
firstChild

其中 firstChild 指向一个孩子链表，这个链表中记录该结点所有孩子的编号。

本质上它是：

顺序存储 + 链式存储的结合。

优缺点

优点：找孩子非常方便
缺点：找父结点不方便，只能遍历各个链表

适用场景

适合“找孩子多、找父亲少”的场景。

3. 孩子兄弟表示法（左孩子右兄弟）

每个结点有两个指针：

左指针：指向第一个孩子
右指针：指向下一个兄弟

这种结构从存储形式上看，和二叉树长得非常像，因此也是后面“树 / 森林与二叉树互相转换”的基础。

4. 三种方法的比较

双亲表示法：找父亲方便
孩子表示法：找孩子方便
孩子兄弟表示法：最适合做树、森林与二叉树之间的转换

八、树、森林与二叉树的转换

1. 转换的本质

这一部分最重要的不是死记步骤，而是理解本质：

树和森林转二叉树，本质上就是把它们改写成“孩子兄弟表示法”。

2. 树 -> 二叉树

处理方法：

若某结点有多个孩子，就把所有孩子用右指针串成一串“糖葫芦”
把第一个孩子挂到该结点左指针下

于是：

左指针表示第一个孩子
右指针表示下一个兄弟

3. 森林 -> 二叉树

注意：森林中各棵树的根结点是平级关系。

因此转换时：

先把所有树根用右指针串起来
再按孩子兄弟表示法处理各棵树内部

4. 二叉树 -> 树

恢复规则：

左孩子恢复为第一个孩子
沿右指针不断拆下，恢复为该结点的一整串兄弟

5. 二叉树 -> 森林

恢复规则：

把根及其右兄弟链拆出来，作为森林中多棵树的根
再逐棵恢复各自的孩子结构

6. 做题记忆口诀

如果只是记图，很容易忘；建议记本质：

左边看孩子
右边看兄弟

只要这条核心记住，四种转换题都不难。

九、树和森林的遍历

1. 树的先根遍历

规则：

若树非空，先访问根结点
再依次对每棵子树进行先根遍历

它属于深度优先遍历。

2. 树的后根遍历

规则：

若树非空，先依次对每棵子树做后根遍历
最后访问根结点

它也属于深度优先遍历。

3. 树的层次遍历

树的层次遍历和二叉树层次遍历本质一样，也用队列：

根入队
队头出队并访问
将它的孩子依次入队
重复直到队空

4. 森林的先序遍历

若森林非空，则：

访问森林中第一棵树的根
先序遍历第一棵树根的子树森林
再先序遍历剩余森林

本质效果等同于：

依次对每棵树做先根遍历

5. 森林的中序遍历

若森林非空，则：

先中序遍历第一棵树根的子树森林
再访问第一棵树的根
再中序遍历剩余森林

本质效果等同于：

依次对每棵树做后根遍历

6. 最重要的对应关系

必须牢牢记住：

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

这是选择题和综合题的高频点。

十、哈夫曼树与哈夫曼编码

1. 带权路径长度 WPL

（1）结点的权

结点的权，就是赋予结点的一个有现实意义的数值，例如：

重要性
出现频率
代价

（2）结点的带权路径长度

从根到该结点路径长度（边数） × 该结点权值。

（3）树的带权路径长度 WPL

树中所有叶结点带权路径长度之和：

1	WPL = Σ(w_i * l_i)

注意：

WPL 只统计叶结点。

2. 哈夫曼树定义

在含有 n 个带权叶结点的二叉树中，WPL 最小的二叉树称为哈夫曼树，也叫最优二叉树。

3. 哈夫曼树的构造过程

给定 n 个权值 w1, w2, ..., wn：

先把这 n 个结点分别看成 n 棵只有一个结点的树，构成森林 F
从 F 中选择根权值最小的两棵树
构造新结点，权值为二者之和，并把这两棵树作为其左右子树
删除原来两棵树，把新树加入 F
重复上述过程，直到 F 中只剩一棵树

4. 哈夫曼树的性质

必须记住：

初始权值结点最终都变成叶结点
权值越小的结点通常离根越远
哈夫曼树总结点数为 2n - 1
哈夫曼树中不存在度为 1 的结点
哈夫曼树不唯一，但最优 WPL 相同

5. 哈夫曼编码

（1）固定长度编码

每个字符都用相同长度的二进制位表示。

优点：简单；缺点：不能利用字符频率差异。

（2）可变长度编码

允许不同字符使用不同长度的二进制编码。高频字符可以更短，低频字符可以更长。

（3）前缀编码

若没有一个编码是另一个编码的前缀，则称为前缀编码。

前缀编码的好处是：

解码无歧义。

（4）哈夫曼编码的生成

把字符看作叶结点，把字符出现频率看作权值，建立哈夫曼树；再约定：

左边记 0，右边记 1

或反过来：

左边记 1，右边记 0

只要整棵树保持一致即可。

于是，从根到叶的路径就是该字符的编码。

6. 哈夫曼编码的特点

是可变长度编码
是前缀编码
不唯一
但平均编码长度最优
可用于数据压缩

十一、并查集

1. 为什么这一章会讲并查集

前面讨论的线性结构、树结构、图结构，本质上讨论的是元素之间的“连接关系”。

而并查集对应的是另一种逻辑结构：

集合

也就是：

元素被划分成若干个互不相交的子集
我们关心一个元素属于哪个集合
以及两个集合能否合并

2. 并查集的基本思想

把同一集合中的元素组织成一棵树：

一棵树代表一个集合
根结点代表该集合

于是：

要查一个元素属于哪个集合 -> 一路向上找根
要判断两个元素是否属于同一集合 -> 分别找根，看根是否相同
要把两个集合合并 -> 让一棵树成为另一棵树的子树

3. 存储结构

并查集通常用数组 S[] 表示：

S[i] < 0：说明 i 是根
S[i] >= 0：说明 S[i] 是其父结点下标

初始化时，每个元素单独成集合：

1
2
3

void Initial(int S[], int size) {
    for (int i = 0; i < size; i++) S[i] = -1;
}

4. 两个基本操作

（1）Find

查找元素所属集合，本质是找根：

int Find(int S[], int x) {
    while (S[x] >= 0) x = S[x];
    return x;
}

（2）Union

把两个集合合并，本质是把一个根挂到另一个根下面：

void Union(int S[], int x, int y) {
    int rootX = Find(S, x);
    int rootY = Find(S, y);
    if (rootX != rootY) S[rootY] = rootX;
}

5. 朴素并查集的复杂度

若树退化成链，则：

Find 最坏时间复杂度为 O(n)

这显然太差，因此必须优化。

十二、并查集的优化

1. 第一次优化：按规模合并

优化思路：

每次 Union 时，让小树挂到大树下面。

为此，根结点数组中的负值不再只是表示“我是根”，还表示：

该集合的结点总数的相反数

例如：

S[root] = -6 表示该集合有 6 个结点

这样合并时：

结点数少的树挂到结点数多的树下面

效果是：

树不容易变得过高
Find 的最坏复杂度从 O(n) 降到 O(log n)

2. 第二次优化：路径压缩

路径压缩发生在 Find 中。

做法：

先找到根
再把查找路径上的所有结点都直接挂到根下面

递归写法：

int Find(int S[], int x) {
    if (S[x] < 0) return x;
    return S[x] = Find(S, S[x]);
}

路径压缩的意义在于：

当前一次查找之后
后续再次查找同一路径上的结点时会快很多

3. 最终复杂度

路径压缩 + 按规模合并后，代价可视为：

1	O(alpha(n))

其中 alpha(n) 是增长极其缓慢的函数。在常见规模下，它通常不超过 4，因此几乎可以把并查集操作看作“接近常数时间”。

十三、图像化总览（Mermaid）

1. 树与二叉树关系图

  flowchart LR
    T[树: 一个结点可有多个孩子] --> C[左孩子右兄弟转换]
    C --> B[二叉树: 每结点最多两个孩子]

2. 四种遍历顺序图

  mindmap
  root((四种遍历))
    先序: 根 左 右
    中序: 左 根 右
    后序: 左 右 根
    层序: 按层从上到下 同层从左到右

3. 线索二叉树 tag 图

  flowchart TD
    L0[ltag=0] --> L1[lchild 指向左孩子]
    L2[ltag=1] --> L3[lchild 指向前驱线索]
    R0[rtag=0] --> R1[rchild 指向右孩子]
    R2[rtag=1] --> R3[rchild 指向后继线索]

4. 哈夫曼构造图

  flowchart LR
    A[取最小两棵树] --> B[合并成新树]
    B --> C[放回集合]
    C --> D{只剩一棵树?}
    D -->|否| A
    D -->|是| E[结束]

5. 并查集操作图

  mindmap
  root((并查集))
    Find(x)
      沿 parent 指针向上找根
    Union(x,y)
      把一个根挂到另一个根
    优化
      小树挂大树
      路径压缩

十四、易错点与易混淆点（详细版）

A. 易混淆点（A vs B）

m 叉树 vs 度为 m 的树
- m 叉树：每个结点“最多” m 个孩子
- 度为 m 的树：至少有一个结点“恰好” m 个孩子
满二叉树 vs 完全二叉树
- 满二叉树：每层都满
- 完全二叉树：最后一层可不满，但必须连续靠左
树高/深度口径
- 绝大多数考题按“总层数”理解
- 但要看题目是否把根定义为第0层还是第1层
树遍历 vs 对应二叉树遍历
- 树先根 <-> 二叉树先序
- 树后根 <-> 二叉树中序
- 这组对应关系极易记反
哈夫曼树不唯一 vs 最优性唯一
- 树形可以不唯一
- 最小 WPL 值一致（最优性一致）

B. 易错点（为什么错 + 怎么改）

n0 = n2 + 1 用错场景
- 错因：默认对空树也套。
- 正解：该式用于非空二叉树。
完全二叉树编号公式套到普通二叉树
- 错因：忘记顺序存储要求“完全二叉树编号语义”。
- 正解：仅在顺序存储且按完全二叉树编号时可直接用 2i/2i+1。
遍历构树只凭一种序列硬构
- 错因：忽略“必须能划分左右子树”。
- 正解：通常需要中序配合（前+中或后+中）。
线索二叉树把线索当孩子继续递归
- 错因：没判断 tag。
- 正解：遍历线索树时先判 ltag/rtag 再决定走法。
WPL 计算把分支结点也算进去了
- 错因：把“结点带权路径和”误当“树的 WPL”。
- 正解：WPL 只统计叶结点。
并查集路径压缩写成“只压当前结点”
- 错因：对递归返回值赋回 parent 的意义不清。
- 正解：S[x] = Find(S, S[x]) 是沿途整条链压缩。

C. 本章做题顺序建议

性质题：先画小树 -> 再代公式
遍历题：先标根位置 -> 再切左右子树
线索题：先看 tag 再看指针
并查集：先找根再合并，合并后别忘规模更新

十五、书签级思维导图复现（第五章，Mermaid）

  mindmap
  root((第5章 树与二叉树))
    5.1 树的基本概念与性质
      术语（双亲/孩子/兄弟/祖先/子孙）
      度、层次、高度、森林
      m叉树与度为m树区别
    5.2 二叉树
      定义与特殊二叉树（满/完全）
      性质（n0=n2+1 等）
      顺序/链式存储
      先中后层遍历
    5.3 构造与线索化
      前+中/后+中 构树
      线索二叉树（ltag/rtag）
      前驱后继查找
    5.4 树森林转换
      左孩子右兄弟法
    5.5 应用
      哈夫曼树与编码
      并查集（Find/Union+优化）

十六、PDF 例题与知识点补充（树与二叉树）

例题 1：树的边数关系

题目：一棵含 n 个结点的树有多少条边？总结点度数和是多少？

答案：边数 n-1，总结点度数和 n-1。

详细解析：

树连通且无环，每新增一个结点只新增一条连接边。
因此总边数固定为 n-1。
树中每条边对应一次“父到子”的度贡献，总度和同为 n-1。

例题 2：m 叉树第 i 层最大结点数

题目：m 叉树第 i 层最多有多少结点（根为第 1 层）？

答案：m^(i-1)。

详细解析：

每层每个结点最多分出 m 个孩子。
层数每增加 1，最大结点数乘以 m。

例题 3：满二叉树结点数

题目：高度为 h 的满二叉树总结点数是多少？

答案：2^h - 1。

详细解析：

各层结点数为 1,2,4,...,2^(h-1)。
等比求和得 2^h-1。

例题 4：完全二叉树高度

题目：含 n>0 个结点的完全二叉树高度是多少？

答案：floor(log2 n) + 1。

详细解析：

完全二叉树按层紧凑填充。
高度由“最后一个结点所在层”决定，直接由二进制数量级得到公式。

例题 5：完全二叉树下标关系（1基）

题目：顺序存储（1基）下，结点 i 的左右孩子与父结点下标关系是什么？

答案：左 2i，右 2i+1，父 floor(i/2)。

详细解析：

完全二叉树顺序编号与层次结构严格对应。
左右孩子在下一层，索引规律由层序位置推得。

例题 6：叶结点与双分支结点关系

题目：非空二叉树中叶结点数 n0 与双分支结点数 n2 关系是？

答案：n0 = n2 + 1。

详细解析：

设单分支结点数为 n1，总结点 n=n0+n1+n2。
边数也满足 n-1 = n1 + 2n2。
联立化简即得 n0=n2+1。

例题 7：遍历序列唯一性判断

题目：哪些遍历组合能唯一确定一棵二叉树？

答案：前序+中序可唯一，后序+中序可唯一，前序+后序一般不能唯一。

详细解析：

中序能提供左右子树分界。
仅前后序缺少分界信息，通常存在多解。

例题 8：层序遍历实现要点

题目：层序遍历的核心实现方式是什么？

答案：使用队列，结点出队后将左右孩子依次入队。

详细解析：

层序是“先访问先扩展”，符合 FIFO。
队列天然保证同层从左到右顺序。

例题 9：中序线索后继查找

题目：中序线索二叉树中如何找某结点后继？

答案：

rtag==1：后继就是 rchild
rtag==0：后继是右子树最左下结点

详细解析：

tag==1 表示对应指针是线索，不是孩子。
tag==0 才需要进入子树继续找极值结点。

例题 10：中序线索前驱查找

题目：中序线索二叉树中如何找某结点前驱？

答案：

ltag==1：前驱就是 lchild
ltag==0：前驱是左子树最右下结点

详细解析：

与后继查找完全对称。
关键是先判 ltag 再决定走线索还是走子树。

例题 11：树转二叉树规则

题目：普通树转二叉树采用什么规则？

答案：左指针指第一个孩子，右指针指下一个兄弟。

详细解析：

该规则保留了“父子”和“兄弟”两类关系。
是树、森林与二叉树互转的基础。

例题 12：哈夫曼树 WPL

题目：哈夫曼树带权路径长度 WPL 如何计算？

答案：WPL = Σ(wi * li)，只统计叶结点。

详细解析：

wi 是叶结点权值，li 是根到该叶路径长度。
分支结点不是原始符号，不计入 WPL。

例题 13：哈夫曼树结点总数

题目：若原始叶子有 n 个，哈夫曼树总结点数是多少？

答案：2n-1。

详细解析：

每次合并两棵树会新增一个内部结点。
从 n 个叶子合并到 1 棵树需 n-1 次合并。
因而总结点 n + (n-1) = 2n-1。

例题 14：并查集 Find

题目：Find 操作本质在做什么？

答案：沿父指针向上追溯直到根结点。

详细解析：

集合由根代表，根满足 parent[root] < 0 或指向自身（视实现而定）。
Find 返回集合代表元。

例题 15：并查集优化效果

题目：按规模合并 + 路径压缩后复杂度特征如何？

答案：单次操作可视为接近 O(1)（严格上为 O(alpha(n))）。

详细解析：

按规模合并降低树高增长。
路径压缩把访问路径结点直接挂到根，后续更快。
两者叠加使均摊复杂度极低。

十七、第五章必背核对表

n0=n2+1 场景（非空二叉树）别用错。
完全二叉树编号公式必须熟练。
构树题优先用中序切左右子树。
线索树查前驱后继要先判 ltag/rtag。
树/森林转二叉树本质是左孩子右兄弟。
WPL 只统计叶结点。
并查集两大优化：按规模合并、路径压缩。

总结

第五章虽然看上去内容很多，但如果按主线整理，其实就是：

树与二叉树的概念和性质
二叉树与树的存储、遍历、构造、转换
两类重点应用：哈夫曼树与并查集

真正必须滚瓜烂熟的内容包括：

树和二叉树的性质公式
完全二叉树的编号关系
四种遍历与由遍历序列构造二叉树
中序线索二叉树查前驱 / 后继
树、森林和二叉树之间的转换本质
哈夫曼树构造与 WPL
并查集的 Find / Union 与两层优化

把这些吃透，第五章就不仅能做题，而且能在脑子里形成一个完整的结构图。

作者：[Austoin]
参考教材：王道考研《数据结构》

引言

图像化理解（Mermaid）

一、树的定义、基本术语与性质

1. 树的定义

2. 树的几个直观特征

3. 基本术语

（1）祖先、子孙、双亲、孩子、兄弟

（2）路径与路径长度

（3）结点的度、树的度

（4）层次、高度、深度

4. 有序树与无序树

5. 森林

6. 树的常考性质

（1）结点数 = 总度数 + 1

（2）m 叉树 与 度为 m 的树 的区别

（3）第 i 层至多有 m^(i-1) 个结点

（4）高度为 h 的 m 叉树至多有 (m^h - 1)/(m - 1) 个结点

（5）高度为 h 的 m 叉树至少有 h 个结点

（6）高度为 h、度为 m 的树至少有 h + m - 1 个结点

（7）具有 n 个结点的 m 叉树最小高度

二、二叉树的定义、特殊二叉树与性质

1. 二叉树的定义

2. 二叉树的两个本质特征

3. 二叉树的五种状态

4. 特殊二叉树

（1）满二叉树

（2）完全二叉树

（3）二叉排序树

（4）平衡二叉树

5. 二叉树的常考性质

（1）n0 = n2 + 1

（2）二叉树第 i 层至多有 2^(i-1) 个结点

（3）高度为 h 的二叉树至多有 2^h - 1 个结点

（4）完全二叉树高度

（5）完全二叉树的编号关系（1 基）

（6）完全二叉树的叶子与分支判定

（7）完全二叉树中 n0、n1、n2 的个数

三、二叉树的存储结构

1. 顺序存储

2. 为什么顺序存储只适合完全二叉树

3. 链式存储

4. 空链域结论

四、二叉树的遍历

1. 什么是遍历

2. 先序、中序、后序遍历

（1）先序遍历

（2）中序遍历

（3）后序遍历

3. 层序遍历

4. 遍历与表达式树

5. 递归遍历的空间复杂度

6. 手算技巧：路过三次法

五、由遍历序列构造二叉树

1. 单独一个遍历序列不能唯一确定二叉树

2. 前序 + 中序

3. 后序 + 中序

4. 层序 + 中序

5. 哪些两两组合仍不能唯一确定

6. 这一类题的核心思想

六、线索二叉树

1. 为什么需要线索二叉树

2. 基本概念

3. 线索二叉树的存储结构

4. 三种线索二叉树

5. 线索化的关键变量 pre

6. 中序线索树中找前驱和后继

找中序后继

找中序前驱

7. 三种线索树的对比

8. 先序 / 后序线索树中不方便的情况

七、树的存储结构

1. 双亲表示法

优缺点

适用场景

2. 孩子表示法

优缺点

适用场景

3. 孩子兄弟表示法（左孩子右兄弟）

4. 三种方法的比较

八、树、森林与二叉树的转换

（2）m 叉树与度为 m 的树的区别

（3）第 i 层至多有 `m^(i-1)` 个结点

（4）高度为 h 的 m 叉树至多有 `(m^h - 1)/(m - 1)` 个结点

（6）高度为 h、度为 m 的树至少有 `h + m - 1` 个结点

（1）`n0 = n2 + 1`

（2）二叉树第 i 层至多有 `2^(i-1)` 个结点

（3）高度为 h 的二叉树至多有 `2^h - 1` 个结点

（7）完全二叉树中 `n0、n1、n2` 的个数

5. 线索化的关键变量 `pre`