//优先级队列实现的哈夫曼树的编码和译码   
  
#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;    
}