Skip to content

树与二叉树

树的基本概念、二叉树的存储与遍历、二叉搜索树与哈夫曼树。

Updated View as Markdown

前面学的数组、链表、栈、队列都是线性结构,元素一个接一个排成一条线。但很多关系不是线性的:家谱、文件夹、组织架构,都是层层嵌套的。描述这种层次关系,要用树。

本章的知识点与 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. 把新树放回集合。

重复到只剩一棵树。用优先队列(小根堆)可以高效实现。

例:权值 1、2、3、4。

  1. 取 1、2 合并成 3,集合变成 {3, 3, 4}。
  2. 取 3、3 合并成 6,集合变成 {4, 6}。
  3. 取 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。

题目分析

这道题是二叉树性质 + 树上递归的经典组合,也是本章「二叉树的重要性质」那几行的直接应用。

先明确满二叉树的判定条件。注意不是「左右儿子都有」,而是:

  1. 所有叶子在同一深度;
  2. 非叶子结点都有两个儿子。

这两个条件可以合并成一句:一棵树是满二叉树,当且仅当左右子树都是满二叉树,且左右子树高度相同。这是递归定义的天然形式,也是本题的核心。

于是可以写一个后序 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:

  1. 从 u 开始做一次 BFS,按「左儿子 2i、右儿子 2i+1」的规则给结点编号;
  2. 统计子树结点数 cnt 和最大编号 maxId;
  3. 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)后,最大编号等于结点数。
  • 树上统计类题目一律用后序(先算子树、再算自己),因为父结点的信息依赖子结点。
Navigation

Type to search…

↑↓ navigate↵ selectEsc close