哈夫曼树
哈夫曼树（Huffman Tree）是一种最优的二叉树，常用于数据压缩，如在 Huffman 编码中使用。它是根据字符出现的频率来构造的，频率越高的字符越靠近树的根，频率低的字符则在较深的节点上。其核心思想是通过构建一颗最小堆（或者优先队列）来逐步合并最小的两个节点，直到所有节点都合并成一颗哈夫曼树。
哈夫曼树的构建过程：
- 统计频率：首先统计每个字符出现的频率。
- 构建最小堆：将每个字符作为一个树的节点插入一个最小堆（优先队列）中。
- 合并最小频率的节点：每次从最小堆中取出两个频率最小的节点，创建一个新节点，其频率为这两个节点频率之和。然后将这个新节点插入回最小堆。
- 重复步骤3，直到堆中只剩下一个节点，这个节点就是哈夫曼树的根节点
#include <iostream>
#include <queue>
#include <vector>
#include <unordered_map>
#include <string>using namespace std;// 哈夫曼树的节点
struct HuffmanNode {char ch; // 存储字符int freq; // 字符的频率HuffmanNode* left; // 左子树HuffmanNode* right; // 右子树// 构造函数HuffmanNode(char c, int f) : ch(c), freq(f), left(nullptr), right(nullptr) {}// 定义优先级队列的比较规则：按频率最小的优先struct Compare {bool operator()(HuffmanNode* l, HuffmanNode* r) {return l->freq > r->freq; // 返回 true 时 l 排在 r 后面}};
};// 用递归生成哈夫曼编码
void generateHuffmanCodes(HuffmanNode* root, const string& str, unordered_map<char, string>& huffmanCode) {if (root == nullptr)return;// 如果是叶子节点，保存它的编码if (!root->left && !root->right) {huffmanCode[root->ch] = str;}// 遍历左子树和右子树generateHuffmanCodes(root->left, str + "0", huffmanCode);generateHuffmanCodes(root->right, str + "1", huffmanCode);
}// 构造哈夫曼树
HuffmanNode* buildHuffmanTree(const unordered_map<char, int>& freq) {// 优先队列（最小堆）用于按频率排序priority_queue<HuffmanNode*, vector<HuffmanNode*>, HuffmanNode::Compare> minHeap;// 创建叶子节点并插入最小堆for (const auto& pair : freq) {minHeap.push(new HuffmanNode(pair.first, pair.second));}// 合并节点直到只剩一个节点while (minHeap.size() > 1) {// 取出两个最小的节点HuffmanNode* left = minHeap.top(); minHeap.pop();HuffmanNode* right = minHeap.top(); minHeap.pop();// 创建一个新的内部节点，频率为左右节点频率之和HuffmanNode* node = new HuffmanNode('\0', left->freq + right->freq);node->left = left;node->right = right;// 将新节点插入最小堆minHeap.push(node);}// 最后堆中剩下的节点就是哈夫曼树的根节点return minHeap.top();
}// 打印哈夫曼编码
void printHuffmanCodes(const unordered_map<char, string>& huffmanCode) {for (const auto& pair : huffmanCode) {cout << pair.first << ": " << pair.second << endl;}
}int main() {// 输入字符串string text = "this is an example for huffman encoding";// 统计每个字符的频率unordered_map<char, int> freq;for (char c : text) {freq[c]++;}// 构建哈夫曼树HuffmanNode* root = buildHuffmanTree(freq);// 保存每个字符的哈夫曼编码unordered_map<char, string> huffmanCode;// 生成哈夫曼编码generateHuffmanCodes(root, "", huffmanCode);// 打印哈夫曼编码printHuffmanCodes(huffmanCode);return 0;
}