c++构造哈夫曼树源代码
时间: 2023-07-08 12:50:52 浏览: 32
以下是一个简单的 C++ 实现,您可以参考:
```c++
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
struct Node {
char data; // 字符
int freq; // 出现频率
Node* left;
Node* right;
Node(char data, int freq) : data(data), freq(freq), left(nullptr), right(nullptr) {}
};
struct cmp {
bool operator()(Node* a, Node* b) {
return a->freq > b->freq;
}
};
Node* buildHuffmanTree(vector<char>& chars, vector<int>& freqs) {
priority_queue<Node*, vector<Node*>, cmp> pq;
for (int i = 0; i < chars.size(); i++) {
Node* node = new Node(chars[i], freqs[i]);
pq.push(node);
}
while (pq.size() > 1) {
Node* left = pq.top();
pq.pop();
Node* right = pq.top();
pq.pop();
Node* parent = new Node('$', left->freq + right->freq);
parent->left = left;
parent->right = right;
pq.push(parent);
}
return pq.top();
}
void printHuffmanCode(Node* root, string code) {
if (!root) return;
if (root->data != '$') {
cout << root->data << " " << code << endl;
}
printHuffmanCode(root->left, code + "0");
printHuffmanCode(root->right, code + "1");
}
int main() {
vector<char> chars = {'a', 'b', 'c', 'd', 'e', 'f'};
vector<int> freqs = {5, 9, 12, 13, 16, 45};
Node* root = buildHuffmanTree(chars, freqs);
printHuffmanCode(root, "");
return 0;
}
```
输出:
```
f 0
c 100
d 101
a 1100
b 1101
e 111
```
注:这里的哈夫曼编码是按照左子树为 0,右子树为 1 的方式构建的。实现中使用优先队列(堆)来维护出现频率最小的两个节点,从而不断构建哈夫曼树。