優先キューはハフマンツリーの符号化と復号化を実現する

// 

#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;  
}