首页/数据结构/第 5 章 树与二叉树
408 计算机学科专业基础 数据结构 第 5 章

树与二叉树
性质、遍历、哈夫曼与并查集

数据结构分值最高的一章:选择题 3–4 道,算法题也常以二叉树为载体。必会:结点数与度数的关系、完全二叉树性质、由遍历序列还原、树与森林的转换、哈夫曼 WPL。

树描述的是“一对多”的层次关系:文件目录、组织架构、表达式。学会一句话就能解决大部分性质题:除根以外每个结点都恰好被一条边指向。

8 个考点模块 4 个交互模拟器 4 张图
A B C D E F n₀ = 3,n₂ = 2:n₀ = n₂ + 1
00
复习策略

考频地图

★★★★★ 核心章 选择 + 算法题

树是数据结构的重中之重:选择题 3–4 道(性质计算、遍历、线索树、树与森林转换、哈夫曼),算法题也常出在二叉树上(2014 WPL、2017 表达式树、2022 判断二叉排序树)。

考点考频常见问法
树的性质(结点数、度数)★★★★☆“度为 4 的树中……叶结点个数是”
二叉树性质、完全二叉树★★★★★“768 个结点的完全二叉树叶子数”
遍历与还原★★★★★“先序与中序相同的二叉树”“由序列还原”
线索二叉树★★★☆☆“某结点的后继线索指向”
树、森林与二叉树转换★★★★☆“森林 F 的叶结点数等于 T 中……的结点数”
哈夫曼树与编码★★★★☆“WPL”“前缀编码”
并查集★★★☆☆“合并与查找后的数组”
一句话:所有结点数 = 所有结点度数之和 + 1(每个结点除根外都被一条边指向);二叉树 n₀ = n₂ + 1;完全二叉树按层编号,结点 i 的孩子是 2i、2i + 1。遍历序列中“中序”负责分左右,“先序 / 后序”负责定根。
01
5.1 · 性质计算

树的基本概念与性质

★★★★☆ 高频 选择题

结点的度 = 孩子个数;树的度 = 结点度的最大值;度为 0 的是叶结点。结点的深度从根往下数,高度从叶往上数;树的高度(深度)= 最大层数。

① 结点数 n = 所有结点的度数之和 + 1 = 分支(边)数 + 1 ② 度为 m 的树第 i 层至多 mⁱ⁻¹ 个结点 ③ 高为 h 的 m 叉树至多 (mʰ − 1)/(m − 1) 个结点 ④ n 个结点的 m 叉树最小高度 ⌈log_m(n(m − 1) + 1)⌉
#
例(2010 真题):度为 4 的树中,度为 4、3、2、1 的结点分别有 20、10、1、10 个,叶结点几个?
计算
1
度数之和 = 20×4 + 10×3 + 1×2 + 10×1
122
2
结点总数 = 度数之和 + 1
123
3
叶结点 = 总数 − 非叶结点(20 + 10 + 1 + 10)
82
02
5.2 · 必考

二叉树的性质与存储

★★★★★ 必考 选择题
满二叉树(高 3,2³ − 1 = 7 个结点) 完全二叉树(n = 6) 1234567 123456 结点 i:双亲 ⌊i/2⌋,左孩子 2i,右孩子 2i + 1编号与满二叉树一一对应;叶子只在最后两层,最后一层靠左
图 5-1 满二叉树与完全二叉树。完全二叉树就是“按层序编号,编号与同高满二叉树前 n 个结点一一对应”的二叉树。
① n₀ = n₂ + 1  (推导:n = n₀ + n₁ + n₂,分支数 n − 1 = n₁ + 2n₂) ② 第 i 层至多 2ⁱ⁻¹ 个结点;高为 h 至多 2ʰ − 1 个结点 ③ n 个结点的完全二叉树:高度 ⌊log₂n⌋ + 1 = ⌈log₂(n + 1)⌉ ④ 完全二叉树中 i ≤ ⌊n/2⌋ 是分支结点,i > ⌊n/2⌋ 是叶子 → 叶子数 = ⌈n/2⌉ ⑤ 完全二叉树中度为 1 的结点只有 0 或 1 个(n 为偶数时有 1 个)
#
例(2009 真题):768 个结点的完全二叉树,叶结点个数?
计算
1
分支结点编号 1 ~ ⌊768/2⌋
1 ~ 384
2
叶子 = 768 − 384
384
3
校验:n 为偶数,有 1 个度为 1 的结点,n₂ = 383,n₀ = n₂ + 1
384 ✓

