# 信息学奥赛（CSP-J）零基础启蒙培训讲义
## 第九天：分叉的艺术与等级森严的阶层（树与二叉树）

* **总时长**：6 小时（上午 3 小时，下午 3 小时）
* **培训目标**：通过生动的生活化比喻，帮助零基础学生彻底理解树与二叉树的概念、完全二叉树的性质、二叉树的三种遍历手算方法（先序、中序、后序），以及哈夫曼树（最优二叉树）与带权路径长度（WPL）的计算。

---

## 📅 上午场：树与二叉树的基本概念及完全二叉树性质（09:00 - 12:00）

### 一、 什么是树？（Tree）

#### 1. 生活中的比喻
* 现实生活中的大树：**根**在下面，**枝叶**往上面分叉。
* **计算机里的树**：刚好反过来！它是一棵**“倒挂的树”**——**根（Root）在最上面**，叶子在最下面。

#### 2. 核心专业术语
* **根节点（Root）**：整棵树最顶端的老大，它没有父节点。比如一棵家族树的始祖。
* **父节点与子节点（Parent & Child）**：上下级关系。比如张三是李四的父亲，李四就是张三的儿子。
* **兄弟节点（Sibling）**：拥有同一个父节点的多个节点互为兄弟。
* **叶子节点（Leaf）**：没有孩子的“光杆司令”（没有子节点的节点）。
* **度（Degree）**：一个节点拥有子节点的个数。比如某节点有 2 个儿子，它的度就是 2。整棵树中最大的度就是这棵树的度。
* **深度 / 高度（Depth / Height）**：树的层数。通常根节点算作第 1 层（或第 0 层，看题目具体定义，默认无说明时根算第 1 层）。

---

### 二、 二叉树（Binary Tree）—— 乖巧的“二胎家庭”

#### 1. 什么是二叉树？
* **定义**：如果一棵树里的所有节点，**每个人最多只能生 2 个孩子**（也就是每个节点的度最大不超过 2），那么这棵树就叫做**二叉树**。
* 这两个孩子分别被称为**左孩子（Left Child）**和**右孩子（Right Child）**。左右顺序绝对不能颠倒！

#### 2. 两种特殊的二叉树
1. **满二叉树（Full Binary Tree）**：
   * 每一层都长得整整齐齐、塞得满满当当，没有任何空缺。
   * 如果一棵满二叉树有 $h$ 层，它总共的节点数是一个固定的公式：
     $$\text{总节点数} = 2^h - 1$$
     *(例如：3层的满二叉树，节点数是 $2^3 - 1 = 7$ 个)*
2. **完全二叉树（Complete Binary Tree）**：
   * 允许最后一层有空缺，但**空缺必须只能靠右边**。
   * 换句话说：所有节点都紧凑地往左边靠，绝对不能出现“左边空着、右边有个孤立节点”的情况。（满二叉树是一种特殊的完全二叉树）。

#### 3. 完全二叉树的黄金性质与数组存储
* **序号对应关系**：如果把一棵完全二叉树从上到下、从左到右依次编上号（从 1 开始）：
  * 如果某个节点编号是 $i$：
    * 它的**左孩子**编号一定是：$2i$
    * 它的**右孩子**编号一定是：$2i + 1$
    * 它的**父节点**编号一定是：$\lfloor i / 2 \rfloor$（向下取整）
* *初赛经典考题*：已知某完全二叉树根在下标 1，问下标 9 的结点的左右孩子和兄弟是谁？
  * 左孩子：$9 \times 2 = 18$
  * 右孩子：$9 \times 2 + 1 = 19$
  * 兄弟：因为 9 是奇数（说明它是右孩子），它的左边兄弟就是 $9 - 1 = 8$。

---
---

## 📅 下午场：二叉树遍历与哈夫曼树（14:00 - 17:00）

### 一、 二叉树的三种遍历（遍历 = 参观全树）

遍历二叉树，就是按照某种规律把树里的所有节点都访问一遍。假设我们把一个节点简称为 **D（Root）**，它的左子树叫 **L（Left）**，右子树叫 **R（Right）**。
因为每次我们先看根，还是先看左、先看右，就诞生了初赛必考的三种遍历方式：

#### 1. 先序遍历（Pre-order Traversal：根 - 左 - 右）
* **口诀**：**先自己，再左边，最后右边**。
* 遇到一个节点：先打印它自己，然后递归遍历它的左子树，最后递归遍历它的右子树。

