数据结构构造哈夫曼树c++
时间: 2023-07-08 18:50:52 浏览: 140
哈夫曼树是一种特殊的二叉树,它的叶子节点对应着要编码的字符,而非叶子节点则对应着编码。哈夫曼树的构建过程是基于贪心策略的,即每次选取出现频率最小的两个节点,将它们合并成一个新节点,直到最后形成一棵哈夫曼树。以下是一个 C++ 的实现:
```c++
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
// 定义哈夫曼树节点结构体
struct TreeNode {
char data; // 节点存储的字符
int freq; // 节点对应字符出现的频率
TreeNode* left; // 左子节点
TreeNode* right; // 右子节点
TreeNode(char data, int freq) : data(data), freq(freq), left(nullptr), right(nullptr) {}
};
// 定义比较函数,用于优先队列的排序
struct cmp {
bool operator()(TreeNode* a, TreeNode* b) {
return a->freq > b->freq; // 频率小的节点优先级高
}
};
// 构建哈夫曼树的函数
TreeNode* buildHuffmanTree(vector<char>& chars, vector<int>& freqs) {
priority_queue<TreeNode*, vector<TreeNode*>, cmp> pq; // 定义优先队列
for (int i = 0; i < chars.size(); i++) {
TreeNode* node = new TreeNode(chars[i], freqs[i]); // 创建节点,存储字符和频率
pq.push(node); // 将节点加入到优先队列中
}
while (pq.size() > 1) { // 只要队列中还有两个及以上的节点
TreeNode* left = pq.top(); // 取出频率最小的节点
pq.pop();
TreeNode* right = pq.top(); // 取出频率次小的节点
pq.pop();
TreeNode* parent = new TreeNode('$', left->freq + right->freq); // 新建一个父节点
parent->left = left; // 将左子节点挂到父节点下面
parent->right = right; // 将右子节点挂到父节点下面
pq.push(parent); // 将新建的父节点加入到队列中
}
return pq.top(); // 队列中最后剩下的节点即为根节点
}
// 递归打印哈夫曼树的编码
void printHuffmanCode(TreeNode* root, string code) {
if (!root) return; // 递归结束条件
if (root->data != '$') { // 如果是叶子节点,输出对应字符和编码
cout << root->data << " " << code << endl;
}
printHuffmanCode(root->left, code + "0"); // 递归处理左子树
printHuffmanCode(root->right, code + "1"); // 递归处理右子树
}
int main() {
vector<char> chars = {'a', 'b', 'c', 'd', 'e', 'f'};
vector<int> freqs = {5, 9, 12, 13, 16, 45};
TreeNode* root = buildHuffmanTree(chars, freqs);
printHuffmanCode(root, "");
return 0;
}
```
输出结果:
```
f 0
c 100
d 101
a 1100
b 1101
e 111
```
以上代码中,`buildHuffmanTree` 函数用于构建哈夫曼树,它使用了优先队列(堆)来维护频率最小的两个节点,不断合并成为新的节点,直到最后形成一棵哈夫曼树。`printHuffmanCode` 函数用于递归打印哈夫曼树的编码,其中传入的 `code` 参数表示当前节点的编码。
阅读全文