哈夫曼树原理及其C语言实现
目录
原理
应用场景
实现步骤
C语言实现
总结
原理
哈夫曼树（Huffman Tree），又称最优二叉树，是一种带权路径长度最短的二叉树，广泛应用于数据压缩领域。所谓树的带权路径长度，是指树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为第0层，叶结点到根结点的路径长度为叶结点的层数）之和。它的核心思想是：权值越大的节点离根越近，权值越小的节点离根越远，从而最小化整体的带权路径长度（WPL）。
关键概念：
-
权值（Weight）：节点的权重（如字符出现的频率）。
-
路径长度：从根节点到某节点的边数。
-
带权路径长度（WPL）：所有叶子节点的权值 × 路径长度之和。
哈夫曼树的构造基于贪心算法，具体步骤如下：
- 初始状态：给定N个权值，将它们视为N棵仅含一个结点的树（森林）。
- 选择合并：在森林中选出两个根结点权值最小的树，将它们合并为一棵新树，新树的根结点权值为这两个子树根结点权值之和。
- 更新森林：从森林中删除这两个最小的树，并将新树加入森林。
- 重复操作：重复步骤2和3，直到森林中只剩下一棵树，这棵树即为所求得的哈夫曼树。
以下是一个简单的哈夫曼树构造过程的图形化展示（假设初始权值为2, 3, 6, 8, 9）：
- 初始状态：五棵独立的树，每棵树的权值分别为2, 3, 6, 8, 9。
- 第一次合并：选择权值最小的两棵树（权值为2和3），合并成新树，新树的权值为5。
- 第二次合并：再次选择权值最小的两棵树（此时为权值为5和6的树），合并成新树，新树的权值为11。
- 后续合并：继续上述过程，直到所有树合并为一棵哈夫曼树。
示例：假设字符集 {A, B, C, D} 的权值分别为 {5, 2, 1, 3}，哈夫曼树构建过程如下：
Step 1: 最小权值 C(1) 和 B(2) → 合并为权值3的父节点
Step 2: 新节点3 和 D(3) → 合并为权值6的父节点
Step 3: 合并 A(5) 和 6 → 最终根节点权值11
最终哈夫曼树：
11
/ \
5 6
/ \
3 3
/ \
1 2 (B)
(C)应用场景
-
数据压缩：哈夫曼编码（Huffman Coding）将高频字符用短编码，低频字符用长编码。
-
文件压缩工具：如 ZIP、GZIP 使用哈夫曼算法。
-
图像压缩：JPEG 格式中的熵编码阶段。
-
通信协议：优化数据传输效率。
实现步骤
哈夫曼树的实现步骤：
-
统计字符频率：遍历数据，统计每个字符的出现次数作为权值。
-
构建最小堆：将所有字符节点按权值排序，形成优先队列（最小堆）。
-
合并节点：循环取出权值最小的两个节点，合并为新节点，放回堆中。
-
生成编码表：从根节点出发，向左为0，向右为1，记录叶子节点的路径编码。
-
压缩与解压：根据编码表将原始数据转换为二进制流，或反向解码。
C语言实现
1. 定义哈夫曼树节点结构
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_TREE_NODES 256
typedef struct HuffmanNode {
char ch; // 字符（叶子节点有效）
int weight; // 权值（字符频率）
struct HuffmanNode *left, *right; // 左右子节点
} HuffmanNode;
typedef struct PriorityQueue {
HuffmanNode **nodes; // 节点指针数组
int size; // 当前堆大小
int capacity; // 堆容量
} PriorityQueue;2. 构建最小堆（优先队列）
// 初始化优先队列
PriorityQueue* createQueue(int capacity) {
PriorityQueue* queue = (PriorityQueue*)malloc(sizeof(PriorityQueue));
queue->nodes = (HuffmanNode**)malloc(capacity * sizeof(HuffmanNode*));
queue->size = 0;
queue->capacity = capacity;
return queue;
}
// 上浮调整（插入节点时保持最小堆性质）
void heapifyUp(PriorityQueue* queue, int index) {
int parent = (index - 1) / 2;
while (index > 0 && queue->nodes[index]->weight < queue->nodes[parent]->weight) {
HuffmanNode* temp = queue->nodes[index];
queue->nodes[index] = queue->nodes[parent];
queue->nodes[parent] = temp;
index = parent;
parent = (index - 1) / 2;
}
}
// 下沉调整（删除节点时保持最小堆性质）
void heapifyDown(PriorityQueue* queue, int index) {
int left = 2 * index + 1;
int right = 2 * index + 2;
int smallest = index;
if (left < queue->size && queue->nodes[left]->weight < queue->nodes[smallest]->weight) {
smallest = left;
}
if (right < queue->size && queue->nodes[right]->weight < queue->nodes[smallest]->weight) {
smallest = right;
}
if (smallest != index) {
HuffmanNode* temp = queue->nodes[index];
queue->nodes[index] = queue->nodes[smallest];
queue->nodes[smallest] = temp;
heapifyDown(queue, smallest);
}
}
// 插入节点
void enqueue(PriorityQueue* queue, HuffmanNode* node) {
if (queue->size >= queue->capacity) return;
queue->nodes[queue->size] = node;
heapifyUp(queue, queue->size);
queue->size++;
}
// 取出权值最小的节点
HuffmanNode* dequeue(PriorityQueue* queue) {
if (queue->size == 0) return NULL;
HuffmanNode* minNode = queue->nodes[0];
queue->nodes[0] = queue->nodes[queue->size - 1];
queue->size--;
heapifyDown(queue, 0);
return minNode;
}3. 构建哈夫曼树
// 创建叶子节点
HuffmanNode* createLeafNode(char ch, int weight) {
HuffmanNode* node = (HuffmanNode*)malloc(sizeof(HuffmanNode));
node->ch = ch;
node->weight = weight;
node->left = node->right = NULL;
return node;
}
// 构建哈夫曼树
HuffmanNode* buildHuffmanTree(char data[], int weights[], int n) {
PriorityQueue* queue = createQueue(MAX_TREE_NODES);
for (int i = 0; i < n; i++) {
HuffmanNode* node = createLeafNode(data[i], weights[i]);
enqueue(queue, node);
}
while (queue->size > 1) {
HuffmanNode* left = dequeue(queue);
HuffmanNode* right = dequeue(queue);
HuffmanNode* parent = (HuffmanNode*)malloc(sizeof(HuffmanNode));
parent->ch = '\0'; // 内部节点无字符
parent->weight = left->weight + right->weight;
parent->left = left;
parent->right = right;
enqueue(queue, parent);
}
HuffmanNode* root = dequeue(queue);
free(queue->nodes);
free(queue);
return root;
}4. 生成哈夫曼编码表
void generateCodes(HuffmanNode* root, char* code, int depth, char** codes) {
if (root == NULL) return;
if (root->left == NULL && root->right == NULL) { // 叶子节点
code[depth] = '\0';
codes[(unsigned char)root->ch] = strdup(code);
return;
}
code[depth] = '0';
generateCodes(root->left, code, depth + 1, codes);
code[depth] = '1';
generateCodes(root->right, code, depth + 1, codes);
}5. 压缩与解压示例
// 压缩函数（将字符串转换为哈夫曼编码）
char* compress(char* input, char** codes) {
int len = strlen(input);
char* compressed = (char*)malloc(MAX_TREE_NODES * len);
compressed[0] = '\0';
for (int i = 0; i < len; i++) {
strcat(compressed, codes[(unsigned char)input[i]]);
}
return compressed;
}
// 解压函数（根据哈夫曼树解码）
void decompress(HuffmanNode* root, char* compressed) {
HuffmanNode* current = root;
int len = strlen(compressed);
for (int i = 0; i < len; i++) {
if (compressed[i] == '0') {
current = current->left;
} else {
current = current->right;
}
if (current->left == NULL && current->right == NULL) {
printf("%c", current->ch);
current = root; // 重置到根节点继续解码
}
}
}6. 测试代码
int main() {
char data[] = {'A', 'B', 'C', 'D'};
int weights[] = {5, 2, 1, 3};
int n = sizeof(data) / sizeof(data[0]);
// 构建哈夫曼树
HuffmanNode* root = buildHuffmanTree(data, weights, n);
// 生成编码表
char* codes[MAX_TREE_NODES] = {NULL};
char code[MAX_TREE_NODES];
generateCodes(root, code, 0, codes);
// 打印编码
printf("哈夫曼编码表:\n");
for (int i = 0; i < MAX_TREE_NODES; i++) {
if (codes[i] != NULL) {
printf("%c: %s\n", (char)i, codes[i]);
}
}
// 压缩示例
char* input = "ABACAD";
char* compressed = compress(input, codes);
printf("\n原始数据: %s\n压缩后的二进制: %s\n", input, compressed);
// 解压示例
printf("解压结果: ");
decompress(root, compressed);
printf("\n");
// 释放内存（略）
return 0;
}输出示例
哈夫曼编码表:
A: 0
B: 110
C: 111
D: 10
原始数据: ABACAD
压缩后的二进制: 01100111010
解压结果: ABACAD总结
-
优点：哈夫曼编码是无损压缩，保证数据完整性。
-
缺点：需存储编码表，压缩率依赖字符频率分布。
-
优化方向：动态哈夫曼编码（适应数据变化）、结合其他算法（如LZ77）。