请用C++实现输入HuffmanTree的参考标准底稿
时间: 2023-06-13 07:08:19 浏览: 106
用C++实现霍夫曼树编码
5星 · 资源好评率100%
下面是一个简单的参考标准底稿,可以用C++实现输入HuffmanTree:
```cpp
#include <iostream>
#include <queue>
using namespace std;
struct TreeNode {
char data;
int weight;
TreeNode* left;
TreeNode* right;
TreeNode(char d, int w) : data(d), weight(w), left(NULL), right(NULL) {}
};
struct cmp {
bool operator()(TreeNode* a, TreeNode* b) {
return a->weight > b->weight;
}
};
TreeNode* createHuffmanTree(priority_queue<TreeNode*, vector<TreeNode*>, cmp>& pq) {
while (pq.size() > 1) {
TreeNode* left = pq.top(); pq.pop();
TreeNode* right = pq.top(); pq.pop();
int sum = left->weight + right->weight;
TreeNode* parent = new TreeNode('\0', sum);
parent->left = left;
parent->right = right;
pq.push(parent);
}
return pq.top();
}
int main() {
int n;
cin >> n;
priority_queue<TreeNode*, vector<TreeNode*>, cmp> pq;
for (int i = 0; i < n; i++) {
char c;
int w;
cin >> c >> w;
pq.push(new TreeNode(c, w));
}
TreeNode* root = createHuffmanTree(pq);
// do something with the Huffman tree
return 0;
}
```
其中,`TreeNode` 结构体表示一个节点,`cmp` 结构体是一个比较器,用于优先队列的排序。`createHuffmanTree` 函数用于构建Huffman树,输入一个优先队列,输出一个根节点。`main` 函数中首先输入叶子节点的个数 `n`,然后逐个输入每个叶子节点的字符和权重,将它们放入优先队列中,最后调用 `createHuffmanTree` 函数构建Huffman树,并可以对树进行后续操作。
阅读全文