【数据结构】霍夫曼树

1.概念

霍夫曼树（Huffman Tree），又称最优二叉树，是一种带权路径长度最短的二叉树。在霍夫曼树中，叶子节点的权值通常代表字符出现的频率，非叶子节点的权值是其子节点权值的和。霍夫曼树广泛应用于数据压缩，尤其是霍夫曼编码，它是一种基于字符出现频率的变长前缀编码。

霍夫曼树的构建过程如下：

权值集合：首先，将给定的字符和它们对应的权值（频率）放入一个集合中。
选择最小的权值：每次从集合中选出两个具有最小权值的节点，将它们合并成一个新节点，新节点的权值是这两个子节点权值的和。
删除并添加：将选出的两个最小权值节点从集合中删除，并将新创建的节点添加到集合中。
重复步骤2和3：重复步骤2和3，直到集合中只剩下一个节点，这个节点就是霍夫曼树的根节点。
构建完成：此时，霍夫曼树构建完成，每个原始节点都成为了叶子节点，而新创建的节点都是非叶子节点。

霍夫曼编码的过程如下：

为每个叶子节点分配码字：从根节点开始，向左的路径分配0，向右的路径分配1。这样，每个叶子节点都会得到一个唯一的二进制编码。
构建编码表：将每个字符和它对应的霍夫曼编码放入一个编码表中。
编码：使用编码表对原始数据进行编码，替换每个字符为其对应的霍夫曼编码。
解码：解码时，从霍夫曼树的根节点开始，根据编码的0和1向左或向右移动。每次到达一个叶子节点，就输出对应的字符，然后从根节点开始继续解码过程。

霍夫曼编码是一种前缀编码，即任何一个字符的编码都不是另一个字符编码的前缀，这样可以保证编码的唯一可解性。由于频率高的字符分配的编码较短，频率低的字符分配的编码较长，因此霍夫曼编码能够实现数据的压缩。

2.如何自己实现霍夫曼编码？

实现霍夫曼编码需要定义数据结构来表示霍夫曼树节点，以及实现构建霍夫曼树和编码的过程。以下是一个简单的 C 语言实现。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>// 定义霍夫曼树节点结构
typedef struct {char ch;                // 字符（仅用于叶子节点）int freq;               // 字符频率char code[100];         // 霍夫曼编码struct HuffmanNode *left, *right; // 左右子树指针
} HuffmanNode;// 函数声明
HuffmanNode* createNode(int freq, char ch);
void printCodes(HuffmanNode* root, char* arr, int top);
void buildHuffmanTree(char ch[], int freq[], int size);
void destroyTree(HuffmanNode* root);int main() {int n, i;printf("请输入字符的数量：");scanf("%d", &n);char ch[n];int freq[n];printf("请输入字符及其频率（例如：a 5）：\n");for(i = 0; i < n; i++) {scanf(" %c %d", &ch[i], &freq[i]);}buildHuffmanTree(ch, freq, n);return 0;
}// 创建一个新的霍夫曼树节点
HuffmanNode* createNode(int freq, char ch) {HuffmanNode* newNode = (HuffmanNode*)malloc(sizeof(HuffmanNode));newNode->ch = ch;newNode->freq = freq;newNode->left = newNode->right = NULL;strcpy(newNode->code, "");return newNode;
}// 打印霍夫曼编码
void printCodes(HuffmanNode* root, char* arr, int top) {if (root->left) {arr[top] = '0';printCodes(root->left, arr, top + 1);}if (root->right) {arr[top] = '1';printCodes(root->right, arr, top + 1);}if (!root->left && !root->right) {printf("%c: %s\n", root->ch, root->code);strcpy(root->code, arr);}
}// 构建霍夫曼树
void buildHuffmanTree(char ch[], int freq[], int size) {HuffmanNode *left, *right, *top;// 创建一个节点数组HuffmanNode* nodes[size];for(int i = 0; i < size; i++) {nodes[i] = createNode(freq[i], ch[i]);}// 构建霍夫曼树for(int i = 0; i < size - 1; i++) {// 找到两个最小频率的节点HuffmanNode* min1 = NULL, *min2 = NULL;for(int j = 0; j < size; j++) {if(nodes[j] && (!min1 || nodes[j]->freq < min1->freq)) {min2 = min1;min1 = nodes[j];} else if(nodes[j] && (!min2 || nodes[j]->freq < min2->freq)) {min2 = nodes[j];}}// 创建一个新的内部节点top = createNode(min1->freq + min2->freq, '\0');top->left = min1;top->right = min2;// 从节点数组中移除已合并的节点nodes[size + i] = top;nodes[min1 - nodes] = NULL;nodes[min2 - nodes] = NULL;}// 打印霍夫曼编码char arr[100];printCodes(nodes[size + size - 2], arr, 0);// 释放内存for(int i = 0; i < size; i++) {destroyTree(nodes[i]);}
}// 销毁霍夫曼树
void destroyTree(HuffmanNode* root) {if(root) {destroyTree(root->left);destroyTree(root->right);free(root);}
}

这段代码定义了霍夫曼树节点的结构，并提供了一个简单的命令行界面来输入字符及其频率。然后，它构建了霍夫曼树并打印了每个字符的霍夫曼编码。最后，它释放了分配给霍夫曼树的内存。

请注意，这个实现是为了演示目的而简化的。在实际应用中，霍夫曼编码的构建和解析通常更复杂，需要处理更多的边缘情况和优化。

以上就是霍夫曼树的基本使用，本次代码分享到此结束，后续还会更新数据结构与算法的知识。最后的最后，还请大家点点赞，点点关注，谢谢大家！