- 基本思路
(1)unordered_map统计每个字符出现的个数
(2)将所有的节点放到一个优先队列中,用一个节点替换两个频率最低的节点,新节点的频率就是这两个节点的频率之和。这样,新节点就是两个被替换节点的父节点了。
(3)如此循环,直到队列中只剩一个节点(树根)。
//定义哈夫曼树的节点 struct Node{ char key; //代表的值 int freq; //出现的频率 Node* left; Node* right; //既然是树中的节点,左右子节点 Node(int k='\0',int f=0):key(k),freq(f),left(NULL),right(NULL){} //默认构造函数 }; //用到优先队列的话,根据freq从小到大排序,但是pq中定义的应该是相反的,a.freq>b.freq struct cmp{ bool operator()(const Node *a,const Node *b){ return a->freq > b->freq; } }; Node* huffman(unordered_map<char>& mymap){ //总共多少个点先统计 int n=mymap.size(); //先来构建顶点 priority_queue<node>,cmp> pq; //一个优先队列 for(auto it=mymap.begin();it!=mymap.end();it++){ //生成节点,插入优先队列中 Node* cur=new Node(); //生成节点 cur->freq=it->second; cur->key=it->first; pq.push(cur); //进队列 } //直到最后剩下的一个就是root while(pq.size()>1){ auto sub1=pq.top(); pq.pop(); auto sub2=pq.top(); pq.pop(); //取两个进行合并后放回去 Node* cur=new Node(); cur->freq=sub1->freq+sub2->freq; //当前节点的freq为两者之和 cur->left=sub1; cur->right=sub2; //两个节点分别作为当前的左右子节点进行相连 pq.push(cur); //将当前的节点放回去 } //最终剩下的就是root return pq.top(); } //考虑LDR进行遍历,打印叶子节点的信息 void print_leaf(Node* root,string s){ if(!root){ //遍历到空 return; } if(!root->left && !root->right){ //如果是叶子节点了,打印信息 cout<<"current leaf is: "<key<<"-----"; //输出编码值 cout<<"the code is: "<<<endl>left,s+"0"); //左边标记0 print_leaf(root->right,s+"1"); //右边标记1 } int main(){ //string s; //cin>>s; //输入的字符串 unordered_map<char> mymap; //统计每个字符出现的个数 //for(auto ch:s){ // mymap[ch]++; //} mymap['a']=45; mymap['b']=13; mymap['c']=12; mymap['d']=16; mymap['e']=9; mymap['f']=5; //进行霍夫曼编码 Node* root=huffman(mymap); //左0右1进行打印编码,每一个输入的所需都应该在叶子节点上,考虑LDR输出 string res=""; print_leaf(root,res); system("pause"); return 0; }
- 运行结果如下所示:
而题中如果要求长度,可以考虑记录每个节点的标记是多少,最终来累加长度