6.1 树的定义
树（Tree）是n(n大于等于0)个结点的有限集T，若n=0，称为空树；
若n>0，则它满足如下两个条件：
有且仅有一个特定的称为根(Root）的结点；
其余结点可分为m(m>=0)个互不相交的有限集T1, T2, T3…Tm, 其中每个集合本身又是一棵树，并称为根的子树(SubTree)。
基本术语：
- 结点(node): 包括一个数据元素及若干指向其子树的分支
- 结点的度(degree)：结点拥有的子树个数
- 叶子(leaf)：度为0的结点（或称终端结点）
- 分支结点（非终端结点）：度不为0的结点
- 树的度：树内各结点的度的最大值
- 孩子(child)：结点的子树的根称为该结点的孩子
- 结点 B、C、D 是结点 A 的孩子；
- 结点 E、F 是结点 B 的孩子；
- 双亲(parents): (相对孩子)结点的上层结点
- 结点 A 是结点 B、C、D 的双亲；
- 结点 B 是结点 E、F 的双亲；
- 兄弟(sibling)：同一双亲的孩子之间互称兄弟
- 结点的祖先：从根到该结点所经分支上的所有结点
- 子孙：某结点为根的子树中的任意结点
- 结点的层次(level)：从根结点算起，根为第一层，它的孩子为第二层……
- 深度(depth)：树中结点的最大层次数
- 森林(forest)：m(m0)棵互不相交的树的集合
6.2 二叉树
二叉树：是n个结点的有限集，它或为空树(n=0)，或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成
特点：
- 每个结点至多有二棵子树(即不存在度大于2的结点)
- 二叉树的子树有左、右之分，且其次序不能任意颠倒
5种基本形态：
二叉树的性质
两种特殊形式的二叉树：完全二叉树和满二叉树
满二叉树
定义：一棵深度为k且有2k-1个结点的二叉树称为满二叉树
特点：每一层上的结点数都是最大结点数
完全二叉树
定义：深度为k，有n个结点的二叉树当且仅当其每一个结 点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称为完全二叉树
特点：叶子结点只可能在层次最大的两层上出现；对任一结点，若其右分支下子孙的最大层次为l，则其左分支下子孙的最大层次必为l 或 l+1
二叉树的存储结构
顺序存储结构
结点间关系蕴含在其存储位置中。
浪费空间，适于存满二叉树和完全二叉树
链式存储结构
二叉树的结点由一个数据元素和分别指向其左右子树的两个分支构成，这二叉树链表中的结点至少包含3个域：数据域和左右指针域。有时为了便于找到双亲，则可以在结点结构中增加一个指向其双亲结点的指针域，利用这两种结点结构所得的二叉树的存储结构分被称为二叉链表和三叉链表
遍历二叉树 Traversing Binary Tree
定义: 按某条搜索路径巡访树的每个结点，且使每个顶点仅被访问一次
输出：得到树中所有结点的一个线性排列
实现方法：
若限定先左后右则只剩下3种方案：
- 先序遍历：先看当前根节点，再把左子树整个逛完，最后逛右子树
- 中序遍历：先把左子树整个逛完，再看当前根节点，最后逛右子树。
- 后序遍历：先把左子树整个逛完，再把右子树整个逛完，最后看当前根节点。
无论先后，一定要逛完子树
如果只输入 “有值的结点”，会搞不清 “哪些位置是空的”—— 比如同样的先序序列ABCDEGF，能对应不同的二叉树（就像图里右边那两棵树，结构不一样，但先序序列可能相同）。为了让输入唯一对应一棵二叉树，必须在输入时用 “空字符”（比如图里的 “Ø”）表示 “这个位置没有结点”
树与森林
树的存储结构
“树的双亲表示法”
结构数组存放树的结点，每个结点含两个域：
数据域：存放结点本身信息
双亲域：指示本结点的双亲结点在数组中位置
- 数组第 0 位是 A：A 是根节点（没有爸爸），所以 parent 写
-1（表示无父）； - 数组第 1 位是 B：B 的爸爸是 A（A 在 0 位），所以 parent 写
0； - 数组第 2 位是 C：C 的爸爸是 A（A 在 0 位），所以 parent 写
0； - 数组第 3 位是 D：D 的爸爸是 B（B 在 1 位），所以 parent 写
1；
特点：“找爸爸容易，找孩子难”
- 找爸爸（双亲）很方便：比如想知道 G 的爸爸是谁，看 G 在数组第 6 位，parent 是 4 → 数组第 4 位是 E，所以 G 的爸爸是 E；
- 找孩子很难：比如想知道 B 有哪些孩子，得把整个数组扫一遍，看谁的 parent 是 1（B 的下标）→ 扫出来 D（3 位）、E（4 位），所以 B 的孩子是 D、E。
// 1. 定义树的最大节点数（最多存100个节点）
#define MAX_TREE_SIZE 100
// 2. 定义“单个节点的结构”（对应之前的“家庭关系卡”）
typedef struct PTNode {
TElemType data; // 数据域：存节点自己的信息（比如A、B）
int parent; // 双亲域：存“爸爸在数组中的下标”（根节点的parent是-1）
} PTNode;
// 3. 定义“整个树的结构”（用数组存所有节点）
typedef struct {
PTNode nodes[MAX_TREE_SIZE]; // 存所有节点的数组
int r; // 根节点在数组中的下标（比如根是A，r就是0）
int n; // 树的总节点数
} PTree;
// 4. 函数：找节点t[i]的“第一个孩子”（长子）
Int FirstChild (PTree t, int i)
{
// 遍历数组中i之后的节点（从i+1开始，因为节点一般按层次/顺序存）
for (j = i+1; j < t.n; j++) {
// 如果某个节点的parent是i → 这个节点是t[i]的孩子
if (t.nodes[j].parent == i)
return (j); // 返回第一个找到的孩子的下标
}
return (-1); // 没找到孩子，返回-1
}孩子表示法（多重链表）
它分两种形式：
1. 节点同构（所有家长的通讯录页数一样）
- 规则：不管一个节点有多少个孩子，都给它固定数量的 “孩子指针”（数量等于树的最大孩子数，叫 “树的度 d”）。
- 比如树里最多的节点有 3 个孩子，那所有节点都给 3 个指针位。
- 缺点：浪费空间—— 比如某个节点只有 1 个孩子，剩下 2 个指针位就空着没用。
2. 节点不同构（家长的通讯录页数按需给）
- 规则：每个节点先记 “自己有几个孩子（degree）”，再给对应数量的 “孩子指针”。
- 比如节点 A 有 2 个孩子，就给 2 个指针位；节点 B 有 3 个孩子，就给 3 个指针位。
- 缺点：操作麻烦—— 每个节点的结构不一样，存、取的时候得先看 “degree”，再处理指针。
在基础版的数组条目里，加一个parent域（记爸爸在数组中的下标）。
// 1. 定义【孩子链表的单个节点】（存某个孩子在数组中的下标，以及下一个孩子的地址）
typedef struct CTNode {
int child; // 存“孩子节点在数组中的下标”（比如A的孩子B在数组第1位，这里就存1）
struct CTNode *next; // 指向下一个孩子的指针（链表的下一个节点）
} *ChildPtr; // ChildPtr是这个结构的指针类型
// 2. 定义【数组中的单个节点】（存自己的信息+第一个孩子的链表入口）
typedef struct {
TElemType data; // 存节点自己的信息（比如A、B）
ChildPtr firstchild; // 指向第一个孩子的链表指针（比如A的firstchild指向B对应的链表节点）
} CTBox;
// 3. 定义【整个树的结构】（用数组存所有节点，记录总节点数和根的位置）
typedef struct {
CTBox nodes[MAX_TREE_SIZE]; // 存所有节点的数组（每个元素是CTBox类型）
int n, r; // n：树的总节点数；r：根节点在数组中的下标（比如根A在数组第0位，r就是0）
} CTree; 孩子兄弟表示法
“二叉链表” ，存储结构： 链表（链式存储） ，逻辑结构，二叉树，命名为list容易造成困惑
| 存储方式 | 核心特点 | 优点 | 缺点 |
|---|---|---|---|
| 双亲表示法 | 每个节点记 “爸爸的位置” | 找爸爸方便 | 找孩子要遍历全树 |
| 孩子链表法 | 每个节点用 “链表记所有孩子” | 找孩子方便 | 找爸爸要遍历全树（改进版加 parent 后才方便） |
| 孩子兄弟表示法 | 每个节点记 “第一个孩子 + 下一个兄弟” | 用二叉链表就能存任意树，结构统一（所有节点都是 2 个指针） | 找爸爸需要额外遍历（得从根开始找） |
森林与二叉树的转换
树用二叉树存储
树的结构需要 “压缩” 成二叉树的双指针
树的每个节点可以有多个孩子（比如 A 有 3 个孩子 B、C、E），但二叉链表每个节点只有 2 个指针 —— 如果直接存 “所有孩子”，指针数量不够
所以我们想了个办法：用 1 个指针存 “第一个孩子”，另 1 个指针存 “下一个兄弟”，把 “多孩子” 的关系拆成 “孩子 + 兄弟” 的链式结构，刚好能塞进二叉链表的 2 个指针里：
- 左指针→第一个孩子：负责 “向下” 的父子关系；
- 右指针→下一个兄弟：负责 “横向” 的兄弟关系。
二叉树和树，都能用 “二叉链表”（每个节点有 2 个指针）来存。从物理存储上看，它们用的是同一个二叉链表结构，但对指针的 “解释逻辑” 不一样
从树与二叉树的转换可知：任何一棵和树对应的二叉树，其右子树必为空
这个 “右子树为空” 是指 “根节点的右子树为空”，不是说整个二叉树所有节点都没有右子树
将n个二叉树连接为森林
- 将各棵树分别转换成二叉树
- 将每棵树的根结点用线相连
- 以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树型结构
看出森林由哪些二叉树构成
给定一个森林可以唯一确定由哪些树构成
若把森林中第二棵树的根结点看成是第一棵树根结点的兄弟，则可导出森林和二叉树的对应关系
森林转换成二叉树
具体来说，每棵树对应 “当前节点 + 它的左子树”，而 “当前节点的右子树” 是下一棵树的起始（因为由上森林的树是普通树，只是转成二叉树存储森林的树互为兄弟，对应二叉树的右分支）：
- 第 1 棵树 = 二叉树的根节点 + 根的左子树（因为树转二叉树后根的右子树为空，这里的右子树是下一棵树）；
- 第 2 棵树 = 第 1 棵树根的右子树的根节点 + 这个根的左子树；
- 第 3 棵树 = 第 2 棵树根的右子树的根节点 + 这个根的左子树；… 以此类推，直到右子树为空。
画图直观理解
树和森林的遍历
树的遍历（其实和二叉树一样）
先根（序）遍历，若T非空，则：
1、访问根结点R
2、依次先序遍历根的各子树
后根（序）遍历，若T非空，则：
1、依次后序遍历根的各子树
2、访问根结点R
此外，树的先根 / 后根遍历，和它对应的二叉树的先序 / 中序遍历，结果是完全一样的（这是树和二叉树转换规则带来的必然结果）
遍历森林
1. 先序遍历森林
- 先访问第一棵树的根；
- 再先序遍历这棵树的子树（子树组成的小森林）；
- 最后先序遍历剩下的树组成的森林。→ 对应森林转成的二叉树的先序遍历。
2. 中序遍历森林
- 先中序遍历第一棵树的子树（子树组成的小森林）；
- 再访问这棵树的根；
- 最后中序遍历剩下的树组成的森林。→ 对应森林转成的二叉树的中序遍历
森林的先序 / 中序遍历，和它转成的二叉树的先序 / 中序遍历，结果完全一致；而二叉树的后序遍历，则是森林特有的遍历序列。
赫夫曼(Huffman)树及应用
赫夫曼(Huffman)树，又称最优树，是一类带权路径长度最短的树，有着广泛的应用。本节先讨论最优二叉树。
路径，路径长度：
从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径，路径上的分支数目称做路径长度。树的路径长度是从树根到每一结点的路径长度之和。6.2.1节中定义的完全二叉树就是这种路径长度最短的二叉树
若将上述概念推广到一般情况，考虑带权的结点。结点的带权路径长度为从该结点到树根之间的路径长度与结点上权的乘积。树的带权路径长度为树中所有叶子结点的带权路径长度之和，通常记作WPL
例：从 A 到 B，C，D，E，F，G，H，I 的路径长度分别为：1，1，2，2，2，3，3，3
树的路径长度：1+1+2+2+2+3+3+3=17
赫夫曼树——最优二叉树定义
设有n个权值w1 w2 …… wn ，构造一棵有n个叶子结点的二叉树，每个叶子的权值为wi,则wpl最小的那棵二叉树叫最优二叉树或Huffman树.
在解某些判定问题时，利用赫夫曼树可以得到最佳判定算法。例如，要编制一个将百分制转换成五级分制的程序。显然，此程序很简单，只要利用条件语句便可完成。如：
def score_to_grade(a):
# 先验证输入是否为有效分数（0-100）
if not isinstance(a, (int, float)) or a < 0 or a > 100:
return "无效分数"
# 按条件判定
if a < 60:
b = "bad"
elif a < 70:
b = "pass"
elif a < 80:
b = "general"
elif a < 90:
b = "good"
else:
b = "excellent"
return b这个判定过程可以图 6.23 (a) 的判定树来表示。如果上述程序需反复使用，而且每次的输入量很大，则应考虑上述程序的质量问题，即其操作所需时间。因为在实际生活中，学生的成绩在 5 个等级上的分布是不均匀的。假设其分布规律如下表所示：
| 分数 | 0—59 | 60—69 | 70—79 | 80—89 | 90—100 |
|---|---|---|---|---|---|
| 比例数 | 0.05 | 0.15 | 0.40 | 0.30 | 0.10 |
则 80% 以上的数据需进行 3 次或 3 次以上的比较才能得出结果。假定以 5,15,40,30 和 10 为权构造一棵有 5 个叶子结点的赫夫曼树，则可得到如图 6.23 (b) 所示的判定过程，它可使大部分的数据经过较少的比较次数得出结果。但由于每个判定框都有两次比较，将这两次比较分开，我们得到如图 6.23 (c) 所示的判定树，按此判定树可写出相应的程序。
假设现有 10 000 个输入数据，若按图 6.23 (a) 的判定过程进行操作，则总共需进行 31 500 次比较；而若按图 6.23 (c) 的判定过程进行操作，则总共仅需进行 22 000 次比较。
构造赫尔曼树
假设最优树的叶子权值从小到大是 \(w_1 \leq w_2 \leq … \leq w_n\)，则：
- a) 权值最小的两个叶子（\(w_1\)、\(w_2\)）是兄弟：最优树要让整体路径长度最小，就得让 “权值小的叶子” 放在路径最长的位置（这样 “权值 × 路径长度” 的总和才小）；而路径最长的位置，就是二叉树的最底层，所以最小的两个权值会作为兄弟节点放在最底层。
- b) 这两个叶子的父节点（分枝点），路径长度最长：因为这两个叶子在最底层，它们的父节点也在相对靠下的位置，所以从根到这个父节点的路径长度，是所有分枝点中最长的。
如果把 “\(w_1\)、\(w_2\) 这两个叶子的父节点”，替换成一个权值为 \(w_1 + w_2\) 的新叶子，得到的新树 \(T’\) 也是最优树。
这其实是赫夫曼树的构造方法：每次选两个最小的权值合并成一个新权值，重复这个过程直到只剩一个节点 —— 因为合并后新树的 WPL 依然是最小的，所以是最优树。
Huffman 树的构造：
- 根据给定的 n 个权值 {w1,w2,……wn} 构成 n 棵二叉树的集合 F={T1,T2,……Tn}，其中每棵二叉树 Ti 中只有一个带权为 Wi 的结点，其左右子树均为空。（构造森林全是根）
- 在 F 中选取两棵根结点权值最小的树作左右子树，构造一棵新的二叉树，且置新的二叉树根结点的权值为其左右子树根结点权值之和。（选用两小造新树）
- 在 F 中删除这两棵树，同时将新得到的二叉树加入森林中。（删除两小添新人）
- 重复 2、3 上述两步，直到 F 只含一棵树为止，这棵树即为赫夫曼树
Huffman编码
// 函数功能：构造赫夫曼树，并为其生成赫夫曼编码
// 参数说明：
// - HT：赫夫曼树（输出参数，存储树的结构）
// - HC：赫夫曼编码（输出参数，存储每个叶子的编码）
// - w：存储n个叶子权值的数组
// - n：叶子结点的数量
void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n)
{
// 若只有0个或1个叶子，无需构造赫夫曼树（赫夫曼树至少需要2个叶子）
if (n <= 1) return;
// 赫夫曼树的总结点数公式：m = 2*n - 1（n个叶子 + n-1个分支结点）
m = 2 * n - 1;
// 为赫夫曼树分配内存：结点下标从1开始（共m+1个空间，0号不用）
// HTNode是赫夫曼树结点的结构体（包含weight、parent、lchild、rchild四个字段）
HT = (HuffmanTree)malloc((m + 1) * sizeof(HTNode));
// 初始化前n个结点（叶子结点）：
// p指向HT的当前结点，i是循环变量，w是权值数组
for (p = HT, i = 1; i <= n; ++i, ++p, ++w)
// 叶子结点的权值为*w，parent/lchild/rchild初始化为0（无父/子结点）
*p = {*w, 0, 0, 0};
// 初始化剩余m-n个结点（分支结点）：权值、父、左右子均初始化为0
for (; i <= m; ++i, ++p) *p = {0, 0, 0, 0};
// 构造赫夫曼树的核心循环：生成n-1个分支结点（从n+1到m）
for (i = n + 1; i <= m; ++i) {
// 从当前森林（前i-1个结点）中，选择权值最小的两个结点，下标存入s1、s2
select(HT, i - 1, s1, s2);
// 将选中的两个结点的parent设为当前分支结点i（标记为已合并）
HT[s1].parent = i;
HT[s2].parent = i;
// 当前分支结点i的左孩子是s1，右孩子是s2
HT[i].lchild = s1;
HT[i].rchild = s2;
// 当前分支结点i的权值 = 两个孩子结点的权值之和
HT[i].weight = HT[s1].weight + HT[s2].weight;
}
}
