哈夫曼编码的核心思想是利用字符出现的频率来构建一个最优的二叉树,使得每个字符的编码长度尽可能短。构建过程如下:
统计频率:首先统计每个字符出现的频率。构建优先队列:将每个字符及其频率作为节点,构建一个优先队列(通常是最小堆)。构建哈夫曼树:不断从优先队列中取出两个频率最小的节点,将它们合并为一个新节点,新节点的频率为两个节点频率之和,然后将新节点重新加入优先队列。生成编码:从根节点开始,向左子树走标记为0,向右子树走标记为1,直到到达叶子节点,此时叶子节点的路径即为对应字符的编码。 哈夫曼编码的C++实现下面是一个C++实现示例:
#include #include #include #include #include using namespace std;struct Node {char data;int freq;Node* left;Node* right;Node(char d, int f) : data(d), freq(f), left(nullptr), right(nullptr) {}};// 比较函数,用于最小堆bool compare(Node* l, Node* r) {return l->freq > r->freq;}// 构建哈夫曼树Node* buildHuffmanTree(vector freq) {priority_queue minHeap(compare);for (int i = 0; i < freq.size(); ++i) {minHeap.push(new Node('A' + i, freq[i]));}while (minHeap.size() != 1) {Node* left = minHeap.top();minHeap.pop();Node* right = minHeap.top();minHeap.pop();Node* sum = new Node('$', left->freq + right->freq);sum->left = left;sum->right = right;minHeap.push(sum);}return minHeap.top();}// 打印哈夫曼编码void printCodes(Node* root, string str) {if (root->left == nullptr && root->right == nullptr) {cout data