#### 2. 中序遍历（In-order Traversal：左 - 根 - 右）
* **口诀**：**先左边，再自己，最后右边**。
* 遇到一个节点：先不管它，先去遍历它的左子树；左子树完了，打印它自己；最后去遍历它的右子树。

#### 3. 后序遍历（Post-order Traversal：左 - 右 - 根）
* **口诀**：**先左边，再右边，最后自己**。
* 遇到一个节点：把左右子树都折腾完了，最后才轮到打印它自己。

> **💡 核心秒杀技巧**：
> * 看到**先序遍历**，第一个字母永远是**整棵树的根节点**！
> * 看到**后序遍历**，最后一个字母永远是**整棵树的根节点**！
> * 通过“先序/后序”定位根，再结合“中序”左右切蛋糕，就能轻松还原整棵二叉树。

---

### 二、 哈夫曼树（Huffman Tree，最优二叉树）

#### 1. 什么是哈夫曼树？
* 假设你有几个权值（比如代表字母出现的频率），你想把它们连成一棵二叉树。
* 如果让**频率高（权值大）的离根节点近一点**，**频率低（权值小）的离根节点远一点**，整棵树传输或编码的“代价”就会最小。这种树就叫**哈夫曼树**。

#### 2. 带权路径长度（WPL - Weighted Path Length）
* **路径长度**：从根节点到该节点的边数。
* **WPL**：所有**叶子节点的权值 $\times$ 该节点到根的深度（边数）**的总和。
* **哈夫曼树的构造口诀（贪心思想）**：
  1. 在一堆数字里，挑出**最小的两个**。
  2. 把它们加起来合成一个新的数字。
  3. 重复这个过程，直到合成一个根节点。

---
---

## 📝 随堂与课后实战强化练习卷（学生版）

**班级**：______________  **姓名**：______________  **得分**：______________

### 一、 选择题（共 10 题）

1. 一棵具有 5 层的满二叉树中，结点的总数为（ ）。
   A. 15
   B. 31
   C. 32
   D. 63

2. 如果根结点的深度记为 1，一棵具有 61 个结点的完全二叉树的高度为（ ）。
   A. 5
   B. 6
   C. 7
   D. 8

3. 一棵完全二叉树用数组进行存储与表示，已知根结点存储在数组的第 1 个位置。若存储在数组第 9 个位置的结点存在兄弟结点和两个子结点，则它的兄弟结点和右子结点的位置分别是（ ）。
   A. 8、18
   B. 10、18
   C. 8、19
   D. 10、19

4. 某二叉树的前序遍历序列为 `ABDECFG`，中序遍历序列为 `DEBACFG`。请问这棵树的正确后序遍历结果是什么？（ ）
   A. `EDBGFCA`
   B. `EDGBFCA`
   C. `DEBGFCA`
   D. `DBEGFCA`

5. 设一棵二叉树中有 3 个叶子结点，有 2 个度为 1 的结点，则该二叉树的结点总数是（ ）。
   A. 5
   B. 6
   C. 7
   D. 8

6. 用 5 个权值分别为 `10, 12, 15, 20, 25` 的叶子结点构造一棵哈夫曼树，该树的带权路径长度（WPL）是多少？（ ）
   A. 176
   B. 186
   C. 196
   D. 206

7. 已知一棵二叉树的后序遍历序列是 `CBFEGDA`，前序遍历序列是 `ABCDEFG`，则根结点的左子树的结点个数可能是（ ）。
   A. 2
   B. 3
   C. 4
   D. 5

8. 在下列关于完全二叉树的说法中，正确的是（ ）。
   A. 完全二叉树的子树一定也是完全二叉树
   B. 深度为 $k$ 的完全二叉树，其第 $k$ 层上必然有 $2^{k-1}$ 个结点
   C. 完全二叉树中，若某个结点没有左孩子，则它一定也没有右孩子
   D. 满二叉树不属于完全二叉树

9. 若一棵二叉树的前序遍历结果为根节点，且左子树为空，对于任意节点均满足此条件，则该二叉树的高度为（ ）。
   A. 无法确定
   B. 等于结点数 $n$
   C. 等于 $\log_2 n$
   D. 1

10. 有一个具有 $n$ 个分支结点（度不为 0 的结点）的非空二叉树，它的叶子结点数目（度为 0 的结点）最多为（ ）。
    A. $n$
    B. $n - 1$
    C. $n + 1$
    D. $2n$

---
*(注：教师答案与详细解析页在下方，建议打印前单独切分)*

\newpage

---

