第9章树和图

2.1二叉树基本概念

定义：每个结点最多有两个子结点，分别称为左孩子和右孩子（左右有顺序，不能颠倒）。

重要性质（务必记牢）

第 i 层最多有 2^(i-1) 个结点（根算第 1 层）。
深度为 k 的二叉树最多有 2^k - 1 个结点。
度为 0 的结点数 n0 = 度为 2 的结点数 n2 + 1（即叶子数 = 双孩子结点数 + 1）。
有 n 个结点的二叉树，深度至少为 ⌈log₂(n+1)⌉。

存储方式

链式存储（最常用）：

struct TreeNode {
    int val;
    TreeNode *l, *r;
    TreeNode(int v) : val(v), l(nullptr), r(nullptr) {}
};

顺序存储（适合完全二叉树）：下标 i 的结点，左孩子 2i、右孩子 2i+1、父结点 i/2（下标从 1 开始）。

2.2 四种遍历

设遍历顺序记为 D=访问根，L=遍历左子树，R=遍历右子树。

遍历	顺序	典型用途
前序（Pre-order）	D L R	复制树、序列化、打印目录结构
中序（In-order）	L D R	BST 中序得到递增序列
后序（Post-order）	L R D	释放树、求子树信息（如子树和）
层序（Level-order）	逐层从左到右	BFS 输出、建树、求深度

递归实现（最简洁，考试首选）

void pre (TreeNode* t) { if (!t) return; cout << t->val; pre (t->l); pre (t->r); }
void in  (TreeNode* t) { if (!t) return; in  (t->l); cout << t->val; in  (t->r); }
void post(TreeNode* t) { if (!t) return; post(t->l); post(t->r); cout << t->val; }

层序（用队列）

void level(TreeNode* t) {
    if (!t) return;
    queue<TreeNode*> q; q.push(t);
    while (!q.empty()) {
        TreeNode* u = q.front(); q.pop();
        cout << u->val << ' ';
        if (u->l) q.push(u->l);
        if (u->r) q.push(u->r);
    }
}

非递归前序（用栈，理解即可）：栈先压右孩子再压左孩子，循环弹出访问。

2.3 由遍历序列还原二叉树

前序 + 中序 或 后序 + 中序 可唯一确定一棵二叉树（中序提供左右划分，前/后序提供根）。
仅有前序+后序不能唯一确定（左右子树划分不清）。
思路：前序首元素为根 → 在中序中找到根，左边是左子树、右边是右子树 → 递归构造。

经典应用：表达式树（前/后序表达式求值）、根据遍历序列重建树、求树高/直径、统计叶子数。 易错点：① 中序遍历的"中"指根在中间，不是数值中间；② 递归遍历务必写 if(!t) return; 终止条件；③ 层序用队列而非栈；④ 左右子树顺序不能反。

3、特殊树：完全二叉树 / 哈夫曼树 / 二叉搜索树（BST）

3.1 完全二叉树（Complete Binary Tree）

定义：除最后一层外，其他各层都填满；且最后一层结点从左往右连续排列（不能有"空档"）。

与满二叉树区别：满二叉树每层都满（深度 k 共 2^k-1 结点）；完全二叉树最后一层可不满，但必须左连续。

性质与好处

可用数组顺序存储（下标 1 起），父 i/2、左 2i、右 2i+1，无指针、省空间、访问快。
堆（参见提高级）就是建立在完全二叉树上的。

易错点：完全二叉树要求"最后一层从左到右连续"，若某层中间缺结点则不是完全二叉树。

3.2 哈夫曼树（Huffman Tree）

定义：给定一组带权叶子结点，带权路径长度（WPL, Weighted Path Length）最小的二叉树。WPL = Σ(叶子权值 × 该叶子到根的路径长度)。

构造算法（贪心）

把所有叶子权值放入最小堆（优先队列）。
每次取出权值最小的两个结点 a、b，合并为一个新结点（权值 a+b），放回堆。
重复直到堆中只剩一个结点，即为哈夫曼树的根；合并过程产生的总代价 a+b 之和即 WPL。

