----哈夫曼树：从原理到代码实现)
一、什么是哈夫曼树哈夫曼树Huffman Tree又称最优二叉树是一种带权路径长度最短的二叉树。在数据压缩领域哈夫曼树有着广泛的应用哈夫曼编码就是其在电讯通信中的经典应用之一。在深入理解哈夫曼树之前我们需要先掌握几个核心概念路径与路径长度在一棵树中从一个结点到另一个结点所经过的通路称为路径路径上所经过的边的数量就是路径长度。从根结点到第 i 层结点的路径长度为 i-1。结点的权给树中每个结点赋予的一个有某种意义的数值。结点的带权路径长度从根结点到该结点的路径长度与该结点权值的乘积。树的带权路径长度WPL树中所有叶子结点的带权路径长度之和。哈夫曼树的定义就是在叶子结点和权重确定的情况下带权路径长度最小的二叉树。权重越大的结点离树根越近这样能使WPL达到最小。二、哈夫曼树的构造算法哈夫曼树的构造过程遵循一个简单而巧妙的贪心算法根据给定的 n 个权值构造 n 棵只有根结点的二叉树这些二叉树构成一个森林在森林中选取两棵根结点权值最小的树作为左右子树构造一棵新的二叉树新根结点的权值为两棵子树根结点权值之和从森林中删除这两棵树将新得到的二叉树加入森林重复步骤2和3直到森林中只剩一棵树为止以权重 2、3、7、9、18、25 为例先选出最小的2和3合并为5再从当前集合{5,7,9,18,25}中选出最小的5和7合并为12以此类推直到所有结点合并成一棵树。三、C语言代码实现下面我们来分析一份完整的哈夫曼树C语言实现代码。3.1 结点结构定义typedef struct { int weight; // 权值 int parent; // 父结点下标 int lchild; // 左孩子下标 int rchild; // 右孩子下标 } HuffmanNode, *HuffmanTree;这里采用顺序存储结构数组来存储哈夫曼树。每个结点包含四个字段权值、父结点下标、左右孩子下标。哈夫曼树一般没有增删改查的操作一旦创建就直接使用因此数组存储已经足够。3.2 选择最小权值结点static void selectMinNode(HuffmanTree tree, int n, int* s1, int* s2) { int minIndex 0; // 找到第一个父节点为0的值让他做参考 for (int i 1; i n; i) { if (tree[i].parent 0) { minIndex i; break; } } // 比较下列的值若有更小的值则更新 for (int i 1; i n; i) { if (tree[i].weight tree[minIndex].weight tree[i].parent 0) { minIndex i; } } *s1 minIndex; // 找到第一个父节点为0的值让他做参考排除s1 for (int i 1; i n; i) { if (tree[i].parent 0 i ! *s1) { minIndex i; break; } } // 比较下列的值若有更小的值则更新排除s1 for (int i 1; i n; i) { if (tree[i].weight tree[minIndex].weight tree[i].parent 0 i ! *s1) { minIndex i; } } *s2 minIndex; }selectMinNode函数的作用是在前 n 个结点中找出父结点为0即尚未被合并的两个权值最小的结点。函数分两次查找第一次找出最小权值结点存入s1第二次找出次小权值结点存入s2每次查找时都要排除已选中的结点。3.3 构建哈夫曼树HuffmanTree createHuffmanTree(const int* w, int n) { HuffmanTree tree; int m 2 * n - 1; // 哈夫曼树共有 2n-1 个结点 tree malloc(sizeof(HuffmanNode) * (m 1)); if (tree NULL) { return NULL; } memset(tree, 0, sizeof(HuffmanNode) * (m 1)); // 初始化前 n 个叶子结点 for (int i 1; i n; i) { tree[i].weight w[i - 1]; } int s1, s2; // 从 n1 到 m逐步构造内部结点 for (int i n 1; i m; i) { selectMinNode(tree, i - 1, s1, s2); tree[s1].parent tree[s2].parent i; tree[i].lchild s1; tree[i].rchild s2; tree[i].weight tree[s1].weight tree[s2].weight; } return tree; }核心逻辑如下一棵有 n 个叶子结点的哈夫曼树共有2n-1个结点前 n 个位置存放初始的叶子结点从 n1 开始每次选取两个权值最小的结点合并产生新结点新结点的权值为两子结点权值之和左右孩子分别指向两个子结点两个子结点的 parent 更新为新结点的下标3.4 打印与测试void showHuffmanTree(HuffmanTree tree, int m) { for (int i 1; i m; i) { printf(%d\t%d\t%d\t%d\t%d\n, i, tree[i].weight, tree[i].parent, tree[i].lchild, tree[i].rchild); } } int main() { int w[] { 5, 29, 7, 8, 14, 23, 3, 11 }; char show[] { A, B, C, D, E, F, G, H }; HuffmanTree tree createHuffmanTree(w, sizeof(w) / sizeof(w[0])); showHuffmanTree(tree, 2 * (sizeof(w) / sizeof(w[0])) - 1); }测试数据为 8 个权值5、29、7、8、14、23、3、11对应字符 A 到 H。四、哈夫曼编码4.1 为什么需要变长编码定长编码如ASCII每个字符使用固定长度的二进制位。对于仅包含ASCII字符的纯文本每个字符占8位存在明显的空间浪费。而变长编码的思想是赋予高频字符短码字低频字符长码字。4.2 前缀码变长编码面临一个问题如何避免解码时的二义性前缀码的定义是没有任何码字是其他码字的前缀。例如如果 a 的编码是 0那么其他所有字符的编码都不能以 0 开头。哈夫曼编码正是一种前缀码。在哈夫曼树中每个字符都对应一个叶子结点从根到该叶子结点的路径就构成了该字符的编码——左子树为0右子树为1。由于所有字符都在叶子结点上没有任何一个字符的编码会是另一个字符编码的前缀。4.3 压缩效果哈夫曼编码的压缩率通常在 20% 到 90% 之间具体取决于数据的特性。例如对一个包含6个不同字符、共10万个字符的文件定长编码需要30万位而哈夫曼编码仅需22.4万位。在现代应用中哈夫曼编码被广泛应用于ZIP压缩、PNG图像、HTTP/2头部压缩及多媒体处理等领域。五、总结哈夫曼树的核心价值在于通过贪心策略构建带权路径长度最小的二叉树从而实现最优的数据压缩。理解哈夫曼树需要掌握以下要点带权路径长度WPL是衡量二叉树性能的关键指标WPL越小树的性能越优构造算法本质是贪心——每次合并权值最小的两个结点哈夫曼编码是一种前缀码能保证解码的唯一性代码实现采用顺序存储结构通过数组模拟树形结构
