首页/考点精讲/数据结构 · 树与森林
考点精讲数据结构大纲 · 树与二叉树

树与森林
所有题都是“数结点”和“走一遍”

数据结构分值最高的一章:选择 3–5 道,算法题常考二叉树遍历的变形(求高度、WPL、判断是否完全/平衡等)。

两个基本功贯穿全章:① 结点数关系(度、叶子、层数);② 遍历(先/中/后/层序)。线索树、树与森林的转换、哈夫曼、并查集、堆,都是在这两个基本功上加的“用途”。

11 个大纲条目 6 类必会题型 3 处仅做理解
00
先看范围

大纲对照

★★★★★ 必考选择 + 算法
  1. 一树的基本概念→ 01
(二)二叉树
  1. 1二叉树的定义及其主要特征→ 02
  2. 2二叉树的顺序存储结构和链式存储结构→ 02
  3. 3二叉树的遍历→ 03
  4. 4线索二叉树的基本概念和构造→ 04
(三)树、森林
  1. 1树的存储结构→ 05
  2. 2森林与二叉树的转换→ 05
  3. 3树和森林的遍历→ 05
(四)树与二叉树的应用
  1. 1哈夫曼(Huffman)树和哈夫曼编码→ 06
  2. 2并查集及其应用→ 07
  3. 3堆及其应用→ 08

二叉排序树、平衡二叉树、红黑树、B 树在大纲里属于“查找”一章,见 DS·7 查找。

本页标为“仅做理解”的内容

后序线索树找后继的细节 · 三叉链表 · 并查集的反阿克曼复杂度证明。

二叉树的一切数量关系都从“结点数 = 边数 + 1”推出来(得到 n0 = n2 + 1);一切算法题都是遍历框架 + 在访问结点时做点事。
01
大纲(一)

树的基本概念与性质

★★★★☆选择
树就是“家谱”:一个祖先(根),每个人有若干孩子,除了根每个人只有一个父亲。结点的度 = 孩子个数;树的度 = 最大的那个结点的度;叶子 = 度为 0 的结点。
一棵 9 个结点的树:根 A;绿色为叶子(6 个);树的度 = 3,高度 = 3。
验证性质 1:Σ度 = 3 + 2 + 3 = 8,n = 8 + 1 = 9。
电脑里的文件夹就是一棵树:磁盘根目录是根,每个文件夹是一个结点,里面的子文件夹是它的孩子,文件是叶子。公司组织架构、族谱、书的目录(章 → 节 → 小节)也都是树。
性质 1:结点数 n = 所有结点的度之和 + 1 (除根外每个结点都对应一条“来自父亲”的边) 性质 2:度为 m 的树第 i 层最多 m^(i−1) 个结点 性质 3:高度为 h 的 m 叉树最多 (m^h − 1)/(m − 1) 个结点 性质 4:n 个结点的 m 叉树最小高度 = ⌈log_m(n(m−1) + 1)⌉

一棵树中度为 4 的结点 20 个、度为 3 的 10 个、度为 2 的 1 个、度为 1 的 10 个,叶子有几个?

n = 1 + 4×20 + 3×10 + 2×1 + 1×10 = 123;非叶结点 = 20+10+1+10 = 41 → 叶子 = 123 − 41 = 82。
这类题永远只用两个等式:n = Σ 度 + 1,n = n0 + n1 + … + nm。
  • “度为 3 的树”至少有一个结点度为 3;“3 叉树”只是规定每个结点最多 3 个孩子,可以一个度为 3 的都没有,甚至可以为空。
  • 高度/深度的层数默认从 1 开始数(根在第 1 层),个别题目从 0 开始,先看题。
02
大纲(二)1–2

二叉树:主要特征与存储结构

★★★★★选择
二叉树每个结点最多两个孩子,而且分左右——只有一个孩子时也要说明是左还是右。所以二叉树不是“度为 2 的树”。

一、必背性质

