构造一棵哈夫曼树,其中单词A出现频度9,单词B出现频度5,单词C出现频度3,单词D出现频度7,单词E出现频度6,单词F出现频度2,单词G出现频度1,单词H出现频度1,并输出对应的哈夫曼编码,代码c++
时间: 2023-08-21 20:06:24 浏览: 92
好的,我来解答你的问题。
首先,我们可以将每个单词及其对应的出现频率存储在一个结构体中:
```c++
struct Node {
char word; // 单词
int freq; // 出现频率
Node *left; // 左子节点
Node *right; // 右子节点
};
```
然后,我们可以使用一个优先队列(最小堆)来存储这些结构体,并按照出现频率从小到大排序:
```c++
struct cmp {
bool operator() (Node *a, Node *b) {
return a->freq > b->freq;
}
};
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});
```
接下来,我们可以使用贪心算法来构建哈夫曼树。每次从优先队列中取出两个出现频率最小的节点,合并成一个新的节点,其出现频率为两个节点出现频率之和,并将新的节点重新加入优先队列中。重复这个过程,直到队列中只剩下一个节点,即为哈夫曼树的根节点:
```c++
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)来遍历哈夫曼树,并输出每个单词的哈夫曼编码。在遍历过程中,我们可以使用一个字符串来记录当前节点的哈夫曼编码,并将该字符串传递给左右子节点,分别在其基础上添加'0'或'1',直到遍历到叶子节点,即为该单词的哈夫曼编码:
```c++
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");
}
dfs(root, "");
```
完整代码如下:
阅读全文