//優(yōu)先級隊列實現(xiàn)的哈夫曼樹的編碼和譯碼   
  
#include<iostream>      
#include<queue>      
#include<string>      
using namespace std;    class Node     
{    
public:    float weight;    Node* left;    Node* right;    char ch;    Node(float w,Node* l=NULL,Node* r=NULL,char c=' '):weight(w),ch(c),left(l),right(r) {}    Node(float w,char c=' '):weight(w),ch(c),left(NULL),right(NULL) {}    
};    class cmp    
{    
public :    bool operator()(Node* a,Node* b)    {    return a->weight>b->weight;    }    
};  vector<int> v;     
void Encode(Node* r)//打印字符的編碼       
{     if(r->left==NULL && r->right==NULL)     {     cout << r->ch <<": ";     for (int i = 0;i<v.size();++i)     cout << v[i];     cout << endl;     v.pop_back();     return ;     }     if(r->left)     {     v.push_back(0);     Encode(r->left);     }     if(r->right)     {     v.push_back(1);     Encode(r->right);     }    if(!v.empty())    {    v.pop_back();    }    
}    void Decode(Node* root, string s)//譯碼       
{    Node* p=root;    for(int i=0;i<s.length();++i)    {    if(s[i]=='0')     {    if(p->left) p=p->left;    else     {    cout<<s<<" Can't decode!"<<endl;    return ;    }    }     if(s[i]=='1')     {     if(p->right) p=p->right;    else     {    cout<<s<<" Can't decode!"<<endl;     return ;    }    }    }    cout<<s<<": "<<p->ch<<endl;    
}    void freeTree(Node* p)//銷毀哈夫曼樹      
{    if(p->left!=NULL)    freeTree(p->left);    if(p->right!=NULL)    freeTree(p->right);    delete p;    p=NULL;    
}    int main()    
{    Node* m1,*m2;    char ch[]={'A','C','E','D','F','G'};//字符       float f[]={0.1,0.3,0.4,0.5,0.2,0.6};//頻率       
  priority_queue<Node*,vector<Node*>,cmp> q;    int n=sizeof(ch)/sizeof(ch[0]);    for(int i=0;i<n;++i)    {    q.push(new Node(f[i],ch[i]));    cout<<ch[i]<<": "<<f[i]<<'\t';     }    cout<<endl;    for(int i=1;i<n;++i)    {    m1=q.top(); q.pop();    m2=q.top(); q.pop();    float w=m1->weight+m2->weight;    q.push(new Node(w,m1,m2));    }    Node* root=q.top();    Encode(root);    cout<<endl;    Decode(root,"1011");    freeTree(root);    return 0;    
}  

?

轉(zhuǎn)載于:https://www.cnblogs.com/luxiaoxun/archive/2012/08/04/2622626.html

總結(jié)

以上是生活随笔為你收集整理的优先级队列实现哈夫曼树的编码和译码的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。