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

> Documentation Index
> Fetch the complete documentation index at: https://cppguide.xyz/llms.txt
> Use this file to discover all available pages before exploring further.

# 树与二叉树

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

本章的知识点与 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$ |

这种存法只适合完全二叉树。如果树很稀疏（比如一条链），数组里会大片空着，浪费空间。

### 链式存储

一般二叉树用链式存储，每个节点存数据和左右孩子指针。

```cpp
struct Node {
    char data;
    Node *left;
    Node *right;
    Node(char c) : data(c), left(NULL), right(NULL) {}
};

## 二叉树的遍历

遍历就是按某种顺序访问每个节点一次。四种方式：

| 遍历 | 顺序 | 名字的由来 |
| --- | --- | --- |
| 前序 | 根 → 左 → 右 | 根最先访问 |
| 中序 | 左 → 根 → 右 | 根在中间访问 |
| 后序 | 左 → 右 → 根 | 根最后访问 |
| 层序 | 一层一层从左到右 | 按层访问 |

前三种用递归写最自然。

```cpp
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 << " ";
}

层序要用队列。

```cpp
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)$。

```cpp
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 满二叉树](https://dailyup.run/tasks/269)

> 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$（链状树），有爆栈风险。稳妥做法是写非递归版本，或按编号倒序处理（本题父子编号没有保证大小关系，所以更保险的是用显式栈）。本章示例用递归，**正式提交时建议改成迭代或扩大栈**。

#### 参考代码

> 🔒 参考代码已隐藏。请在网页版输入解锁密码查看：https://cppguide.xyz/ds/tree/index.md

验证第一个样例：树是 `1(2,3)`、`2(4,0)`、3 和 4 是叶子。满二叉树的子树有：结点 3（单点）、结点 4（单点）——共 2 个。结点 1 的左右高度分别是 2 和 1，不等；结点 2 只有左儿子。答案 2 ✓

### 练习 2：完全二叉树子树计数

在线评测练习：[P1158 完全二叉树](https://dailyup.run/tasks/242)

> 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)$ 判定版，适合理解原理）

```cpp
#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$）后，**最大编号等于结点数**。
- 树上统计类题目一律用**后序**（先算子树、再算自己），因为父结点的信息依赖子结点。

Source: https://cppguide.xyz/ds/tree/index.mdx
