数据结构：哈夫曼树
1.概念
哈夫曼树（Huffman Tree）是一种用于数据压缩的二叉树，由大卫·哈夫曼（David A. Huffman）于1952年提出。它通过构建最优二叉树来实现数据的高效压缩，广泛应用于文件压缩、图像压缩等领域。
哈夫曼树的核心思想
哈夫曼树的核心思想是用较短的编码表示出现频率较高的字符，用较长的编码表示出现频率较低的字符，从而减少整体的编码长度。
2.构建哈夫曼树的步骤
-
统计字符频率：
-
统计待压缩数据中每个字符出现的频率。
-
-
创建节点：
-
为每个字符创建一个节点，节点的权重为字符的频率。
-
-
构建优先队列：
-
将所有节点放入一个优先队列（最小堆），按权重从小到大排序。
-
-
合并节点：
-
从优先队列中取出权重最小的两个节点，合并成一个新节点，新节点的权重为这两个节点的权重之和。
-
将新节点放回优先队列。
-
-
重复合并：
-
重复上述步骤，直到优先队列中只剩一个节点，这个节点就是哈夫曼树的根节点。
-
-
生成编码：
-
从根节点开始，向左子树走标记为0，向右子树走标记为1，直到叶子节点，得到每个字符的哈夫曼编码。
-
3.哈夫曼树的特点
-
最优前缀编码：哈夫曼编码是一种前缀编码，没有任何一个编码是另一个编码的前缀。
-
最小加权路径长度：哈夫曼树的带权路径长度（WPL）最小，即压缩效率最高。
示例
假设有以下字符及其频率：
-
A: 5
-
B: 9
-
C: 12
-
D: 13
-
E: 16
-
F: 45
构建哈夫曼树的过程：
-
将所有字符节点放入优先队列。
-
取出A(5)和B(9)，合并为新节点(14)，放回队列。
-
取出C(12)和D(13)，合并为新节点(25)，放回队列。
-
取出E(16)和新节点(14)，合并为新节点(30)，放回队列。
-
取出新节点(25)和F(45)，合并为新节点(70)，放回队列。
-
取出新节点(30)和新节点(70)，合并为根节点(100)。
根据哈夫曼树的构建规则和正确的路径长度过程：
(100)
/ \
(30) (70)
/ \ / \
(14) E(16) (25) F(45)
/ \ / \
A(5) B(9) C(12) D(13)
路径长度：
-
A：根 → 30 → 14 → A，路径长度 3。
-
B：根 → 30 → 14 → B，路径长度 3。
-
C：根 → 70 → 25 → C，路径长度 3。
-
D：根 → 70 → 25 → D，路径长度 3。
-
E：根 → 30 → E，路径长度 2。
-
F：根 → 70 → F，路径长度 2。
计算 WPL
| 字符 | 权重（频率） | 路径长度 | 权重 × 路径长度 |
|---|---|---|---|
| A | 5 | 3 | 5×3=15 |
| B | 9 | 3 | 9×3=27 |
| C | 12 | 3 | 12×3=36 |
| D | 13 | 3 | 13×3=39 |
| E | 16 | 2 | 16×2=32 |
| F | 45 | 2 | 45×2=90 |
WPL 总和：
15+27+36+39+32+90=239
总结
路径长度是哈夫曼树中一个重要的概念，它直接决定了每个字符的编码长度。通过最小化带权路径长度（WPL），哈夫曼树能够实现数据的高效压缩。