代码语言：javascript复制
#include<bits/stdc .h>
using namespace std;
struct Node {
char data;
int freq;
Node *lChild, *rChild;
Node(char data, int freq) : data(data), freq(freq) {
lChild = rChild = NULL;
}
};
// 仿函数，给极小化堆用
struct cmp {
bool operator() (const Node* a, const Node* b){
return a->freq > b->freq;
}
};
void print(Node* root, string str) {
if(root == NULL) return;
if(root->data != '#') // 有数据才打印
cout<<root->data<<": "<<str<<endl;
// 左0右1
print(root->lChild, str '0');
print(root->rChild, str '1');
}
void Huffman(char* data, int* freq, int n) {
priority_queue<Node*, vector<Node*>, cmp> pq; // 建立极小化堆
for(int i = 0; i < n; i )
pq.push(new Node(data[i], freq[i])); // 把指针存进去
while(pq.size() > 1) {
// 取最小的两个
Node* left = pq.top(); pq.pop();
Node* right = pq.top(); pq.pop();
// 合并为一个，权重相加，‘#’作为一个标志，非叶节点，无数据
Node* top = new Node('#', left->freq right->freq);
top->lChild = left;
top->rChild = right;
// 再投入堆中
pq.push(top);
}
print(pq.top(), "");
}
int main() {
cout<<"请输入字符个数"<<endl;
int n; cin>>n;
char* data = new char[n 5];
int* freq = new int[n 5];
for(int i = 0; i < n; i ) {
cout<<"请输入字符及对应的权重："<<endl;
cin>>data[i]>>freq[i];
}
Huffman(data, freq, n);
delete(data);
delete(freq);
return 0;
}
