生成哈夫曼树的c++代码
时间: 2023-08-07 17:57:19 浏览: 55
以下是一个简单的C++代码示例,用于生成哈夫曼树:
```cpp
#include <iostream>
#include <queue>
using namespace std;
// 哈夫曼树节点
struct HuffmanNode {
char data;
int frequency;
HuffmanNode* left;
HuffmanNode* right;
HuffmanNode(char data, int frequency) {
this->data = data;
this->frequency = frequency;
left = nullptr;
right = nullptr;
}
};
// 用于比较节点频率的函数对象
struct Compare {
bool operator()(HuffmanNode* a, HuffmanNode* b) {
return a->frequency > b->frequency;
}
};
// 构建哈夫曼树
HuffmanNode* buildHuffmanTree(priority_queue<HuffmanNode*, vector<HuffmanNode*>, Compare>& pq) {
while (pq.size() > 1) {
HuffmanNode* left = pq.top();
pq.pop();
HuffmanNode* right = pq.top();
pq.pop();
// 创建一个新节点作为父节点
HuffmanNode* parent = new HuffmanNode('$', left->frequency + right->frequency);
parent->left = left;
parent->right = right;
pq.push(parent);
}
return pq.top();
}
// 打印哈夫曼编码
void printHuffmanCodes(HuffmanNode* root, string code) {
if (root == nullptr) {
return;
}
if (root->data != '$') { // 叶子节点
cout << root->data << ": " << code << endl;
}
printHuffmanCodes(root->left, code + "0");
printHuffmanCodes(root->right, code + "1");
}
int main() {
string text = "Hello, World!";
int frequency[256] = {0};
// 统计字符频率
for (char c : text) {
frequency[c]++;
}
// 构建优先队列,按照频率排序
priority_queue<HuffmanNode*, vector<HuffmanNode*>, Compare> pq;
for (int i = 0; i < 256; i++) {
if (frequency[i] > 0) {
HuffmanNode* node = new HuffmanNode(static_cast<char>(i), frequency[i]);
pq.push(node);
}
}
// 构建哈夫曼树
HuffmanNode* root = buildHuffmanTree(pq);
// 打印哈夫曼编码
printHuffmanCodes(root, "");
return 0;
}
```
上述代码中,首先统计了给定文本中字符的频率。然后,使用优先队列来构建哈夫曼树,每次从队列中取出两个频率最低的节点,并创建一个新的父节点连接它们。最后,通过递归遍历哈夫曼树,生成每个字符的哈夫曼编码并进行打印输出。
请注意,以上只是一个简单的示例,并没有处理特殊字符或文件输入输出。在实际应用中,可能需要进行相关的扩展和修改。