前面学的数组、链表、栈、队列都是线性结构,元素一个接一个排成一条线。但很多关系不是线性的:家谱、文件夹、组织架构,都是层层嵌套的。描述这种层次关系,要用树。
本章的知识点与 GESP、CSP-J/S 大纲的对应关系如下。
| 考试 | 大纲要求 | 本章位置 |
|---|---|---|
| GESP C++ 六级 | 考点 1:树的基本概念,构造与遍历;考点 2:哈夫曼树、完全二叉树、二叉排序树;考点 3:哈夫曼编码 | 全章 |
| CSP-J/S 入门级 | 3.2 简单树:树的定义与相关概念、表示与存储、二叉树及遍历 | 树的基本概念、二叉树与遍历 |
| CSP-J/S 入门级 | 3.3 特殊树:完全二叉树、哈夫曼树与哈夫曼编码、二叉搜索树 | 完全二叉树、二叉搜索树、哈夫曼树 |
树的基本概念
树由节点和连接节点的边组成,并且满足:有且仅有一个根节点,除根以外的每个节点有且仅有一个父节点。
几个必须记住的术语:
| 术语 | 含义 |
|---|---|
| 根节点 | 最上面那个没有父节点的节点 |
| 父节点、子节点 | 相邻两层中,上层是下层节点的父节点 |
| 兄弟节点 | 同一个父节点的节点 |
| 叶子节点 | 没有子节点的节点 |
| 节点的度 | 该节点拥有的子节点个数 |
| 树的度 | 所有节点中最大的度 |
| 节点的深度 | 从根到该节点经过的边数,根的深度是 0 |
| 树的高度 | 所有节点深度的最大值加 1,也叫深度 |
二叉树
每个节点最多有两个子节点的树叫二叉树,两个子节点分别叫左孩子和右孩子。左右是有区别的,交换左右子树会得到另一棵不同的二叉树。
两种特殊的二叉树:
- 满二叉树。每一层的节点数都达到最大,也就是除了叶子,每个节点都有两个孩子。
- 完全二叉树。除了最后一层,其它层都填满,最后一层的节点全部靠左排列。满二叉树一定是完全二叉树,反过来不成立。
二叉树的重要性质
设二叉树中度为 0(叶子)、度为 1、度为 2 的节点数分别是 n_0、n_1、n_2。
- 第
i层最多有2^{i-1}个节点(根是第 1 层)。 - 深度为
k的二叉树最多有2^k - 1个节点。 - 叶子数与度为 2 的节点数满足
n_0 = n_2 + 1。 n个节点的完全二叉树,深度是\lfloor \log_2 n \rfloor + 1。
最后一条常考。比如 1000 个节点的完全二叉树,深度是 \lfloor \log_2 1000 \rfloor + 1 = 9 + 1 = 10。
二叉树的存储
顺序存储
把二叉树按「从上到下、从左到右」编号,存进数组。如果节点从下标 1 开始编号,那么:
| 关系 | 下标 |
|---|---|
节点 i 的左孩子 |
2i |
节点 i 的右孩子 |
2i + 1 |
节点 i 的父节点 |
\lfloor i / 2 \rfloor |
这种存法只适合完全二叉树。如果树很稀疏(比如一条链),数组里会大片空着,浪费空间。
链式存储
一般二叉树用链式存储,每个节点存数据和左右孩子指针。
struct Node {
char data;
Node *left;
Node *right;
Node(char c) : data(c), left(NULL), right(NULL) {}
};二叉树的遍历
遍历就是按某种顺序访问每个节点一次。四种方式:
| 遍历 | 顺序 | 名字的由来 |
|---|---|---|
| 前序 | 根 → 左 → 右 | 根最先访问 |
| 中序 | 左 → 根 → 右 | 根在中间访问 |
| 后序 | 左 → 右 → 根 | 根最后访问 |
| 层序 | 一层一层从左到右 | 按层访问 |
前三种用递归写最自然。
void preorder(Node *p) { // 前序
if (p == NULL) return;
cout << p->data << " ";
preorder(p->left);
preorder(p->right);
}
void inorder(Node *p) { // 中序
if (p == NULL) return;
inorder(p->left);
cout << p->data << " ";
inorder(p->right);
}
void postorder(Node *p) { // 后序
if (p == NULL) return;
postorder(p->left);
postorder(p->right);
cout << p->data << " ";
}层序要用队列。
void levelorder(Node *root) {
if (root == NULL) return;
queue<Node*> q;
q.push(root);
while (!q.empty()) {
Node *p = q.front();
q.pop();
cout << p->data << " ";
if (p->left != NULL) q.push(p->left);
if (p->right != NULL) q.push(p->right);
}
}由遍历序列还原二叉树
这是初赛的高频题。
- 已知前序 + 中序,可以唯一确定一棵二叉树。
- 已知后序 + 中序,可以唯一确定一棵二叉树。
- 已知前序 + 后序,不能唯一确定(分不清左右孩子)。
思路是:前序的第一个元素一定是根,在它后面的中序序列里找到这个根,左边就是左子树的中序,右边是右子树的中序。按中序里的左右长度,把前序也切成两段,递归下去即可。
二叉搜索树
二叉搜索树(BST,也叫二叉排序树)在二叉树的基础上加了一条约束:
- 左子树所有节点的值都小于根节点。
- 右子树所有节点的值都大于根节点。
它最重要的性质是:中序遍历的结果是从小到大有序的。要判断一棵树是不是二叉搜索树,中序遍历走一遍看是否递增就行。
查找和插入都是沿着一条路径走,每步排除一半,平均复杂度 O(\log n)。
Node* insert(Node *p, int x) {
if (p == NULL) {
Node *q = new Node(x);
return q;
}
if (x < p->data) p->left = insert(p->left, x);
else if (x > p->data) p->right = insert(p->right, x);
return p;
}但二叉搜索树有个致命弱点:如果按 1、2、3、4、5 的顺序插入,它会退化成一条链,查找变成 O(n)。要避免退化,得用平衡树(如 AVL、红黑树),那属于提高级内容。竞赛里 O(\log n) 的查找一般直接用 STL 的 set 和 map。
哈夫曼树
给定一组带权值的叶子节点,构造一棵二叉树,使得所有叶子的带权路径长度(叶子权值 × 到根的边数,求和)最小。这样的树叫哈夫曼树,也叫最优二叉树。
构造方法是贪心:
- 把所有节点放进一个集合,每个节点是一棵单独的树。
- 取出权值最小的两棵树,合并成一棵新树,新树的权值是两者之和。
- 把新树放回集合。
重复到只剩一棵树。用优先队列(小根堆)可以高效实现。
例:权值 1、2、3、4。
- 取 1、2 合并成 3,集合变成 {3, 3, 4}。
- 取 3、3 合并成 6,集合变成 {4, 6}。
- 取 4、6 合并成 10,结束。
带权路径长度:4 的深度是 1,3 的深度是 2,1 和 2 的深度是 3。
4 \times 1 + 3 \times 2 + 1 \times 3 + 2 \times 3 = 4 + 6 + 3 + 6 = 19
哈夫曼编码是哈夫曼树的直接应用。规定往左走记 0,往右走记 1,每个叶子就得到一串编码。
它有两个特点:
- 前缀码。任何一个编码都不是另一个编码的前缀,所以解码时不会混淆。
- 最优性。出现频率高的字符编码短,频率低的编码长,整体编码长度最短。
2020 年 CSP-J 第一轮考过哈夫曼编码的选择题,给一组频率和一个编码表,判断哪组编码合法。判断方法就是看是否满足前缀性质。
复杂度
| 操作 | 普通二叉树 | 二叉搜索树(平均) | 二叉搜索树(最坏) |
|---|---|---|---|
| 遍历 | O(n) |
O(n) |
O(n) |
| 查找 | O(n) |
O(\log n) |
O(n) |
| 插入 | O(1) |
O(\log n) |
O(n) |
常见易错点
- 树的深度和高度容易搞混。深度从根往下数(根为 0),高度从叶子往上数(叶子为 1),两者数值相等。
- 二叉树第
i层最多2^{i-1}个节点,根是第 1 层,不是第 0 层。 - 完全二叉树的顺序存储下标从 1 开始,父节点才是
\lfloor i/2 \rfloor;从 0 开始公式会变。 - 只有前序 + 后序不能还原二叉树,必须有一个中序。
- 二叉搜索树不能解决平衡问题,输入有序就会退化成链表。
- 哈夫曼编码的合法性看前缀性质,不是看长度。
- 满二叉树只判「左右高度相等」。左子树满、右子树是高度相同的链,高度相等但不是满二叉树,必须同时要求左右子树都满。
- 完全二叉树用「高度差不超过 1」判定。这个条件只是必要条件,不充分;正确判据是层序编号的最大值等于结点数。
- 树上统计忘记后序。
full[u]依赖full[l]、full[r],先算自己一定错。 - 链状树上递归爆栈。
n = 10^5的链,递归深度就是10^5,需要改成迭代或显式栈。
练习
练习 1:满二叉树子树计数
在线评测练习:P1185 满二叉树
GESP C++ 2026.06 · 六级题 2
题目描述
给定一棵包含 n 个结点的有根二叉树,根结点编号为 1。对于结点 i,其左儿子编号为 l_i、右儿子编号为 r_i(不存在则为 0)。
树中每个结点都对应一棵以其为根的子树。求所有 n 棵子树中,有多少棵是满二叉树。
满二叉树:所有叶子深度均相同,且除叶子外每个结点都有两个儿子。
输入格式
第一行一个正整数 n;接下来 n 行,每行两个非负整数 l_i、r_i。
输出格式
输出一行一个整数,表示满二叉树子树的数量。
输入输出样例
输入
4
2 3
4 0
0 0
0 0输出
2输入
3
2 3
0 0
0 0输出
3数据范围
1 \le n \le 10^5。
题目分析
这道题是二叉树性质 + 树上递归的经典组合,也是本章「二叉树的重要性质」那几行的直接应用。
先明确满二叉树的判定条件。注意不是「左右儿子都有」,而是:
- 所有叶子在同一深度;
- 非叶子结点都有两个儿子。
这两个条件可以合并成一句:一棵树是满二叉树,当且仅当左右子树都是满二叉树,且左右子树高度相同。这是递归定义的天然形式,也是本题的核心。
于是可以写一个后序 DFS,对每个结点算出:
h[u]:以u为根的子树高度(叶子为 1);full[u]:以u为根的子树是否满。
递推式:
h[u] = 1 + \max(h[l], h[r])
full[u] = \begin{cases}
\text{true} & u \text{ 是叶子} \\
full[l] \land full[r] \land (h[l] = h[r]) & u \text{ 有两个儿子} \\
\text{false} & \text{只有一个儿子}
\end{cases}
最后统计 full[u] 为真的结点个数。
为什么必须「两个条件都判」? 常见的错误写法是只判 h[l] == h[r]。反例:左子树是满的 3 层、右子树是「左偏」的 3 层链(高度也是 3),高度相等但不是满二叉树。高度相等 + 左右都满,才能保证整棵树的叶子在同一层。
为什么用后序(先递归子结点再算自己)? 因为 full[u] 依赖 full[l] 和 full[r],必须等子树算完才能算自己。这是所有「树上统计」类题目的通用顺序。
n 到 10^5:递归深度可能到 10^5(链状树),有爆栈风险。稳妥做法是写非递归版本,或按编号倒序处理(本题父子编号没有保证大小关系,所以更保险的是用显式栈)。本章示例用递归,正式提交时建议改成迭代或扩大栈。
参考代码
验证第一个样例:树是 1(2,3)、2(4,0)、3 和 4 是叶子。满二叉树的子树有:结点 3(单点)、结点 4(单点)——共 2 个。结点 1 的左右高度分别是 2 和 1,不等;结点 2 只有左儿子。答案 2 ✓
练习 2:完全二叉树子树计数
在线评测练习:P1158 完全二叉树
GESP C++ 2026.03 · 六级题 2
题目描述
给定一棵包含 n 个结点的有根二叉树,根结点编号为 1。对于结点 i,其左儿子编号为 l_i、右儿子编号为 r_i(不存在则为 0)。
求所有 n 棵子树中,有多少棵是完全二叉树。
输入格式
第一行一个正整数 n;接下来 n 行,每行两个非负整数 l_i、r_i。
输出格式
输出一行一个整数,表示完全二叉树子树的数量。
输入输出样例
输入
4
2 3
4 0
0 0
0 0输出
4输入
4
2 3
0 0
4 0
0 0输出
3数据范围
1 \le n \le 10^5。
题目分析
完全二叉树的定义是:除最后一层外,其余各层都是满的;最后一层的结点全部靠左连续排列。
它和满二叉树的区别在于最后一层可以不填满,所以「左右子树高度相同」这个条件不再适用(左右高度最多差 1)。练习 1 的递归判定在这里完全失效,必须换方法。
关键技巧:把子树按「完全二叉树的层序编号」重新标号。
完全二叉树有一个漂亮的性质:如果按层序给结点编号(根为 1,结点 i 的左儿子是 2i、右儿子是 2i+1),那么一棵大小为 cnt 的树是完全二叉树,当且仅当它的最大编号恰好等于 cnt。
为什么?因为完全二叉树的编号正好是 1, 2, \ldots, cnt 连续无空洞;一旦有空洞(某个结点只有一个儿子却占了靠右的位置),最大编号就会超过结点总数。
于是对每个结点 u:
- 从
u开始做一次 BFS,按「左儿子2i、右儿子2i+1」的规则给结点编号; - 统计子树结点数
cnt和最大编号maxId; maxId == cnt就是完全二叉树。
但这道题的 n 到 10^5,对每个结点都做一次 BFS 是 O(n^2),会超时。所以还需要优化,两个常用方向:
- 自底向上递推:记录每棵子树的「大小」和「是否完全」,再用「左子树大小 = ?」判断。完全二叉树的左子树要么和右子树一样大(都是满的),要么比右子树多(最后一层左侧多出的部分)。判定条件稍复杂但可以
O(1)转移。 - 只判叶子与已知满树:一棵完全二叉树必然是「一棵满二叉树 + 最后一层若干结点」,可以先求出所有满子树,再往上拼。
本题作为挑战题:上面的「层序编号」判定法是最容易理解、最容易写对的思路,适合先用小数据验证理解;真正拿满分需要把它优化成
O(n)的递推。建议的练习路径:先写出O(n^2)的 BFS 版本,确保样例通过、理解「最大编号 = 结点数」这个判据;再思考如何把「子树大小」和「是否完全」自底向上合并。
参考代码(O(n^2) 判定版,适合理解原理)
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int lc[N], rc[N];
// 判定以 u 为根的子树是否是完全二叉树
bool isComplete(int u) {
queue<pair<int, int> > q; // (结点编号, 层序编号)
q.push(make_pair(u, 1));
int cnt = 0, maxId = 0;
while (!q.empty()) {
pair<int, int> cur = q.front();
q.pop();
int x = cur.first, id = cur.second;
cnt++;
maxId = max(maxId, id);
if (lc[x]) q.push(make_pair(lc[x], 2 * id));
if (rc[x]) q.push(make_pair(rc[x], 2 * id + 1));
}
return maxId == cnt; // 最大编号等于结点数 → 完全
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) cin >> lc[i] >> rc[i];
int ans = 0;
for (int i = 1; i <= n; i++) {
if (isComplete(i)) ans++;
}
cout << ans << endl;
return 0;
}验证样例 2:树是 1(2,3)、3(4,0)。四棵子树分别是:结点 4(单点,完全)、结点 2(单点,完全)、结点 3(有左儿子,完全)、结点 1(左子树是单点、右子树有左儿子,最后一层结点不靠左连续,不完全)。答案 3 ✓
小结
- 树描述层次关系,二叉树是每个节点最多两个孩子的树。
- 二叉树的三条高频性质:第
i层最多2^{i-1}个节点、深度k最多2^k - 1个节点、n_0 = n_2 + 1。 - 完全二叉树适合用数组存储,父子下标关系是
2i、2i+1和\lfloor i/2 \rfloor。 - 前序、中序、后序、层序是四种遍历,前序加中序或后序加中序能还原二叉树。
- 二叉搜索树中序遍历有序,平均查找
O(\log n),但会退化。 - 哈夫曼树让带权路径长度最小,哈夫曼编码是最优前缀码。
- 满二叉树判定:左右子树都满 且高度相同(只判高度相等是错的)。
- 完全二叉树判定:按层序编号(左
2i、右2i+1)后,最大编号等于结点数。 - 树上统计类题目一律用后序(先算子树、再算自己),因为父结点的信息依赖子结点。