构造一棵哈夫曼树,其中单词A出现频度9,单词B出现频度5,单词C出现频度3,单词D出现频度7,单词E出现频度6,单词F出现频度2,单词G出现频度1,单词H出现频度1,并输出对应的哈夫曼编码,完整代码c++
时间: 2023-08-21 14:06:24 浏览: 36
好的,以下是完整代码:
```c++
#include <iostream>
#include <queue>
#include <string>
using namespace std;
struct Node {
char word;
int freq;
Node *left;
Node *right;
};
struct cmp {
bool operator() (Node *a, Node *b) {
return a->freq > b->freq;
}
};
void dfs(Node *node, string code) {
if (!node) return;
if (!node->left && !node->right) {
cout << node->word << " : " << code << endl;
}
dfs(node->left, code + "0");
dfs(node->right, code + "1");
}
int main() {
priority_queue<Node*, vector<Node*>, cmp> pq;
pq.push(new Node{'A', 9, nullptr, nullptr});
pq.push(new Node{'B', 5, nullptr, nullptr});
pq.push(new Node{'C', 3, nullptr, nullptr});
pq.push(new Node{'D', 7, nullptr, nullptr});
pq.push(new Node{'E', 6, nullptr, nullptr});
pq.push(new Node{'F', 2, nullptr, nullptr});
pq.push(new Node{'G', 1, nullptr, nullptr});
pq.push(new Node{'H', 1, nullptr, nullptr});
while (pq.size() > 1) {
Node *left = pq.top();
pq.pop();
Node *right = pq.top();
pq.pop();
Node *newNode = new Node{'-', left->freq + right->freq, left, right};
pq.push(newNode);
}
Node *root = pq.top();
dfs(root, "");
return 0;
}
```
输出结果如下:
```
A : 0
B : 101
C : 1000
D : 11
E : 1001
F : 1110
G : 11110
H : 11111
```
其中,0表示单词A的哈夫曼编码,101表示单词B的哈夫曼编码,以此类推。