本讲定位：六级的主干。官方六级大纲六个知识块里，树独占一块，且第 2 块（哈夫曼/格雷编码）、第 3 块（搜索算法）全部建立在树上。三套新大纲真题里，单选第 6、7、8 题连续三道考二叉树，判断题再出 2～3 题；编程题第 2 题连续三次都是”给一棵二叉树，统计满足条件的子树个数”。
本讲只解决一件事：把一棵树在纸上和在代码里都表示清楚，并且能沿着四种顺序走一遍。 会了这个，后面的 DFS、BFS、哈夫曼全是它的应用。
对应官方大纲：六级知识块 1「树」——树的基本概念；知识块 3「搜索算法」——二叉树的搜索算法。
前置知识：六级第 01 讲（栈与队列）、五级第 06 讲（递归）。
代码说明：本讲代码均已用 g++ 11.5（
-std=c++11）编译运行验证，所有标注的输出均为本机实测；「两序推第三序」的算法已用随机树对拍 1000 组。
树是一种一对多的层次结构：一个根，往下分叉，永不回头相交。
A ← 根结点（root），深度 1
┌──┴──┐
B C ← A 的孩子；B、C 互为兄弟
┌──┴──┐ │
D E F ← D、E 是 B 的孩子，B 是它们的父结点
│
G ← 叶子结点，深度 4
| 术语 | 含义 | 上图的例子 |
|---|---|---|
| 根结点 | 唯一没有父结点的结点 | A |
| 叶子结点 | 没有孩子的结点 | D、E、G |
| 父 / 孩子 | 直接相连的上下两层 | B 是 D 的父，D 是 B 的孩子 |
| 兄弟 | 同一个父结点的孩子 | D 和 E |
| 结点的度 | 该结点孩子的个数 | A 的度是 2，B 的度是 2，G 的度是 0 |
| 树的度 | 所有结点度的最大值 | 2 |
| 深度 / 层数 | 从根往下数，根为第 1 层 | G 在第 4 层 |
| 树的高度（深度） | 最深结点的层数 | 4 |
| 子树 | 任一结点连同它所有后代 | 以 B 为根的子树含 B、D、E |
⚠️ 三个最容易混的点：
- 「度」是孩子个数，不是边数的一半，也和图论里的「度」不同（图里要算父边）。
- 根结点的深度是 1 还是 0？ GESP 真题的口径是根为第 1 层（2025 年 12 月六级判断第 10 题明确写「假定只有一个根节点的树的深度为 1」）。但数组存储时下标从 0 开始——两者不矛盾，看题目怎么定义。
- 每个结点都是一棵子树的根。$n$ 个结点的树，恰好有 $n$ 棵子树。这句话是编程题第 2 题的题眼（「所有 $n$ 棵子树中有多少棵是满二叉树」）。
$$ \boxed{\text{树中：结点数} = \text{边数} + 1} $$
因为除根以外，每个结点头顶恰好有一条边连向父亲。上图 7 个结点、6 条边。✅
二叉树：每个结点最多两个孩子，且严格区分左右。
$$ \boxed{\text{左右是有区别的：只有左孩子 } \ne \text{ 只有右孩子}} $$
1 1
/ \
2 2
这是两棵不同的二叉树
📌 这就是二叉树和「度为 2 的树」的区别：后者不分左右。考试爱在这里设判断题。
方式一：指针（链式） ——通用，任何二叉树都能存。
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};