哈夫曼树c++
时间: 2023-07-01 20:21:50 浏览: 74
下面是一个简单的 C++ 实现哈夫曼树的代码:
```c++
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
struct Node {
char data;
int freq;
Node *left, *right;
Node(char c, int f) : data(c), freq(f), left(NULL), right(NULL) {}
};
struct NodeCmp {
bool operator()(Node* n1, Node* n2) const {
return n1->freq > n2->freq;
}
};
void printCode(Node* root, string code) {
if (root == NULL) {
return;
}
if (root->data != '#') {
cout << root->data << " : " << code << endl;
}
printCode(root->left, code + "0");
printCode(root->right, code + "1");
}
void buildHuffmanTree(string str) {
vector<int> freq(26, 0);
for (int i = 0; i < str.length(); i++) {
freq[str[i] - 'a']++;
}
priority_queue<Node*, vector<Node*>, NodeCmp> pq;
for (int i = 0; i < 26; i++) {
if (freq[i] > 0) {
pq.push(new Node('a' + i, freq[i]));
}
}
while (pq.size() > 1) {
Node* n1 = pq.top();
pq.pop();
Node* n2 = pq.top();
pq.pop();
Node* n = new Node('#', n1->freq + n2->freq);
n->left = n1;
n->right = n2;
pq.push(n);
}
Node* root = pq.top();
pq.pop();
printCode(root, "");
}
int main() {
string str = "hello world";
buildHuffmanTree(str);
return 0;
}
```
代码中定义了 `Node` 结构体表示哈夫曼树的节点,使用优先队列 `pq` 存储节点并按照频率升序排序,使用 `buildHuffmanTree` 函数构建哈夫曼树,并使用 `printCode` 函数输出每个字符的编码。