存储结构

顺序存储:按完全二叉树编号放进数组,适合完全二叉树(一般二叉树会浪费大量空位,最坏高 h 的单支树要 2ʰ − 1 个单元)。二叉链表:每个结点 lchild、data、rchild;n 个结点共 2n 个指针,其中只有 n − 1 个指向孩子,空指针 n + 1 个。

  • n₀ = n₂ + 1 对任意二叉树成立,与 n₁ 无关。
  • “完全二叉树”≠“满二叉树”;满二叉树一定是完全二叉树。
  • 具有 n 个结点的不同形态二叉树有 C(2n, n)/(n + 1) 种(卡特兰数)。
03
5.3 · 必考

遍历与还原

★★★★★ 必考 选择 + 算法题
递归遍历(改变 visit 的位置)
void PreOrder(BiTree T) {
    if (T) {
        visit(T);           // 先序:根在前
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
}
// 中序:visit 放中间;后序:放最后
层序遍历(队列)
InitQueue(Q); EnQueue(Q, T);
while (!IsEmpty(Q)) {
    DeQueue(Q, p); visit(p);
    if (p->lchild) EnQueue(Q, p->lchild);
    if (p->rchild) EnQueue(Q, p->rchild);
}

三种递归遍历时间都是 O(n),空间是递归栈深度 O(h)。非递归遍历用栈模拟:中序“一路向左压栈,弹出访问再转向右子树”;后序需要记录“右子树是否已访问”。

由遍历序列还原二叉树

先序 + 中序、后序 + 中序、层序 + 中序都能唯一确定一棵二叉树;先序 + 后序不能(无法区分只有一个孩子时是左还是右)。

形态判断题:“先序序列与中序序列相同的二叉树”→ 根-左-右 = 左-根-右,说明每个结点都没有左子树(只有右单支)。“先序与后序相反”→ 每层只有一个结点(高度 = 结点数)。“前序和后序相同”→ 只有根结点。

04
5.4 · 中频

线索二叉树

★★★☆☆ 中频 选择题
ABCDE D 的前驱:NULLC 的后继:NULL 中序序列:D B E A C 空的左指针 → 指向中序前驱(ltag = 1) 空的右指针 → 指向中序后继(rtag = 1) n 个结点有 n + 1 个空指针, 全部用来存线索 虚线 = 线索
图 5-2 中序线索二叉树。线索化后,不用栈就能找到任一结点在中序序列中的前驱和后继。

结点结构:lchild | ltag | data | rtag | rchild;tag = 0 表示指向孩子,tag = 1 表示线索。在中序线索树中找后继:若 rtag = 1 直接取;否则后继是右子树最左下的结点。后序线索树找后继仍可能需要知道双亲(要用三叉链表或栈),所以后序线索化后遍历仍不方便。

05
5.5 · 高频

树、森林与二叉树

★★★★☆ 高频 选择题

树的三种存储:双亲表示法(数组,每个结点记双亲下标,找双亲 O(1)、找孩子要遍历)、孩子表示法(每个结点的孩子串成链表)、孩子兄弟表示法(二叉链表:左指针指第一个孩子,右指针指下一个兄弟)——这就是树与二叉树相互转换的依据。

一棵树 RABCDEF 左孩子右兄弟 对应的二叉树 RADBECF 蓝 = 左孩子(第一个孩子)橙 = 右孩子(下一个兄弟) 根没有兄弟,所以根的右子树为空
图 5-3 树 → 二叉树:“左孩子右兄弟”。森林 → 二叉树:先把每棵树转成二叉树,再把第二棵树的根作为第一棵树根的右孩子,依此类推。
树森林对应二叉树
先根遍历先序遍历先序遍历
后根遍历中序遍历(有的教材称后序)中序遍历
  • 树转二叉树后,二叉树根结点没有右孩子;森林转二叉树后根结点可以有右孩子。
  • 森林 F 中叶结点个数 = 对应二叉树中左指针为空的结点个数(没有第一个孩子 ⇔ 叶子)。
  • 森林的二叉树中,根的右链上结点数 = 森林中树的棵数。
06
5.6 · 高频

哈夫曼树与编码

★★★★☆ 高频 选择 + 计算

带权路径长度 WPL = Σ(叶子权值 × 叶子到根的路径长度)。WPL 最小的二叉树叫哈夫曼树(最优二叉树)。构造:每次选两棵根权值最小的树合并,直到只剩一棵。

  • 哈夫曼树中没有度为 1 的结点;n 个叶子共 2n − 1 个结点。权值越大离根越近。
  • 哈夫曼树不唯一(左右可交换、权值相同时选择不同),但 WPL 唯一且最小。
  • 前缀编码:没有一个编码是另一个编码的前缀,解码不会有歧义。哈夫曼编码是前缀编码,且平均码长最短。判断“是否前缀编码”的方法:把编码画成二叉树,所有编码都应在叶子上。
  • k 叉哈夫曼树:若 (n − 1) % (k − 1) ≠ 0,先补 k − 1 − (n − 1) % (k − 1) 个权为 0 的虚结点(用于最佳归并树,第 8 章)。
07
5.7 · 中频

并查集

★★★☆☆ 中频 选择题

并查集用双亲表示法的数组存储一组不相交集合:parent[i] 是 i 的双亲,根结点存负数(其绝对值为集合大小)。两个操作:Find(x) 找 x 所在树的根;Union(a, b) 把一个根挂到另一个根下。

Union:小树的根挂到大树的根下 012435 parent[3] = 0 Find 时路径压缩 024 024… 查找 4 的根后,把路径上所有结点直接挂到根下
图 5-4 并查集的两个优化:按大小(或高度)合并让树尽量矮;查找时路径压缩把路径上的结点直接挂到根下。
int Find(int S[], 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;
}
void Union(int S[], int r1, int r2) {   // r1、r2 是根
    if (S[r2] > S[r1]) { S[r1] += S[r2]; S[r2] = r1; }   // r2 更小,挂到 r1 下
    else { S[r2] += S[r1]; S[r1] = r2; }
}

不优化时 Find 最坏 O(n);按大小合并后树高 ≤ ⌊log₂n⌋ + 1,Find 为 O(log n);再加路径压缩,均摊接近 O(1)(O(α(n)))。并查集用于 Kruskal 判环、判断图的连通分量。

08
实战

真题与自测

★★★★★ 收口 选择 + 算法题

一、真题问法

问法 1:“若一棵完全二叉树有 768 个结点,则叶结点个数是?”→ 384。

问法 2:“将森林 F 转换为对应的二叉树 T,F 中叶结点的个数等于?”→ T 中左孩子指针为空的结点个数。

问法 3(2014 算法题):“求二叉树的 WPL(叶结点 weight 已知)”→ 先序或层序遍历,记录深度,遇到叶子累加 weight × depth。

问法 4(2017 算法题):“把表达式树转换为带括号的中缀表达式”→ 中序遍历,非叶子且非根结点时在左右两边加括号。

二、折叠自测

1. 二叉树有 10 个度为 2 的结点、5 个度为 1 的结点,叶结点几个?

n₀ = n₂ + 1 = 11。

2. 完全二叉树有 1001 个结点,叶子几个?

⌈1001/2⌉ = 501(n 为奇数,没有度为 1 的结点)。

3. n 个结点的二叉链表中有几个空指针?

n + 1 个。

4. 先序为 ABDECF、中序为 DBEAFC,后序是?

DEBFCA。

5. 权值 7、5、2、4 的哈夫曼树 WPL?

35(2 和 4 合并为 6,5 和 6 合并为 11,7 和 11 合并为 18;6 + 11 + 18 = 35)。

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

先序 + 后序。

三、考前速览

4 句话

n = 度数和 + 1。
n₀ = n₂ + 1。
完全二叉树叶子 = ⌈n/2⌉。
树先根 = 二叉树先序,后根 = 中序。

3 个易错

① 先序 + 后序不能确定二叉树。
② 哈夫曼树没有度为 1 的结点。
③ 后序线索树找后继仍需双亲信息。