#include <queue>
using P = priority_queue<int, vector<int>, greater<int>>; // 小根堆
int huffman(vector<int>& w) {
    P pq; for (int x : w) pq.push(x);
    int ans = 0;
    while (pq.size() > 1) {
        int a = pq.top(); pq.pop();
        int b = pq.top(); pq.pop();
        ans += a + b;          // 累加本次合并代价
        pq.push(a + b);
    }
    return ans;                // 返回 WPL
}

重要性质

哈夫曼树没有度为 1 的结点（要么 0 个孩子，要么 2 个）。
若有 n 个叶子，则总结点数为 2n - 1。

经典应用：哈夫曼编码——出现频率高的字符用短码、低的用长码，且是前缀码（任何字符的编码都不是另一字符编码的前缀），实现无损压缩。 易错点：① 合并时取"最小的两个"，不是任意两个；② WPL 是所有合并代价之和；③ 哈夫曼树形态不唯一，但 WPL 唯一。

3.3 二叉搜索树（BST, Binary Search Tree）

定义：左子树所有结点值 < 根值，右子树所有结点值 > 根值（ BST 性质），且左右子树也都是 BST。通常不允许重复值（或统一放左/右）。

核心操作

查找（O(高度)，平衡时 O(log n)）：

TreeNode* find(TreeNode* t, int v) {
    while (t && t->val != v) {
        if (v < t->val) t = t->l;
        else             t = t->r;
    }
    return t;   // 找到返回指针，否则 nullptr
}

插入（递归，O(高度)）：

TreeNode* insert(TreeNode* t, int v) {
    if (!t) return new TreeNode(v);
    if (v < t->val) t->l = insert(t->l, v);
    else if (v > t->val) t->r = insert(t->r, v);
    return t;
}

删除（三种情况，O(高度)）：
- 叶子：直接删。
- 只有一个孩子：用孩子顶替。
- 有两个孩子：用右子树最小结点（或左子树最大结点）的值替换根，再递归删除那个最小结点。

TreeNode* del(TreeNode* t, int v) {
    if (!t) return nullptr;
    if (v < t->val) t->l = del(t->l, v);
    else if (v > t->val) t->r = del(t->r, v);
    else {
        if (!t->l) { TreeNode* r = t->r; delete t; return r; }
        if (!t->r) { TreeNode* l = t->l; delete t; return l; }
        TreeNode* mn = t->r; while (mn->l) mn = mn->l; // 右子树最小
        t->val = mn->val;
        t->r = del(t->r, mn->val);
    }
    return t;
}

重要性质：中序遍历 BST 得到严格递增序列（这是验证/利用 BST 的关键）。 退化风险：若插入有序数据（如 1,2,3,4…），BST 退化为链，高度 O(n)，操作变慢。引出提高级的平衡树（AVL / 红黑树 / Treap / Splay）——CSP-J 不要求实现，但要知道"BST 可能退化"。

经典应用：动态有序集合、排行榜、前缀统计（配合扩展）。 易错点：① 插入/删除后必须返回新子树根并接回父结点；② 中序递增是 BST 的判据；③ 有序插入会退化成链。

4、图的存储：邻接矩阵 / 邻接表

图由顶点（点）和边组成。边可带权（权值表示距离/代价等）。根据边是否有方向分有向图/无向图，根据边是否带权分带权图/无权图。

4.1 邻接矩阵（Adjacency Matrix）

定义：用二维数组 g[u][v] 表示边。

无权图：g[u][v] = 1 表示有边，0 表示无边。
带权图：g[u][v] = 边权，无边设为 0 或 INF。

const int N = 1005, INF = 0x3f3f3f3f;
int g[N][N];
// 初始化：无边为 INF，自身为 0
memset(g, 0x3f, sizeof g);
for (int i = 1; i <= n; i++) g[i][i] = 0;
// 加边（无向图要双向）
g[u][v] = w; g[v][u] = w;   // 无向
g[u][v] = w;                // 有向