## 📖 课后练习卷 —— 标准答案与详细解析

1. **正确答案：B**
   * **详细解析**：
     * 满二叉树结点总数公式为 $2^n - 1$。
     * 当层数 $n = 5$ 时，$2^5 - 1 = 32 - 1 = 31$ 个结点。故选 B。

2. **正确答案：B**
   * **详细解析**：
     * 满二叉树前 5 层共有 $2^5 - 1 = 31$ 个结点。
     * 前 6 层共有 $2^6 - 1 = 63$ 个结点。
     * 题目中结点数为 61，介于 31 和 63 之间，因此这棵完全二叉树的高度为 6 层。故选 B。

3. **正确答案：C**
   * **详细解析**：
     * 在完全二叉树中，若结点编号为 $i$，其左孩子为 $2i$，右孩子为 $2i+1$。
     * 编号为 9 的结点，其左孩子为 $9 \times 2 = 18$，右孩子为 $9 \times 2 + 1 = 19$。
     * 编号 9 是奇数，说明它是双亲的右孩子，它的左边兄弟编号为 $9 - 1 = 8$。
     * 因此兄弟结点和右子结点的位置分别为 8 和 19。故选 C。

4. **正确答案：A**
   * **详细解析**：
     * 前序首位 `A` 为整棵树的根。
     * 在中序 `DEBACFG` 中，`A` 左侧 `DEB` 是左子树，右侧 `CFG` 是右子树。
     * 递归切分还原整棵树后，做后序遍历（左右根），可得正确结果为 `EDBGFCA`。故选 A。

5. **正确答案：C**
   * **详细解析**：
     * 在任意二叉树中，度数与结点数的关系满足：$n_0 = n_2 + 1$（叶子结点数等于度为2的结点数加1）。
     * 已知叶子结点 $n_0 = 3$，则度为 2 的结点 $n_2 = 3 - 1 = 2$。
     * 已知度为 1 的结点 $n_1 = 2$。
     * 结点总数 $N = n_0 + n_1 + n_2 = 3 + 2 + 2 = 7$。故选 C。

6. **正确答案：B**
   * **详细解析**：
     * 用贪心法构造哈夫曼树：
       1. 挑最小的 10 和 12，合并为 22（新集合：15, 20, 25, 22）
       2. 挑最小的 15 和 20，合并为 35（新集合：25, 22, 35）
       3. 挑最小的 22 和 25，合并为 47（新集合：35, 47）
       4. 最后合并 35 和 47，根为 82。
     * 计算 WPL（叶子权值 $\times$ 深度）：
       * 10 和 12 深度为 3：$(10+12) \times 3 = 66$
       * 15、20、25 深度为 2：$(15+20+25) \times 2 = 120$
       * 总 WPL = $66 + 120 = 186$。故选 B。

7. **正确答案：A**
   * **详细解析**：
     * 后序最后一位 `A` 是整棵树的根。结合前序判断，通过左右子树的长度推导，根结点的左子树结点个数为 2。故选 A。

8. **正确答案：C**
   * **详细解析**：
     * **选项 A 错误**：完全二叉树的子树不一定是完全二叉树（比如左子树可能是完全的，但右子树可能是普通树或残缺的）。
     * **选项 B 错误**：完全二叉树的最后一层结点数不一定满，未必有 $2^{k-1}$ 个。
     * **选项 C 正确**：完全二叉树按从上到下、从左到右编号，如果某个结点连左孩子都没有，它往后更不可能有右孩子（否则违反了编号连续和向左靠拢的原则）。故选 C。

9. **正确答案：B**
   * **详细解析**：
     * 前序遍历结果为根且左子树为空，说明该二叉树退化成了一条“单链表”（每个结点都只有右孩子或只有左孩子），此时二叉树的高度等于结点总数 $n$。故选 B。

10. **正确答案：C**
    * **详细解析**：
      * 根据二叉树分支结点与叶子结点的经典关系：在任意非空二叉树中，叶子结点数 $n_0 = n_2 + 1$。
      * 而分支结点（度不为0的结点）包含 $n_1$（度为1的结点）和 $n_2$（度为2的结点），即 $n = n_1 + n_2$。
      * 当 $n_1 = 0$ 时（即二叉树中没有度为 1 的结点，只有度为 2 的结点），$n_2 = n$，此时叶子结点数目最多，为 $n + 1$。故选 C。

信息学奥赛（CSP-J）零基础启蒙培训讲义

第九天：分叉的艺术与等级森严的阶层（树与二叉树）

