哈夫曼树码输出功能函数
时间: 2023-12-16 22:03:12 浏览: 32
下面是一个使用C++语言实现的哈夫曼树码输出功能函数,可以输出哈夫曼树中每个字符的编码。
```C++
#include <iostream>
#include <unordered_map>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
struct Node {
char ch;
int freq;
Node* left;
Node* right;
Node(char ch, int freq) : ch(ch), freq(freq), left(nullptr), right(nullptr) {}
};
void get_codes(Node* root, string code, unordered_map<char, string>& codes) {
if (root == nullptr) {
return;
}
if (root->left == nullptr && root->right == nullptr) {
codes[root->ch] = code;
}
get_codes(root->left, code + "0", codes);
get_codes(root->right, code + "1", codes);
}
void huffman_codes(unordered_map<char, int>& freq_map) {
vector<Node*> nodes;
for (const auto& it : freq_map) {
nodes.push_back(new Node(it.first, it.second));
}
while (nodes.size() > 1) {
sort(nodes.begin(), nodes.end(), [](Node* a, Node* b) {
return a->freq > b->freq;
});
Node* left = nodes.back();
nodes.pop_back();
Node* right = nodes.back();
nodes.pop_back();
Node* parent = new Node('\0', left->freq + right->freq);
parent->left = left;
parent->right = right;
nodes.push_back(parent);
}
unordered_map<char, string> codes;
Node* root = nodes.front();
get_codes(root, "", codes);
for (const auto& it : freq_map) {
cout << "Character: " << it.first << " Code: " << codes[it.first] << endl;
}
}
int main() {
unordered_map<char, int> freq_map;
string s = "Hello, World!";
for (char c : s) {
freq_map[c]++;
}
huffman_codes(freq_map);
return 0;
}
```
上述代码中,`get_codes`函数是用来递归遍历哈夫曼树并获取编码的函数,`huffman_codes`函数则是用来构建哈夫曼树并输出每个字符的编码的函数。在主函数中,我们使用一个字符串来计算每个字符的出现频率,并将该频率映射保存在`freq_map`中。然后调用`huffman_codes`函数来获取哈夫曼编码并输出每个字符的编码。
相关推荐
![txt](https://img-home.csdnimg.cn/images/20210720083642.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)