性质

无向图的邻接矩阵对称（g[u][v]==g[v][u]）；有向图不一定。
空间复杂度 O(n²)，与边数无关。
判断两点是否相邻：O(1)。
遍历所有边 / 枚举邻接点：O(n²)。

适用场景：稠密图（边数接近 n²），或需要快速判断两点是否相连时。

4.2 邻接表（Adjacency List）

定义：为每个顶点维护一个链表 / 动态数组，存放它直接相连的顶点（及边权）。C++ 中用 vector 最方便。

const int N = 100005;
vector<int> g[N];                       // 无权图：存邻接点编号
vector<pair<int,int>> w[N];             // 带权图：存 (邻接点, 边权)
// 加边（无向图双向）
g[u].push_back(v); g[v].push_back(u);
w[u].push_back({v, wt}); w[v].push_back({u, wt});
// 遍历 u 的所有邻居
for (int v : g[u]) { /* 处理边 u->v */ }
for (auto& e : w[u]) { int v = e.first, wt = e.second; /* ... */ }

性质

空间复杂度 O(n + m)（n 顶点、m 边），与稠密程度无关。
枚举某点所有邻接点：O(该点度数)。
判断两点是否相邻：O(度数)（链表）或借助 set（更慢）。

适用场景：稀疏图（边数远小于 n²），是竞赛中最常用的存图方式。

对比速查

维度	邻接矩阵	邻接表
空间	O(n²)	O(n+m)
判边 (u,v)	O(1)	O(度)
遍历某点邻居	O(n)	O(度)
适合	稠密图	稀疏图

经典应用：DFS/BFS 遍历、最短路（Dijkstra/Bellman-Ford）、最小生成树、拓扑排序（均基于邻接表/矩阵）。 易错点：① 无向图加边要双向；② 数组大小 N 要够（顶点编号从 1 起时开 N+1）；③ 带权图注意 INF 相加溢出，比较时用 if (new < dis[v]) 而非先加后比；④ 重边/自环的处理按题意。

5 重要性质与易错点

无法保证无冲突，哈希表提供的是期望/平均 O(1)，最坏 O(n)（所有 key 冲突）。
哈希函数要分散：M 用质数、key 含多位信息时混合高位低位，可显著降冲突。
字符串哈希的陷阱：单模 MOD 有极小概率碰撞，重要场景可用**双模（双哈希）**降低误判。
开放寻址删除用懒惰删除，不能直接置空。
装填因子过大要扩容 rehash（提高级内容，CSP-J 了解即可）。

经典应用：离散化的"值→编号"映射、字符串判重/匹配、集合去重、计数统计（替代 map 提速）。

附录：复杂度速查表（CSP-J 必记）

结构 / 操作	时间复杂度	备注
链表插入/删除（已知位置）	O(1)	查找 O(n)
栈 / 队列入/出	O(1)	顺序/循环实现
二叉树遍历	O(n)	n 为结点数
BST 查找/插入/删除	平均 O(log n)，最坏 O(n)	有序插入退化为链
完全二叉树数组访问	O(1)	父 i/2，左 2i，右 2i+1
哈夫曼建树	O(n log n)	用优先队列
邻接矩阵判边	O(1)	空间 O(n²)
邻接表遍历全图	O(n+m)	空间 O(n+m)
哈希表增/删/查	平均 O(1)	最坏 O(n)

本手册覆盖 CSP-J（入门级）数据结构全部要求点；其中 平衡树实现、线段树、Trie、并查集、图论算法、字符串 KMP/Manacher 等属提高级（CSP-S），不在本册范围内，可在《CSP-S 提高级英文词汇表》中衔接。

本章在原教材中同样以 练习题/选择题 为主，没有独立的知识讲解部分。以下按教材原有顺序整理。

:::

1. 二叉树遍历

二叉树 T，已知其前序遍历序列为：

1 2 4 3 5 7 6

中序遍历序列为：

4 2 1 5 7 3 6

则其后序遍历序列为（）。

