构建哈夫曼树求wpl和哈夫曼编码的代码
时间: 2024-04-21 16:03:20 浏览: 12
构建哈夫曼树求wpl和哈夫曼编码的代码,可以使用以下的伪代码:
1. 定义哈夫曼树的节点结构体:
struct huffman_node {
char data; // 字符数据
int weight; // 权值
huffman_node* left; // 左孩子
huffman_node* right; // 右孩子
};
2. 定义哈夫曼树的构建函数:
huffman_node* build_huffman_tree(vector<pair<char, int>>& freq) {
// 将字符和对应的权值放入一个优先队列中
auto cmp = [](const huffman_node* a, const huffman_node* b) { return a->weight > b->weight; };
priority_queue<huffman_node*, vector<huffman_node*>, decltype(cmp)> pq(cmp);
for (auto p : freq) {
huffman_node* node = new huffman_node{ p.first, p.second, nullptr, nullptr };
pq.push(node);
}
// 不断将队列中的两个节点合并,直到只剩下一个根节点
while (pq.size() > 1) {
huffman_node* left = pq.top(); pq.pop();
huffman_node* right = pq.top(); pq.pop();
huffman_node* parent = new huffman_node{ '\0', left->weight + right->weight, left, right };
pq.push(parent);
}
// 返回根节点
return pq.top();
}
3. 定义求哈夫曼树wpl的函数:
int get_wpl(huffman_node* root, int depth = 0) {
if (!root->left && !root->right) { // 叶节点
return root->weight * depth;
}
return get_wpl(root->left, depth + 1) + get_wpl(root->right, depth + 1);
}
4. 定义求哈夫曼编码的函数:
void get_huffman_code(huffman_node* root, string& code, unordered_map<char, string>& map) {
if (!root->left && !root->right) { // 叶节点
map[root->data] = code;
return;
}
if (root->left) {
code.push_back('0');
get_huffman_code(root->left, code, map);
code.pop_back();
}
if (root->right) {
code.push_back('1');
get_huffman_code(root->right, code, map);
code.pop_back();
}
}
使用以上伪代码,可以构建出求哈夫曼树wpl和哈夫曼编码的完整代码。