① n0 = n2 + 1 ← 叶子比双分支结点多 1 ② 第 i 层最多 2^(i−1) 个;高 h 最多 2^h − 1 个 ③ 完全二叉树(n 个结点,编号从 1 开始): 高度 h = ⌊log2 n⌋ + 1 = ⌈log2(n+1)⌉ 结点 i 的父亲 ⌊i/2⌋,左孩子 2i,右孩子 2i+1(不超过 n 才存在) i > ⌊n/2⌋ 的都是叶子 n1 只能是 0 或 1:n 为偶数时 n1 = 1,奇数时 n1 = 0
完全二叉树 = 按编号 1、2、3… 从上到下、从左到右连续排满,只有最后一层右边可以缺。
中图:⌊10/2⌋ = 5,所以 6~10 都是叶子(绿色);n = 10 为偶数,恰有 1 个度为 1 的结点(橙色的 5)。右图缺了 6 号位置(虚线)却有 7 号,编号不连续。

完全二叉树有 768 个结点,叶子有几个?

n 为偶数 → n1 = 1。n = n0 + 1 + n2 且 n0 = n2 + 1 → 768 = 2n0 → n0 = 384。(也可用 n − ⌊n/2⌋ = 384。)

完全二叉树第 6 层有 8 个叶子,该树最多有多少个结点?

“最多”→ 第 6 层还有非叶结点,树有 7 层。第 6 层共 32 个结点,24 个非叶子,各有 2 个孩子 → 第 7 层 48 个。总数 = 63 + 48 = 111。

二、存储结构

方式做法适合
顺序存储按完全二叉树编号放进数组,下标 i 的孩子在 2i、2i+1;空位要留着完全二叉树、堆;一般树会浪费大量空间(最坏高 h 的单支树要 2h − 1 个单元)
二叉链表lchild | data | rchild一般二叉树;n 个结点有 n + 1 个空指针
顺序存储按“完全二叉树编号”放(结点下方小字为编号):B 没有左孩子,下标 4 也得空着。树越“歪”,空着的格子越多。
typedef struct BiTNode { ElemType data; struct BiTNode *lchild, *rchild; } BiTNode, *BiTree;

三叉链表

再加一个 parent 指针,便于向上找父亲(例如后序线索树找后继)。大纲只要求顺序存储和二叉链表。

03
大纲(二)3

二叉树的遍历

