已知权值集合为{5,7,2,3,6,9},要求给出哈夫曼树,并计算带权路径长度WPL,写出c++算法
时间: 2023-08-19 16:17:07 浏览: 248
首先,哈夫曼树的构建需要用到最小堆,因此我们需要先实现最小堆。
```c++
#include <iostream>
#include <vector>
using namespace std;
template<class T>
class MinHeap {
private:
vector<T> heap;
void shift_up(int idx) {
if (idx == 0) return;
int parent = (idx - 1) / 2;
if (heap[parent] > heap[idx]) {
swap(heap[parent], heap[idx]);
shift_up(parent);
}
}
void shift_down(int idx) {
int left = idx * 2 + 1;
int right = idx * 2 + 2;
int smallest = idx;
if (left < heap.size() && heap[left] < heap[smallest]) {
smallest = left;
}
if (right < heap.size() && heap[right] < heap[smallest]) {
smallest = right;
}
if (smallest != idx) {
swap(heap[idx], heap[smallest]);
shift_down(smallest);
}
}
public:
void push(T val) {
heap.push_back(val);
shift_up(heap.size() - 1);
}
void pop() {
if (heap.empty()) return;
heap[0] = heap.back();
heap.pop_back();
shift_down(0);
}
T top() {
return heap.front();
}
bool empty() {
return heap.empty();
}
};
```
接下来,我们可以使用最小堆来构建哈夫曼树。对于给定的权值集合,我们可以将它们放入最小堆中,并不断地取出最小的两个权值进行合并,直到堆中只剩下一个节点为止。
```c++
#include <iostream>
#include <vector>
using namespace std;
template<class T>
class TreeNode {
public:
T val;
TreeNode<T> *left;
TreeNode<T> *right;
TreeNode(T val) : val(val), left(nullptr), right(nullptr) {}
};
template<class T>
TreeNode<T> *build_huffman_tree(vector<T> weights) {
MinHeap<TreeNode<T> *> heap;
for (auto weight : weights) {
heap.push(new TreeNode<T>(weight));
}
while (!heap.empty()) {
TreeNode<T> *left = heap.top();
heap.pop();
if (heap.empty()) {
return left;
}
TreeNode<T> *right = heap.top();
heap.pop();
TreeNode<T> *parent = new TreeNode<T>(left->val + right->val);
parent->left = left;
parent->right = right;
heap.push(parent);
}
return nullptr;
}
```
最后,我们可以计算哈夫曼树的带权路径长度,即将每个叶子节点的权值乘以到根节点的距离,再将所有叶子节点的带权路径长度相加得到的值。可以使用递归来实现。
```c++
template<class T>
int calc_wpl(TreeNode<T> *root, int depth = 0) {
if (!root->left && !root->right) {
return root->val * depth;
}
return calc_wpl(root->left, depth + 1) + calc_wpl(root->right, depth + 1);
}
```
完整的c++代码如下:
阅读全文