应用
二叉搜索树（BST）
左子树 < 根 < 右子树。查找、插入、删除平均 。中序遍历 BST 得到有序序列。
平衡二叉树（AVL）
任意结点左右子树高度差（平衡因子）不超过 1。插入、删除后通过旋转（LL、RR、LR、RL）恢复平衡，保证 的查找效率。
哈夫曼树与哈夫曼编码
- 哈夫曼树（最优二叉树）：带权路径长度（WPL）最小的二叉树
- 构造方法：每次选权值最小的两个结点合并，直到只剩一棵树
- 哈夫曼编码：左分支 0、右分支 1，用于数据压缩（前缀编码，无歧义）
习题
习题 1
(2023 年 408 真题) 在由 6 个字符组成的字符集 S 中，各字符出现的频次分别为 3, 4, 5, 6, 8, 10，为 S 构造的哈夫曼编码的加权平均长度为（ ）。
A. 2.4 B. 2.5 C. 2.67 D. 2.75
答案与解析
答案
B
解析
构造哈夫曼树的过程如下：
- 将频次从小到大排序：3, 4, 5, 6, 8, 10。
- 选取最小的两个频次 3 和 4，合并成新节点，权值为 7。
- 剩余频次为 5, 6, 7, 8, 10。选取最小的两个 5 和 6，合并成新节点，权值为 11。
- 剩余频次为 7, 8, 10, 11。选取最小的两个 7 和 8，合并成新节点，权值为 15。
- 剩余频次为 10, 11, 15。选取最小的两个 10 和 11，合并成新节点，权值为 21。
- 剩余频次为 15, 21。合并成根节点，权值为 36。
计算加权路径长度 (WPL)：
- 频次为 10 的字符编码长度为 2。
- 频次为 8 的字符编码长度为 2。
- 频次为 6 的字符编码长度为 3。
- 频次为 5 的字符编码长度为 3。
- 频次为 4 的字符编码长度为 3。
- 频次为 3 的字符编码长度为 3。
WPL = (10 × 2) + (8 × 2) + (6 × 3) + (5 × 3) + (4 × 3) + (3 × 3) = 20 + 16 + 18 + 15 + 12 + 9 = 90
加权平均长度 = WPL / 总频次 = 90 / (3+4+5+6+8+10) = 90 / 36 = 2.5
习题 2
哈夫曼树的主要应用是什么？
答案与解析
哈夫曼树的主要应用是哈夫曼编码（最优前缀编码），用于数据压缩。出现频率高的字符用短编码，频率低的用长编码，使总编码长度最短。由于任何字符的编码都不是其他字符编码的前缀，解码无歧义。此外还可用于构造最优判定树。