优先级队列实现哈夫曼树的编码和译码

//优先级队列实现的哈夫曼树的编码和译码   

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

作者：阿凡卢

出处：http://www.cnblogs.com/luxiaoxun/

本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。

http://www.cnblogs.com/luxiaoxun/archive/2012/08/04/2622626.html