哈夫曼樹（Huffman Tree）是一種最優(yōu)的二叉樹，常用于數(shù)據(jù)壓縮，如在 Huffman 編碼中使用。它是根據(jù)字符出現(xiàn)的頻率來構(gòu)造的，頻率越高的字符越靠近樹的根，頻率低的字符則在較深的節(jié)點(diǎn)上。其核心思想是通過構(gòu)建一顆最小堆（或者優(yōu)先隊列）來逐步合并最小的兩個節(jié)點(diǎn)，直到所有節(jié)點(diǎn)都合并成一顆哈夫曼樹。?

哈夫曼樹的構(gòu)建過程：

1. 統(tǒng)計頻率：首先統(tǒng)計每個字符出現(xiàn)的頻率。
2. 構(gòu)建最小堆：將每個字符作為一個樹的節(jié)點(diǎn)插入一個最小堆（優(yōu)先隊列）中。
3. 合并最小頻率的節(jié)點(diǎn)：每次從最小堆中取出兩個頻率最小的節(jié)點(diǎn)，創(chuàng)建一個新節(jié)點(diǎn)，其頻率為這兩個節(jié)點(diǎn)頻率之和。然后將這個新節(jié)點(diǎn)插入回最小堆。
4. 重復(fù)步驟3，直到堆中只剩下一個節(jié)點(diǎn)，這個節(jié)點(diǎn)就是哈夫曼樹的根節(jié)點(diǎn)

#include <iostream>
#include <queue>
#include <vector>
#include <unordered_map>
#include <string>using namespace std;// 哈夫曼樹的節(jié)點(diǎn)
struct HuffmanNode {char ch;              // 存儲字符int freq;             // 字符的頻率HuffmanNode* left;    // 左子樹HuffmanNode* right;   // 右子樹// 構(gòu)造函數(shù)HuffmanNode(char c, int f) : ch(c), freq(f), left(nullptr), right(nullptr) {}// 定義優(yōu)先級隊列的比較規(guī)則：按頻率最小的優(yōu)先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;// 如果是葉子節(jié)點(diǎn)，保存它的編碼if (!root->left && !root->right) {huffmanCode[root->ch] = str;}// 遍歷左子樹和右子樹generateHuffmanCodes(root->left, str + "0", huffmanCode);generateHuffmanCodes(root->right, str + "1", huffmanCode);
}// 構(gòu)造哈夫曼樹
HuffmanNode* buildHuffmanTree(const unordered_map<char, int>& freq) {// 優(yōu)先隊列（最小堆）用于按頻率排序priority_queue<HuffmanNode*, vector<HuffmanNode*>, HuffmanNode::Compare> minHeap;// 創(chuàng)建葉子節(jié)點(diǎn)并插入最小堆for (const auto& pair : freq) {minHeap.push(new HuffmanNode(pair.first, pair.second));}// 合并節(jié)點(diǎn)直到只剩一個節(jié)點(diǎn)while (minHeap.size() > 1) {// 取出兩個最小的節(jié)點(diǎn)HuffmanNode* left = minHeap.top(); minHeap.pop();HuffmanNode* right = minHeap.top(); minHeap.pop();// 創(chuàng)建一個新的內(nèi)部節(jié)點(diǎn)，頻率為左右節(jié)點(diǎn)頻率之和HuffmanNode* node = new HuffmanNode('\0', left->freq + right->freq);node->left = left;node->right = right;// 將新節(jié)點(diǎn)插入最小堆minHeap.push(node);}// 最后堆中剩下的節(jié)點(diǎn)就是哈夫曼樹的根節(jié)點(diǎn)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";// 統(tǒng)計每個字符的頻率unordered_map<char, int> freq;for (char c : text) {freq[c]++;}// 構(gòu)建哈夫曼樹HuffmanNode* root = buildHuffmanTree(freq);// 保存每個字符的哈夫曼編碼unordered_map<char, string> huffmanCode;// 生成哈夫曼編碼generateHuffmanCodes(root, "", huffmanCode);// 打印哈夫曼編碼printHuffmanCodes(huffmanCode);return 0;
}