用数据结构编写一个哈夫曼树
时间: 2023-09-16 11:11:23 浏览: 47
以下是用 C++ 实现的哈夫曼树:
```cpp
#include <iostream>
#include <queue>
using namespace std;
// 定义哈夫曼树节点结构体
struct HuffmanNode {
int weight;
char ch;
HuffmanNode *left;
HuffmanNode *right;
HuffmanNode(int w, char c) : weight(w), ch(c), left(nullptr), right(nullptr) {}
};
// 定义比较器用于优先队列排序
struct Compare {
bool operator() (HuffmanNode *a, HuffmanNode *b) {
return a->weight > b->weight;
}
};
// 哈夫曼树构建函数
HuffmanNode* buildHuffmanTree(priority_queue<HuffmanNode*, vector<HuffmanNode*>, Compare> pq) {
while (pq.size() > 1) {
HuffmanNode *node1 = pq.top();
pq.pop();
HuffmanNode *node2 = pq.top();
pq.pop();
HuffmanNode *newNode = new HuffmanNode(node1->weight + node2->weight, '\0');
newNode->left = node1;
newNode->right = node2;
pq.push(newNode);
}
return pq.top();
}
// 哈夫曼编码函数
void encode(HuffmanNode *root, string code, unordered_map<char, string> &codeMap) {
if (!root) return;
if (root->ch != '\0') {
codeMap[root->ch] = code;
}
encode(root->left, code + "0", codeMap);
encode(root->right, code + "1", codeMap);
}
int main() {
string s = "hello world";
unordered_map<char, int> freqMap;
for (char c : s) {
freqMap[c]++;
}
priority_queue<HuffmanNode*, vector<HuffmanNode*>, Compare> pq;
for (auto pair : freqMap) {
HuffmanNode *node = new HuffmanNode(pair.second, pair.first);
pq.push(node);
}
HuffmanNode *root = buildHuffmanTree(pq);
unordered_map<char, string> codeMap;
encode(root, "", codeMap);
for (auto pair : codeMap) {
cout << pair.first << " : " << pair.second << endl;
}
return 0;
}
```
这个程序首先统计输入字符串里每个字符的频率,然后用哈夫曼树构建函数 `buildHuffmanTree` 构建哈夫曼树,最后用哈夫曼编码函数 `encode` 计算每个字符的编码。最终输出每个字符对应的编码。