★★★★★ 必考选择 + 算法
“先/中/后”说的是根在什么时候被访问:先序 = 根左右,中序 = 左根右,后序 = 左右根。左永远在右前面。层序 = 一层一层从左到右,用队列。
橙色是根 A 的位置:先序在最前、后序在最后、中序把左右子树隔开。
小技巧:把图中结点垂直“压扁”到一条水平线上,从左往右读出来的恰好是中序序列 D B E A F C。
先序像“先报部门名,再依次报下属”(打印目录);后序像“先算完所有子文件夹的大小,才知道父文件夹多大”(统计磁盘占用);层序像“按辈分一代一代点名”。
void PreOrder(BiTree T) { // 改变 visit 的位置就得到中序、后序 if (T == NULL) return; visit(T); // 先序:放在这里 PreOrder(T->lchild); // 中序:放在两次递归之间 PreOrder(T->rchild); // 后序:放在最后 } 时间 O(n);递归栈空间 O(h),最坏 O(n) 层序:根入队;循环 { 出队访问;左孩子非空入队;右孩子非空入队 }
动手试一试:输入层序序列(# 表示空),看四种遍历结果

由遍历序列还原二叉树

必须有中序:先序/后序/层序负责找“谁是根”,中序负责把剩下的分成左右两半。先序 + 后序不能唯一确定一棵二叉树。

先序 A B D E C F,中序 D B E A F C,求后序。

先序第一个 A 是根;中序中 A 左边 D B E 是左子树,右边 F C 是右子树。
左子树:先序 B D E → 根 B,中序 D | B | E → D 左、E 右。右子树:先序 C F → 根 C,中序 F C → F 是 C 的左孩子。
后序:D E B F C A。
每一步:用先序(或后序)找根,用中序把剩下的切成“左 | 根 | 右”,递归到每段只剩一个结点。还原出来就是上面那棵树。
动手试一试:输入任意先序(或后序)+ 中序,看还原过程

几个常考结论

  • 先序和中序相同 → 所有结点没有左孩子(右单支);中序和后序相同 → 没有右孩子;先序和后序相反 → 树高等于结点数(每层一个结点)。
  • n 个结点能构成的不同二叉树个数 = 卡特兰数 C(2n, n) / (n + 1);也是“给定先序序列,可能的二叉树个数”。n = 3 时为 5。
  • 非递归遍历用栈:后序非递归时,栈中保存的恰是当前结点的所有祖先(用于求根到某结点的路径、最近公共祖先)。
算法题常见:求树高、求叶子数、求 WPL(带权路径长度)、判断完全二叉树(层序遇空后不能再有非空)、把表达式树输出成中缀表达式(中序 + 适时加括号)。模板都是“遍历 + 在 visit 处做点事”。
int Depth(BiTree T) { // 求树高:后序框架 if (T == NULL) return 0; int l = Depth(T->lchild), r = Depth(T->rchild); return (l > r ? l : r) + 1; } int WPL(BiTree T, int d) { // 叶子 weight × 深度(根为 0) if (T == NULL) return 0; if (!T->lchild && !T->rchild) return T->weight * d; return WPL(T->lchild, d + 1) + WPL(T->rchild, d + 1); }
04
大纲(二)4

线索二叉树

★★★☆☆选择
二叉链表有 n + 1 个空指针被浪费。把它们利用起来:左指针空着就指向前驱,右指针空着就指向后继(按某种遍历次序)。这些指针叫线索。好处:不用栈也能找到前驱/后继。
中序线索二叉树(中序 D B E A F C):实线是孩子指针,蓝色虚线是线索。
叶子 E 的左线索指向前驱 B、右线索指向后继 A;D 是第一个结点没有前驱,C 是最后一个没有后继,线索为 NULL。
| ltag | lchild | data | rchild | rtag | tag = 0:指针指向孩子 tag = 1:指针是线索(指向前驱 / 后继)
  • 构造:按选定的遍历次序遍历一次,用一个 pre 指针记住“上一个访问的结点”。访问 p 时:p 左空 → p.lchild = pre;pre 右空 → pre.rchild = p。
  • 中序线索树找后继:rtag = 1 → 直接是 rchild;否则 → 右子树里最左下的结点。找前驱对称(左子树最右下)。
  • 先序线索树找后继容易(有左孩子就是左孩子,否则是右指针所指);找前驱需要父指针。

中序 D B E A F C 的二叉树中序线索化后,E 的左、右线索分别指向谁?

E 是叶子,左右都空:左线索指向中序前驱 B,右线索指向中序后继 A。
  • 线索化之后仍然是二叉链表结构,属于物理结构(存储结构)层面的概念。
  • 后序线索树找后继仍然可能需要栈或父指针,不是所有情况都能靠线索解决。

后序线索树找后继的分类讨论

结点是根 → 无后继;是父亲的右孩子,或是左孩子且父亲无右子树 → 后继是父亲;是左孩子且父亲有右子树 → 后继是父亲右子树中后序第一个结点。需要三叉链表,考试只要求知道“后序线索树找后继不方便”。

05
大纲(三)1–3

树、森林的存储、转换与遍历

★★★★☆选择

一、树的三种存储

方式做法找父亲找孩子
双亲表示法数组,每个结点记 parent 下标(根为 −1)快要遍历整个数组
孩子表示法每个结点挂一条孩子链表要遍历快
孩子兄弟表示法二叉链表:firstchild | data | nextsibling麻烦较快;可直接转成二叉树

二、树 / 森林 ⇄ 二叉树:“左孩子,右兄弟”

把每个结点的第一个孩子挂到它的左边,把它的下一个兄弟挂到它的右边。森林就先把每棵树各自转换,再把第 2 棵树的根当成第 1 棵树根的右兄弟,依次挂下去。
E 是 B 的第一个孩子 → 挂在 B 左边;C、D 是 B 的兄弟 → 依次挂在右边(橙色)。树转成的二叉树,根没有右孩子。
森林:每棵树各自转换,再把后一棵树的根当作前一棵树根的右兄弟(橙色 D、F)。
对照遍历:森林先序 A B C D E F G H = 二叉树先序;森林中序 B C A E D G H F = 二叉树中序。

三、遍历的对应关系(必背表)

树森林对应的二叉树
先根遍历先序遍历先序遍历
后根遍历中序遍历(有的书叫后序)中序遍历
  • 树的后根遍历对应二叉树的中序,不是后序——最常见的陷阱。
  • 树没有“中根遍历”(孩子数不定,不知道根放在第几个孩子中间)。

四、常考计数

  • 森林有 n 个结点、m 条边 → 有 n − m 棵树。
  • 森林中叶子数 = 对应二叉树中左指针为空的结点数(没有第一个孩子的就是叶子)。
  • 树中非终端结点数为 k → 对应二叉树中右指针为空的结点数为 k + 1(每个结点的最后一个孩子右指针为空,再加上根)。
06
大纲(四)1

哈夫曼树与哈夫曼编码

★★★★★选择 + 应用
让“出现越频繁的字符路径越短”。做法极其朴素:每次挑两个最小的合并,合并后的新结点再放回去比,直到只剩一个。
带权路径长度 WPL = Σ (叶子权值 × 叶子到根的路径长度) = 所有非叶结点的权值之和(合并时产生的那些和) 性质:n 个叶子 → 合并 n−1 次 → 共 2n − 1 个结点;没有度为 1 的结点 权值越大离根越近;哈夫曼树不唯一,但 WPL 唯一且最小

权值 {2, 3, 4, 7, 8},求哈夫曼树的 WPL。

2+3 = 5 → {4, 5, 7, 8};4+5 = 9 → {7, 8, 9};7+8 = 15 → {9, 15};9+15 = 24。
WPL = 5 + 9 + 15 + 24 = 53。验证:2、3 深度 3,4、7、8 深度 2 → 15 + 8 + 14 + 16 = 53。
每一步只看“森林里所有树的根”,挑最小的两个合并(橙色为新合并出的结点)。WPL = 2×3 + 3×3 + 4×2 + 7×2 + 8×2 = 53。
ZIP、JPEG、MP3 等压缩格式都用到了哈夫曼编码:一篇英文里 e 出现最多,就给它最短的码;z 很少见,码长一点也无所谓,总长度就变短了。
动手试一试:输入任意权值,看哈夫曼树和编码

哈夫曼编码

  • 左分支记 0、右分支记 1,从根到叶子的 0/1 串就是该字符的编码。
  • 它是前缀编码:任何一个编码都不是另一个编码的前缀 → 解码不会有歧义。判断一组编码是否为前缀码:把它们画成二叉树,看是否所有编码都落在叶子上。
  • 与定长编码比:总码长 = WPL(权值为出现次数时)。
k 叉哈夫曼树(外部排序的最佳归并树会用到):若 (n − 1) mod (k − 1) ≠ 0,先补 (k − 1) − (n − 1) mod (k − 1) 个权为 0 的虚结点,再每次取 k 个最小的合并。
07
大纲(四)2

并查集及其应用

★★★★☆选择 + 算法
把元素分成若干互不相交的“帮派”,只需要两个操作:Find(你是哪个帮派的?—— 一路找到老大)和 Union(两个帮派合并 —— 让一个老大认另一个当老大)。用双亲表示法的数组存一片森林即可。
int S[N]; // S[i] = i 的父亲;根结点 S[root] = −1(或 −集合大小) int Find(int x) { while (S[x] >= 0) x = S[x]; return x; } void Union(int r1, int r2) { // r1、r2 必须是两个不同的根 S[r2] = r1; }
S[i] 存父亲下标,根存“−结点数”。集合 {0,1,2,3} 有 4 个结点,比 {4,5,6} 大,所以让根 4 指向 0。Find(3) 沿 3 → 2 → 0 找到根,顺手把 3 直接挂到 0 上,下次只要 1 步。
判断两个人是不是在同一个“朋友圈”:一开始每人自成一圈;“A 和 B 是朋友”就把两圈合并(Union);问“C 和 D 是否认识(间接也算)”就看两人的圈主是不是同一个(Find)。

两个优化

  • 小树并入大树(按大小/秩合并):根存 −(结点数),合并时让小的挂到大的下面 → 树高 ≤ ⌊log2n⌋ + 1,Find 为 O(log n)。
  • 路径压缩:Find 时把沿途所有结点直接挂到根上。两者结合后单次操作几乎是常数。
int Find(int x) { // 路径压缩版 int root = x; while (S[root] >= 0) root = S[root]; while (x != root) { int t = S[x]; S[x] = root; x = t; } return root; }

应用

  • 判断图的连通分量个数:每条边 Union 两端点,最后数根的个数。
  • Kruskal 算法判断加边是否成环:两端点 Find 结果相同 → 成环,舍弃。
  • 判断无向图是否有环、等价类划分。

复杂度 O(α(n))

同时使用按秩合并和路径压缩,m 次操作总时间 O(m·α(n)),α 是反阿克曼函数,实际中不超过 4。证明不要求。

08
大纲(四)3

堆及其应用

★★★★★选择 + 应用
堆 = 一棵完全二叉树(所以用数组存),而且每个结点都不小于它的孩子(大根堆)或不大于孩子(小根堆)。只保证“父子有序”,兄弟之间没有大小关系,所以堆不是二叉排序树。

三个操作

操作做法时间
建堆从最后一个非叶结点 ⌊n/2⌋ 开始,到 1 为止,依次做下沉(和较大的孩子比,小于它就交换,继续往下)O(n)
插入放到末尾,上浮(比父亲大就交换)O(log n)
删除堆顶用最后一个元素替换堆顶,再下沉O(log n)

把 53 17 78 09 45 65 87 32 建成大根堆。

n = 8,从 i = 4 开始:
i=4(09)与孩子 32 交换;i=3(78)与较大孩子 87 交换;i=2(17)与较大孩子 45 交换;i=1(53)与 87 交换,下沉到位置 3 后再与 78 交换。
结果:87 45 78 32 17 65 53 09。
从最后一个非叶结点(i = ⌊8/2⌋ = 4)倒着往前,每个结点和“较大的孩子”比,小了就交换并继续往下(橙色为每步交换的结点)。树和数组是同一份数据的两种看法。
微博热搜“前 10 名”:话题热度不停更新,不需要把所有话题全排序,只维护一个大小为 10 的小根堆——新话题比堆顶(第 10 名)热,就替换堆顶并下沉。医院急诊按病情轻重叫号、操作系统按优先级调度进程,用的都是优先队列(堆)。
动手试一试:建堆、插入、删除堆顶
  • 下沉时和两个孩子中较大的比(大根堆),比较次数每层最多 2 次。
  • 建堆是 O(n) 不是 O(n log n);堆排序整体才是 O(n log n)。
  • 在大根堆中,最小元素一定在叶子上,但不确定是哪个叶子。

应用

  • 优先队列:每次取最大(最小)元素,如进程按优先级调度、Dijkstra 中取最近顶点。
  • 堆排序:见 DS·8 排序。
  • Top-K:从 n 个数中找最小的 k 个 → 维护一个大小为 k 的大根堆,新元素比堆顶小就替换堆顶并下沉,时间 O(n log k)。
  • 多路归并:k 个有序表合并时用小根堆每次挑最小者。
09
收口

自测与考前速览

★★★★★自测
1. 二叉树有 50 个叶子、30 个度为 1 的结点,共多少结点?

n2 = n0 − 1 = 49,n = 50 + 30 + 49 = 129。

2. 哪两种遍历序列组合不能唯一确定二叉树?

先序 + 后序(以及任何不含中序的组合)。

3. 树的后根遍历序列等于对应二叉树的哪种遍历?

中序遍历。

4. 有 n 个叶子的哈夫曼树共有多少结点?

2n − 1。

5. 编码 {0, 10, 110, 111} 和 {0, 01, 11} 哪个是前缀码?

第一组是;第二组中 0 是 01 的前缀,不是。

6. 往大根堆 [87 45 78 32 17 65 53 09] 插入 80,结果?

80 放在位置 9,父亲 32 → 交换;位置 4 的父亲 45 → 交换;位置 2 的父亲 87 → 停。结果:87 80 78 45 17 65 53 09 32。

7. 用并查集求无向图连通分量个数,思路?

初始每个顶点一个集合;对每条边 (u, v),若 Find(u) ≠ Find(v) 则 Union;最后根的个数(S[i] < 0 的个数)就是连通分量数。

五句话

n = Σ度 + 1,二叉树 n0 = n2 + 1。
还原二叉树必须有中序。
左孩子右兄弟;树的后根 = 二叉树中序。
哈夫曼 WPL = 所有合并和之和。
建堆从 ⌊n/2⌋ 倒着下沉,O(n)。

五个易错

① 度为 3 的树 ≠ 3 叉树。
② 完全二叉树 n 为偶数时 n1 = 1。
③ 二叉链表空指针 n + 1 个。
④ 哈夫曼树不唯一,WPL 唯一。
⑤ 堆中兄弟无序,不是 BST。