好的学习网站打广告,个人站长和企业网站,ctoc网站有哪些,柳江网站开发哈夫曼树#xff08;Huffman Tree#xff09;是一种最优的二叉树#xff0c;常用于数据压缩#xff0c;如在 Huffman 编码中使用。它是根据字符出现的频率来构造的#xff0c;频率越高的字符越靠近树的根#xff0c;频率低的字符则在较深的节点上。其核心思想是通过构建一… 哈夫曼树Huffman Tree是一种最优的二叉树常用于数据压缩如在 Huffman 编码中使用。它是根据字符出现的频率来构造的频率越高的字符越靠近树的根频率低的字符则在较深的节点上。其核心思想是通过构建一颗最小堆或者优先队列来逐步合并最小的两个节点直到所有节点都合并成一颗哈夫曼树。 哈夫曼树的构建过程 统计频率首先统计每个字符出现的频率。构建最小堆将每个字符作为一个树的节点插入一个最小堆优先队列中。合并最小频率的节点每次从最小堆中取出两个频率最小的节点创建一个新节点其频率为这两个节点频率之和。然后将这个新节点插入回最小堆。重复步骤3直到堆中只剩下一个节点这个节点就是哈夫曼树的根节点 #include iostream
#include queue
#include vector
#include unordered_map
#include stringusing 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_mapchar, 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_mapchar, int freq) {// 优先队列最小堆用于按频率排序priority_queueHuffmanNode*, vectorHuffmanNode*, 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_mapchar, 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_mapchar, int freq;for (char c : text) {freq[c];}// 构建哈夫曼树HuffmanNode* root buildHuffmanTree(freq);// 保存每个字符的哈夫曼编码unordered_mapchar, string huffmanCode;// 生成哈夫曼编码generateHuffmanCodes(root, , huffmanCode);// 打印哈夫曼编码printHuffmanCodes(huffmanCode);return 0;
}