总时长：6 小时（上午 3 小时，下午 3 小时）
培训目标：通过生动的生活化比喻，帮助零基础学生彻底理解树与二叉树的概念、完全二叉树的性质、二叉树的三种遍历手算方法（先序、中序、后序），以及哈夫曼树（最优二叉树）与带权路径长度（WPL）的计算。

📅 上午场：树与二叉树的基本概念及完全二叉树性质（09:00 - 12:00）

一、什么是树？（Tree）

1. 生活中的比喻

现实生活中的大树：根在下面，枝叶往上面分叉。
计算机里的树：刚好反过来！它是一棵“倒挂的树”——根（Root）在最上面，叶子在最下面。

2. 核心专业术语

根节点（Root）：整棵树最顶端的老大，它没有父节点。比如一棵家族树的始祖。
父节点与子节点（Parent & Child）：上下级关系。比如张三是李四的父亲，李四就是张三的儿子。
兄弟节点（Sibling）：拥有同一个父节点的多个节点互为兄弟。
叶子节点（Leaf）：没有孩子的“光杆司令”（没有子节点的节点）。
度（Degree）：一个节点拥有子节点的个数。比如某节点有 2 个儿子，它的度就是 2。整棵树中最大的度就是这棵树的度。
深度 / 高度（Depth / Height）：树的层数。通常根节点算作第 1 层（或第 0 层，看题目具体定义，默认无说明时根算第 1 层）。

二、二叉树（Binary Tree）—— 乖巧的“二胎家庭”

1. 什么是二叉树？

定义：如果一棵树里的所有节点，每个人最多只能生 2 个孩子（也就是每个节点的度最大不超过 2），那么这棵树就叫做二叉树。
这两个孩子分别被称为左孩子（Left Child）和右孩子（Right Child）。左右顺序绝对不能颠倒！

2. 两种特殊的二叉树

满二叉树（Full Binary Tree）：
每一层都长得整整齐齐、塞得满满当当，没有任何空缺。
如果一棵满二叉树有 $h$ 层，它总共的节点数是一个固定的公式： $$\text{总节点数} = 2^h - 1$$ (例如：3层的满二叉树，节点数是 $2^3 - 1 = 7$ 个)
完全二叉树（Complete Binary Tree）：
允许最后一层有空缺，但空缺必须只能靠右边。
换句话说：所有节点都紧凑地往左边靠，绝对不能出现“左边空着、右边有个孤立节点”的情况。（满二叉树是一种特殊的完全二叉树）。

3. 完全二叉树的黄金性质与数组存储

序号对应关系：如果把一棵完全二叉树从上到下、从左到右依次编上号（从 1 开始）：
如果某个节点编号是 $i$：
- 它的左孩子编号一定是：$2i$
- 它的右孩子编号一定是：$2i + 1$
- 它的父节点编号一定是：$\lfloor i / 2 \rfloor$（向下取整）
初赛经典考题：已知某完全二叉树根在下标 1，问下标 9 的结点的左右孩子和兄弟是谁？
左孩子：$9 \times 2 = 18$
右孩子：$9 \times 2 + 1 = 19$
兄弟：因为 9 是奇数（说明它是右孩子），它的左边兄弟就是 $9 - 1 = 8$。

---

📅 下午场：二叉树遍历与哈夫曼树（14:00 - 17:00）

一、二叉树的三种遍历（遍历 = 参观全树）

遍历二叉树，就是按照某种规律把树里的所有节点都访问一遍。假设我们把一个节点简称为 D（Root），它的左子树叫 L（Left），右子树叫 R（Right）。因为每次我们先看根，还是先看左、先看右，就诞生了初赛必考的三种遍历方式：

1. 先序遍历（Pre-order Traversal：根 - 左 - 右）

口诀：先自己，再左边，最后右边。
遇到一个节点：先打印它自己，然后递归遍历它的左子树，最后递归遍历它的右子树。

2. 中序遍历（In-order Traversal：左 - 根 - 右）

口诀：先左边，再自己，最后右边。
遇到一个节点：先不管它，先去遍历它的左子树；左子树完了，打印它自己；最后去遍历它的右子树。

3. 后序遍历（Post-order Traversal：左 - 右 - 根）

口诀：先左边，再右边，最后自己。
遇到一个节点：把左右子树都折腾完了，最后才轮到打印它自己。

💡 核心秒杀技巧： * 看到先序遍历，第一个字母永远是整棵树的根节点！ * 看到后序遍历，最后一个字母永远是整棵树的根节点！ * 通过“先序/后序”定位根，再结合“中序”左右切蛋糕，就能轻松还原整棵二叉树。

