给定权值构造哈夫曼树的代码
时间: 2023-06-28 12:05:41 浏览: 46
以下是构造哈夫曼树的代码,假设已经有一个权值数组weights,长度为n,以及一个结构体Node表示哈夫曼树的节点:
```c++
#include <queue>
using namespace std;
// 定义哈夫曼树节点结构体
struct Node {
int weight; // 权值
Node* left; // 左儿子指针
Node* right; // 右儿子指针
Node(int w=0, Node* l=NULL, Node* r=NULL) : weight(w), left(l), right(r) {}
};
// 定义比较器,用于优先队列排序
struct cmp {
bool operator()(Node* a, Node* b) {
return a->weight > b->weight;
}
};
// 构造哈夫曼树
Node* buildHuffmanTree(int* weights, int n) {
priority_queue<Node*, vector<Node*>, cmp> pq; // 定义优先队列
for (int i = 0; i < n; i++) {
pq.push(new Node(weights[i])); // 将所有节点插入优先队列中
}
while (pq.size() > 1) {
Node* left = pq.top(); // 取出权值最小的节点作为左儿子
pq.pop();
Node* right = pq.top(); // 取出权值次小的节点作为右儿子
pq.pop();
Node* parent = new Node(left->weight + right->weight, left, right); // 创建新节点
pq.push(parent); // 将新节点插入优先队列中
}
return pq.top(); // 返回根节点
}
```
使用示例:
```c++
int weights[5] = {5, 2, 4, 7, 1};
Node* root = buildHuffmanTree(weights, 5);
```
上面的代码将会构造出如下的哈夫曼树:
```
19
/ \
7 12
/ \ / \
3 4 5 7
```