树和二叉树 ⭐
🎯 一句话秒杀：树是一对多的层次结构，二叉树是最常用的树（每个结点最多俩孩子）。遍历二叉树就是按特定顺序访问每个结点一次。
一、树的基本概念
树的定义
树 = n(n≥0)个结点的有限集合。n=0时为空树。 有且只有一个根结点，其余结点分成m个互不相交的子树。
树的基本术语
| 术语 | 定义 |
|---|---|
| 根 | 唯一没有前驱的结点 |
| 叶子 | 没有孩子的结点（度为0） |
| 结点度 | 结点拥有的子树个数 |
| 树的度 | 所有结点度的最大值 |
| 深度/高度 | 从根到叶子最大层数（根为第1层） |
| 森林 | m棵互不相交的树的集合 |
二、二叉树
二叉树的定义与性质
二叉树每个结点最多有2棵子树（左子树和右子树），分左右，顺序不能颠倒
重要性质（必背！）：
- 第 i 层最多有 2^(i-1) 个结点（i≥1）
- 深度为 k 的二叉树最多有 2^k - 1 个结点
- 叶子结点数 n₀ = 度为2的结点数 n₂ + 1
- n个结点的二叉树深度至少为 ⌊log₂n⌋ + 1
特殊二叉树
| 类型 | 定义 | 特点 |
|---|---|---|
| 满二叉树 | 每一层都满 | 结点总数 = 2^k - 1 |
| 完全二叉树 | 只有最后一层不满，且从左向右连续 | 可用顺序存储 |
| 二叉排序树 | 左<根<右 | 中序是递增序列 |
| 平衡二叉树 | 左右子树高度差≤1 | 查找效率 O(log n) |
🔑 秒杀秘籍
性质3 叶子数公式：
叶子 = 度为2的结点 + 1（n₀ = n₂ + 1） 考试必考：已知二叉树度2结点有5个，叶子有___个？ → 6个
三、二叉树的存储
顺序存储（数组）
c
// 完全二叉树用数组存
// 根下标1，左孩子2i，右孩子2i+1
int tree[MAXSIZE];
// tree[1] = 根, tree[2] = 左孩子, tree[3] = 右孩子...
链式存储（最常用）
c
typedef struct BiTNode {
int data; // 数据域
struct BiTNode *lchild; // 左孩子指针
struct BiTNode *rchild; // 右孩子指针
} BiTNode, *BiTree; A
/ \
B C
/ \ / \
D E F G
链式存储结构：
A(•, •)
/ \
B(•, •) C(•, •)
/ \ / \
D(•,•) E(•,•) F(•,•) G(•,•)四、二叉树的遍历（绝对重点！）
三种遍历方式
c
// 先序遍历：根 → 左 → 右
void PreOrder(BiTree T) {
if (T == NULL) return;
printf("%d ", T->data); // 访问根
PreOrder(T->lchild); // 遍历左子树
PreOrder(T->rchild); // 遍历右子树
}
// 中序遍历：左 → 根 → 右
void InOrder(BiTree T) {
if (T == NULL) return;
InOrder(T->lchild);
printf("%d ", T->data);
InOrder(T->rchild);
}
// 后序遍历：左 → 右 → 根
void PostOrder(BiTree T) {
if (T == NULL) return;
PostOrder(T->lchild);
PostOrder(T->rchild);
printf("%d ", T->data);
}遍历结果示例
A
/ \
B C
/ \ / \
D E F G
先序：A B D E C F G (根左右)
中序：D B E A F C G (左根右)
后序：D E B F G C A (左右根)
📌 图里圆圈内的数字是访问顺序：先序先访问根（A=1），中序先访问最左（D=1），后序最后访问根（A=7）。背口诀：先序"根左右"、中序"左根右"、后序"左右根"，配合上图理解递归遍历的推进方向。
🚨 红牌警告
已知中序+先序/后序 → 可唯一确定一棵二叉树只知道先序+后序 → 不能唯一确定！ 考试必考：给你先序和中序，画出二叉树
五、线索二叉树
利用空指针域指向遍历序列的前驱/后继
- 如果结点无左孩子 → lchild指向前驱
- 如果结点无右孩子 → rchild指向后继
六、树的存储结构
| 表示法 | 说明 |
|---|---|
| 双亲表示法 | 每个结点存parent下标 |
| 孩子表示法 | 每个结点存孩子链表 |
| 孩子兄弟表示法 | left=第一个孩子，right=下一个兄弟 |
孩子兄弟表示法可以将任意树转为二叉树！
七、哈夫曼树（最优二叉树）
定义
带权路径长度（WPL）最小的二叉树 WPL = ∑(叶子权重 × 路径长度)
构造哈夫曼树
- 所有结点看成独立的树（森林）
- 选两个权值最小的合并
- 新结点权值 = 两子权值和
- 重复2-3直到只剩一棵树
示例：权值 {2, 3, 5, 7}
合并2+3=5 → {5, 5, 7}
合并5+5=10 → {10, 7}
合并10+7=17 → {17}
哈夫曼编码
- 左分支标0，右分支标1
- 从根到叶子路径上的0/1序列就是字符编码
- 前缀编码：任何字符的编码都不是另一个的前缀
🔑 秒杀秘籍
哈夫曼树的特点：
- 权值越大的叶子离根越近
- 没有度为1的结点
- n个叶子 → 总结点数 = 2n - 1
📝 闭卷真题挑战
（点击下方空白查看答案）
1. 二叉树第i层最多有几个结点？
2. 深度为5的二叉树最多有几个结点？
3. 某二叉树有5个度为2的结点，叶子有几个？
4. 先序ABDCE，中序BDAEC，画出二叉树。
5. 哈夫曼树中n个叶子，总共有几个结点？👆 点击展开答案
- **2^(i-1)**个
- 2^5-1 = 31个
- n₀ = n₂ + 1 = 6个
A
/ \
B C
/ /
D E思路：先序第一个A是根，中序A左边是左子树(B D)，右边是右子树(E C)...
- 2n - 1个（哈夫曼树没有度为1的结点）
📖 教材习题对照
| 教材习题 | 知识点 | 难度 |
|---|---|---|
| 习题6.1~6.3 | 二叉树性质 | ⭐⭐ |
| 习题6.4~6.7 | 二叉树遍历 | ⭐⭐⭐ |
| 习题6.8~6.10 | 树与二叉树的转换 | ⭐⭐⭐ |
| 习题6.11~6.13 | 哈夫曼树与哈夫曼编码 | ⭐⭐⭐⭐ |
对应教材：严蔚敏《数据结构》C语言版 第2版 → 第6章 树和二叉树 对应考试大纲：考点16 — 树和二叉树 ⭐
📺 配套视频
复习到本考点 → 先看视频补讲，再刷上面「闭卷挑战」。