二、哈夫曼树（Huffman Tree，最优二叉树）

1. 什么是哈夫曼树？

假设你有几个权值（比如代表字母出现的频率），你想把它们连成一棵二叉树。
如果让频率高（权值大）的离根节点近一点，频率低（权值小）的离根节点远一点，整棵树传输或编码的“代价”就会最小。这种树就叫哈夫曼树。

2. 带权路径长度（WPL - Weighted Path Length）

路径长度：从根节点到该节点的边数。
WPL：所有叶子节点的权值 $\times$ 该节点到根的深度（边数）的总和。
哈夫曼树的构造口诀（贪心思想）：
在一堆数字里，挑出最小的两个。
把它们加起来合成一个新的数字。
重复这个过程，直到合成一个根节点。

---

📝 随堂与课后实战强化练习卷（学生版）

班级：__ 姓名：__ 得分：__

一、选择题（共 10 题）

一棵具有 5 层的满二叉树中，结点的总数为（）。 A. 15 B. 31 C. 32 D. 63
如果根结点的深度记为 1，一棵具有 61 个结点的完全二叉树的高度为（）。 A. 5 B. 6 C. 7 D. 8
一棵完全二叉树用数组进行存储与表示，已知根结点存储在数组的第 1 个位置。若存储在数组第 9 个位置的结点存在兄弟结点和两个子结点，则它的兄弟结点和右子结点的位置分别是（）。 A. 8、18 B. 10、18 C. 8、19 D. 10、19
某二叉树的前序遍历序列为 ABDECFG，中序遍历序列为 DEBACFG。请问这棵树的正确后序遍历结果是什么？（） A. EDBGFCA B. EDGBFCA C. DEBGFCA D. DBEGFCA
设一棵二叉树中有 3 个叶子结点，有 2 个度为 1 的结点，则该二叉树的结点总数是（）。 A. 5 B. 6 C. 7 D. 8
用 5 个权值分别为 10, 12, 15, 20, 25 的叶子结点构造一棵哈夫曼树，该树的带权路径长度（WPL）是多少？（） A. 176 B. 186 C. 196 D. 206
已知一棵二叉树的后序遍历序列是 CBFEGDA，前序遍历序列是 ABCDEFG，则根结点的左子树的结点个数可能是（）。 A. 2 B. 3 C. 4 D. 5
在下列关于完全二叉树的说法中，正确的是（）。 A. 完全二叉树的子树一定也是完全二叉树 B. 深度为 $k$ 的完全二叉树，其第 $k$ 层上必然有 $2^{k-1}$ 个结点 C. 完全二叉树中，若某个结点没有左孩子，则它一定也没有右孩子 D. 满二叉树不属于完全二叉树
若一棵二叉树的前序遍历结果为根节点，且左子树为空，对于任意节点均满足此条件，则该二叉树的高度为（）。 A. 无法确定 B. 等于结点数 $n$ C. 等于 $\log_2 n$ D. 1
有一个具有 $n$ 个分支结点（度不为 0 的结点）的非空二叉树，它的叶子结点数目（度为 0 的结点）最多为（）。 A. $n$ B. $n - 1$ C. $n + 1$ D. $2n$

(注：教师答案与详细解析页在下方，建议打印前单独切分)

\newpage

📖 课后练习卷 —— 标准答案与详细解析

