创建一棵Huffman树并输出其字母的Huffman编码。
时间: 2024-06-14 22:06:30 浏览: 28
要创建一棵Huffman树并输出其字母的Huffman编码,可以按照以下步骤进行:
1. 统计每个字母在文本中出现的频率。
2. 根据频率构建一个最小堆(或优先队列),将每个字母作为一个节点插入堆中,节点的权重为对应字母的频率。
3. 从堆中取出两个权重最小的节点,合并它们成为一个新的节点,新节点的权重为两个子节点的权重之和。将新节点插入堆中。
4. 重复步骤3,直到堆中只剩下一个节点,这个节点就是Huffman树的根节点。
5. 遍历Huffman树,给每个字母分配一个唯一的Huffman编码。从根节点开始,向左走为0,向右走为1,直到叶子节点。记录下每个字母对应的编码。
6. 输出每个字母及其对应的Huffman编码。
下面是一个示例代码:
```cpp
#include <iostream>
#include <queue>
#include <unordered_map>
using namespace std;
// Huffman树节点
struct Node {
char data; // 字母
int freq; // 频率
Node* left;
Node* right;
Node(char data, int freq) : data(data), freq(freq), left(nullptr), right(nullptr) {}
};
// 用于比较节点频率的函数对象
struct Compare {
bool operator()(Node* a, Node* b) {
return a->freq > b->freq;
}
};
// 构建Huffman树
Node* buildHuffmanTree(const unordered_map<char, int>& freqMap) {
priority_queue<Node*, vector<Node*>, Compare> minHeap;
for (const auto& pair : freqMap) {
minHeap.push(new Node(pair.first, pair.second));
}
while (minHeap.size() > 1) {
Node* left = minHeap.top();
minHeap.pop();
Node* right = minHeap.top();
minHeap.pop();
Node* parent = new Node('\0', left->freq + right->freq);
parent->left = left;
parent->right = right;
minHeap.push(parent);
}
return minHeap.top();
}
// 递归遍历Huffman树,生成编码
void generateHuffmanCode(Node* root, string code, unordered_map<char, string>& huffmanCodeMap) {
if (root == nullptr) {
return;
}
if (root->left == nullptr && root->right == nullptr) {
huffmanCodeMap[root->data] = code;
}
generateHuffmanCode(root->left, code + "0", huffmanCodeMap);
generateHuffmanCode(root->right, code + "1", huffmanCodeMap);
}
// 输出Huffman编码
void printHuffmanCode(const unordered_map<char, string>& huffmanCodeMap) {
for (const auto& pair : huffmanCodeMap) {
cout << pair.first << ": " << pair.second << endl;
}
}
int main() {
string text = "hello world";
unordered_map<char, int> freqMap;
for (char c : text) {
freqMap[c]++;
}
Node* root = buildHuffmanTree(freqMap);
unordered_map<char, string> huffmanCodeMap;
generateHuffmanCode(root, "", huffmanCodeMap);
printHuffmanCode(huffmanCodeMap);
return 0;
}
```
这段代码会输出每个字母及其对应的Huffman编码。在这个示例中,输入的文本是"hello world",输出结果如下:
```
h: 00
e: 10
l: 110
o: 111
w: 0100
r: 0101
d: 011
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_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)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![java](https://img-home.csdnimg.cn/images/20210720083646.png)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)