13.3.1 树知识点概述
树是软件设计师考试的数据结构重难点，几乎每次都会考到其中一两个知识点。它与线性结构不同：线性结构是一对一，树是层次化的一对多关系，并且没有回路。
树这一章考什么
| 内容 | 课堂定位 | 考试表现 |
|---|---|---|
| 树与二叉树基本概念 | 先建立术语体系 | 根、父子、兄弟、叶子、度、层次 |
| 二叉树性质 | 高频计算点 | 节点数、层数、度为 0/1/2 的关系 |
| 二叉树遍历 | 树操作核心 | 先序、中序、后序、层序 |
| 二叉排序树 | 查找结构 | 插入、查找、中序有序 |
| 最优二叉树 | 哈夫曼树 | 带权路径长度、构造过程、编码 |
| 其他特殊二叉树 | 概念辨析 | 满二叉树、完全二叉树、平衡思想等 |
树的基本语言
树的术语有相对性。同一个节点可以是某个节点的孩子，也可以是另一些节点的父节点。
| 术语 | 含义 |
|---|---|
| 根节点 | 没有父节点的节点 |
| 父节点/孩子节点 | 直接上下层关系 |
| 兄弟节点 | 拥有同一个父节点的节点 |
| 叶子节点 | 度为 0，没有孩子 |
| 分支节点 | 度不为 0，有孩子 |
| 节点的度 | 节点拥有的子树个数 |
| 树的度 | 整棵树中最大的节点度 |
| 层次 | 根为第 1 层，向下逐层加 1 |
| 高度/深度 | 树的最大层次数 |
普通树与二叉树
二叉树不是“度为 2 的树”的简单同义词。二叉树强调每个节点最多有两个孩子，并且左、右孩子有顺序。
| 比较项 | 普通树 | 二叉树 |
|---|---|---|
| 子节点数量 | 可多个，由树的度决定 | 最多 2 个 |
| 子节点顺序 | 通常不强调左右 | 左子树、右子树不能交换 |
| 空子树 | 一般不单独讨论 | 左空、右空会影响结构 |
| 遍历规则 | 可转化后处理 | 先序、中序、后序都依赖左右 |
树可以转换成二叉树
课程提到“左孩子右兄弟”法：普通树中，每个节点的第一个孩子放到左孩子位置，兄弟节点依次连到右孩子位置。考试近年很少直接考转换过程，但理解它有助于明白二叉树为什么能表达更一般的层次结构。
mermaid
flowchart LR
T["普通树"] --> L["第一个孩子 -> 左孩子"]
L --> R["兄弟节点 -> 右孩子"]
R --> B["转换为二叉树"]学树时的基本方法
树题不要只背公式。课程强调，很多性质可以拿满二叉树或小规模例子验证：
- 遇到“最多”时，画满二叉树。
- 遇到“最少”时，画单支树。
- 遇到编号关系时，画完全二叉树从上到下、从左到右编号。
- 遇到遍历时，把整棵树拆成“根、左子树、右子树”。
本节例题
关于树与二叉树，下列说法正确的是：
自查清单
- 能否区分节点的度和树的度？
- 能否说明为什么二叉树强调左、右子树？
- 能否解释普通树转换为二叉树的“左孩子右兄弟”思想？