用c++语言构造一个哈夫曼树
时间: 2023-08-10 08:32:36 浏览: 39
以下是用C++语言实现构造哈夫曼树的示例代码:
```cpp
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
struct Node {
int val;
Node* left;
Node* right;
Node(int v) : val(v), left(nullptr), right(nullptr) {}
Node(int v, Node* l, Node* r) : val(v), left(l), right(r) {}
};
struct Compare {
bool operator() (Node* a, Node* b) {
return a->val > b->val;
}
};
Node* constructHuffmanTree(vector<int>& weights) {
priority_queue<Node*, vector<Node*>, Compare> pq;
for (int w : weights) {
pq.push(new Node(w));
}
while (pq.size() > 1) {
Node* left = pq.top();
pq.pop();
Node* right = pq.top();
pq.pop();
int sum = left->val + right->val;
pq.push(new Node(sum, left, right));
}
return pq.top();
}
void printHuffmanTree(Node* root, string prefix = "") {
if (root == nullptr) {
return;
}
if (root->left == nullptr && root->right == nullptr) {
cout << prefix << " " << root->val << endl;
}
printHuffmanTree(root->left, prefix + "0");
printHuffmanTree(root->right, prefix + "1");
}
int main() {
vector<int> weights = {5, 9, 12, 13, 16, 45};
Node* root = constructHuffmanTree(weights);
printHuffmanTree(root);
return 0;
}
```
在这个示例程序中,我们使用了一个优先队列来保存每个权值对应的节点,每次从队列中取出权值最小的两个节点,构造新的父节点,并将其加入队列中。最后队列中只剩下一个节点,即为哈夫曼树的根节点。我们还实现了一个函数 `printHuffmanTree`,用于打印哈夫曼树的编码。