A. 4 2 5 7 6 3 1
B. 4 2 7 5 6 3 1
C. 4 2 7 5 3 6 1
D. 4 7 2 3 5 6 1

查看答案

答案：B

2. 前序遍历与后序遍历

前序遍历序列与后序遍历序列相同的二叉树为（）。

A. 非叶子结点只有左子树的二叉树
B. 只有根结点的二叉树
C. 根结点无右子树的二叉树
D. 非叶子结点只有右子树的二叉树

查看答案

答案：B

3. 完全二叉树的高度

如果根的高度为 1，具有 61 个结点的完全二叉树的高度为（）。

A. 5
B. 6
C. 7
D. 8

查看答案

答案：B

4. 满二叉树的结点数

一棵具有 5 层结点的满二叉树的结点数为（）。

A. 31
B. 32
C. 33
D. 16

查看答案

答案：A

5. 表达式的后缀形式

表达式：

a * (b + c) * d

的后缀形式是（）。

A. a b c d * + *
B. a b c + * d *
C. a * b c + * d
D. b + c * a * d

查看答案

答案：B

6. 有向图的度

有向图中每个顶点的度等于该顶点的（）。

A. 入度
B. 出度
C. 入度和出度之和
D. 入度和出度之差

查看答案

答案：C

7. 无向图顶点度数之和

在无向图中，所有顶点的度数之和是边数的（）倍。

A. 0.5
B. 1
C. 2
D. 4

查看答案

答案：C

8. 完全无向图与生成树

设 G 是有 6 个结点的完全无向图，要得到一棵生成树，需要从 G 中删去（）条边。

A. 6
B. 9
C. 10
D. 15

查看答案

答案：C

9. 连通图变成树

设 G 是有 n 个结点、m 条边（n ≤ m）的连通图，必须删去 G 的（）条边，才能使得 G 变成一棵树。

A. m - n + 1
B. m - n
C. m + n + 1
D. n - m + 1

查看答案

答案：A

10. 简单无向连通图

由四个没有区别的点构成的简单无向连通图的个数是（）。

A. 6
B. 7
C. 8
D. 9

查看答案

答案：A

2.1二叉树基本概念​

2.2 四种遍历​

2.3 由遍历序列还原二叉树​

3、特殊树：完全二叉树 / 哈夫曼树 / 二叉搜索树（BST）​

3.1 完全二叉树（Complete Binary Tree）​

3.2 哈夫曼树（Huffman Tree）​

3.3 二叉搜索树（BST, Binary Search Tree）​

4、图的存储：邻接矩阵 / 邻接表​

4.1 邻接矩阵（Adjacency Matrix）​

4.2 邻接表（Adjacency List）​

5 重要性质与易错点​

附录：复杂度速查表（CSP-J 必记）​

1. 二叉树遍历​

2. 前序遍历与后序遍历​

3. 完全二叉树的高度​

4. 满二叉树的结点数​

5. 表达式的后缀形式​

6. 有向图的度​

7. 无向图顶点度数之和​

8. 完全无向图与生成树​

9. 连通图变成树​

10. 简单无向连通图​

2.1二叉树基本概念

2.2 四种遍历

2.3 由遍历序列还原二叉树

3、特殊树：完全二叉树 / 哈夫曼树 / 二叉搜索树（BST）

3.1 完全二叉树（Complete Binary Tree）

3.2 哈夫曼树（Huffman Tree）

3.3 二叉搜索树（BST, Binary Search Tree）

4、图的存储：邻接矩阵 / 邻接表

4.1 邻接矩阵（Adjacency Matrix）

4.2 邻接表（Adjacency List）

5 重要性质与易错点

附录：复杂度速查表（CSP-J 必记）

1. 二叉树遍历

2. 前序遍历与后序遍历

3. 完全二叉树的高度

4. 满二叉树的结点数

5. 表达式的后缀形式

6. 有向图的度

7. 无向图顶点度数之和

8. 完全无向图与生成树

9. 连通图变成树

10. 简单无向连通图