用数据结构编写一个哈夫曼树
时间: 2023-09-15 14:19:59 浏览: 44
好的,以下是用C++语言实现哈夫曼树的代码:
```c++
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
// 定义哈夫曼树节点
struct HuffmanNode {
char ch; // 节点存储的字符
int weight; // 节点的权值
HuffmanNode *left, *right; // 节点的左右子节点
HuffmanNode(char ch, int weight) {
this->ch = ch;
this->weight = weight;
left = right = NULL;
}
};
// 定义比较函数,用于优先队列的排序
struct Compare {
bool operator()(const HuffmanNode* a, const HuffmanNode* b) const {
return a->weight > b->weight;
}
};
// 从根节点开始遍历哈夫曼树,生成编码表
void generateCodeTable(HuffmanNode* root, string code, vector<pair<char, string>>& codeTable) {
if (root == NULL) {
return;
}
// 如果是叶子节点,将该节点的字符和编码插入编码表中
if (root->left == NULL && root->right == NULL) {
codeTable.push_back(make_pair(root->ch, code));
}
// 递归遍历左子树
generateCodeTable(root->left, code + "0", codeTable);
// 递归遍历右子树
generateCodeTable(root->right, code + "1", codeTable);
}
int main() {
string s = "hello world";
int freq[256] = {0}; // 存储每个字符出现的频率
// 统计每个字符出现的频率
for (int i = 0; i < s.length(); i++) {
freq[s[i]]++;
}
priority_queue<HuffmanNode*, vector<HuffmanNode*>, Compare> pq;
// 将每个字符作为一个叶子节点插入优先队列
for (int i = 0; i < 256; i++) {
if (freq[i] > 0) {
pq.push(new HuffmanNode(i, freq[i]));
}
}
// 不断取出两个权值最小的节点,合并成一个新节点,插入优先队列
while (pq.size() > 1) {
HuffmanNode* left = pq.top();
pq.pop();
HuffmanNode* right = pq.top();
pq.pop();
HuffmanNode* parent = new HuffmanNode('\0', left->weight + right->weight);
parent->left = left;
parent->right = right;
pq.push(parent);
}
HuffmanNode* root = pq.top(); // 哈夫曼树的根节点
vector<pair<char, string>> codeTable; // 存储字符和对应的编码的表
generateCodeTable(root, "", codeTable);
// 输出每个字符的编码
for (int i = 0; i < codeTable.size(); i++) {
cout << codeTable[i].first << ": " << codeTable[i].second << endl;
}
return 0;
}
```
在上面的代码中,首先统计每个字符出现的频率,然后将每个字符作为一个叶子节点插入优先队列中。接着,不断取出两个权值最小的节点,合并成一个新节点,插入优先队列,直到队列中只剩一个节点,这个节点就是哈夫曼树的根节点。最后,从根节点开始遍历哈夫曼树,生成编码表,然后输出每个字符的编码。
相关推荐
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.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)