正确答案：B
详细解析：
- 满二叉树结点总数公式为 $2^n - 1$。
- 当层数 $n = 5$ 时，$2^5 - 1 = 32 - 1 = 31$ 个结点。故选 B。
正确答案：B
详细解析：
- 满二叉树前 5 层共有 $2^5 - 1 = 31$ 个结点。
- 前 6 层共有 $2^6 - 1 = 63$ 个结点。
- 题目中结点数为 61，介于 31 和 63 之间，因此这棵完全二叉树的高度为 6 层。故选 B。
正确答案：C
详细解析：
- 在完全二叉树中，若结点编号为 $i$，其左孩子为 $2i$，右孩子为 $2i+1$。
- 编号为 9 的结点，其左孩子为 $9 \times 2 = 18$，右孩子为 $9 \times 2 + 1 = 19$。
- 编号 9 是奇数，说明它是双亲的右孩子，它的左边兄弟编号为 $9 - 1 = 8$。
- 因此兄弟结点和右子结点的位置分别为 8 和 19。故选 C。
正确答案：A
详细解析：
- 前序首位 A 为整棵树的根。
- 在中序 DEBACFG 中，A 左侧 DEB 是左子树，右侧 CFG 是右子树。
- 递归切分还原整棵树后，做后序遍历（左右根），可得正确结果为 EDBGFCA。故选 A。
正确答案：C
详细解析：
- 在任意二叉树中，度数与结点数的关系满足：$n_0 = n_2 + 1$（叶子结点数等于度为2的结点数加1）。
- 已知叶子结点 $n_0 = 3$，则度为 2 的结点 $n_2 = 3 - 1 = 2$。
- 已知度为 1 的结点 $n_1 = 2$。
- 结点总数 $N = n_0 + n_1 + n_2 = 3 + 2 + 2 = 7$。故选 C。
正确答案：B
详细解析：
- 用贪心法构造哈夫曼树：
- 挑最小的 10 和 12，合并为 22（新集合：15, 20, 25, 22）
- 挑最小的 15 和 20，合并为 35（新集合：25, 22, 35）
- 挑最小的 22 和 25，合并为 47（新集合：35, 47）
- 最后合并 35 和 47，根为 82。
- 计算 WPL（叶子权值 $\times$ 深度）：
- 10 和 12 深度为 3：$(10+12) \times 3 = 66$
- 15、20、25 深度为 2：$(15+20+25) \times 2 = 120$
- 总 WPL = $66 + 120 = 186$。故选 B。
正确答案：A
详细解析：
- 后序最后一位 A 是整棵树的根。结合前序判断，通过左右子树的长度推导，根结点的左子树结点个数为 2。故选 A。
正确答案：C
详细解析：
- 选项 A 错误：完全二叉树的子树不一定是完全二叉树（比如左子树可能是完全的，但右子树可能是普通树或残缺的）。
- 选项 B 错误：完全二叉树的最后一层结点数不一定满，未必有 $2^{k-1}$ 个。
- 选项 C 正确：完全二叉树按从上到下、从左到右编号，如果某个结点连左孩子都没有，它往后更不可能有右孩子（否则违反了编号连续和向左靠拢的原则）。故选 C。
正确答案：B
详细解析：
- 前序遍历结果为根且左子树为空，说明该二叉树退化成了一条“单链表”（每个结点都只有右孩子或只有左孩子），此时二叉树的高度等于结点总数 $n$。故选 B。
正确答案：C
- 详细解析：
- 根据二叉树分支结点与叶子结点的经典关系：在任意非空二叉树中，叶子结点数 $n_0 = n_2 + 1$。
- 而分支结点（度不为0的结点）包含 $n_1$（度为1的结点）和 $n_2$（度为2的结点），即 $n = n_1 + n_2$。
- 当 $n_1 = 0$ 时（即二叉树中没有度为 1 的结点，只有度为 2 的结点），$n_2 = n$，此时叶子结点数目最多，为 $n + 1$。故选 C。

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com

第九天：分叉的艺术与等级森严的阶层（树与二叉树）

信息学奥赛（CSP-J）零基础启蒙培训讲义

第九天：分叉的艺术与等级森严的阶层（树与二叉树）

📅 上午场：树与二叉树的基本概念及完全二叉树性质（09:00 - 12:00）

一、 什么是树？（Tree）

1. 生活中的比喻

2. 核心专业术语

二、 二叉树（Binary Tree）—— 乖巧的“二胎家庭”

1. 什么是二叉树？

2. 两种特殊的二叉树

3. 完全二叉树的黄金性质与数组存储

---

📅 下午场：二叉树遍历与哈夫曼树（14:00 - 17:00）

一、 二叉树的三种遍历（遍历 = 参观全树）

1. 先序遍历（Pre-order Traversal：根 - 左 - 右）

2. 中序遍历（In-order Traversal：左 - 根 - 右）

3. 后序遍历（Post-order Traversal：左 - 右 - 根）

二、 哈夫曼树（Huffman Tree，最优二叉树）

1. 什么是哈夫曼树？

2. 带权路径长度（WPL - Weighted Path Length）

---

📝 随堂与课后实战强化练习卷（学生版）

一、 选择题（共 10 题）

📖 课后练习卷 —— 标准答案与详细解析

一、什么是树？（Tree）

二、二叉树（Binary Tree）—— 乖巧的“二胎家庭”

一、二叉树的三种遍历（遍历 = 参观全树）

二、哈夫曼树（Huffman Tree，最优二叉树）

一、选择题（共 10 题）