Huffman树建立与中序遍历数据结构实验以c➕➕语言为例
时间: 2024-02-27 14:51:24 浏览: 29
好的,下面是Huffman树建立与中序遍历的C++代码示例:
```c++
#include <iostream>
#include <queue>
using namespace std;
struct Node {
char ch; // 字符
int freq; // 频率
Node* left;
Node* right;
Node(char c, int f, Node* l = nullptr, Node* r = nullptr) : ch(c), freq(f), left(l), right(r) {}
};
// 定义比较器
struct cmp {
bool operator()(Node* a, Node* b) {
return a->freq > b->freq;
}
};
// 构建Huffman树
Node* buildHuffmanTree(string str) {
// 统计字符频率
int freq[128] = {0};
for (char c : str) {
freq[c]++;
}
// 构建小根堆
priority_queue<Node*, vector<Node*>, cmp> pq;
for (int i = 0; i < 128; i++) {
if (freq[i] > 0) {
pq.push(new Node(i, freq[i]));
}
}
// 构建Huffman树
while (pq.size() > 1) {
Node* left = pq.top();
pq.pop();
Node* right = pq.top();
pq.pop();
Node* parent = new Node('\0', left->freq + right->freq, left, right);
pq.push(parent);
}
return pq.top();
}
// 中序遍历Huffman树
void inorderTraversal(Node* root) {
if (root == nullptr) {
return;
}
inorderTraversal(root->left);
cout << root->ch << ":" << root->freq << " ";
inorderTraversal(root->right);
}
int main() {
string str = "abacdbdcefb";
Node* root = buildHuffmanTree(str);
inorderTraversal(root);
return 0;
}
```
这段代码实现了Huffman树的构建,并且输出了Huffman树的中序遍历结果,即按照字符的字典序输出每个节点的字符和频率。