霍夫曼編碼（Huffman Coding）是一種編碼方式，是一種用于無損數據壓縮的熵編碼（權編碼）算法。1952年，David A. Huffman在麻省理工攻讀博士時所發明的，并發表于《一種構建極小多余編碼的方法》（A Method for the Construction of Minimum-Redundancy Codes）一文。
在計算機數據處理中，霍夫曼編碼使用變長編碼表對源符號（如文件中的一個字母） 進行編碼，其中變長編碼表是通過一種評估來源符號出現機率的方法得到的，出現機率高的字母使用較短的編碼，反之出現機率低的則使用較長的編碼，這便使編碼 之后的字符串的平均長度、期望值降低，從而達到無損壓縮數據的目的。( http://zh.wikipedia.org/wiki/Huffman%E7%B7%A8%E7%A2%BC)

#include<iostream>

include<string>
include<queue>
using namespace std;
class node{
     public:
        node(string con, float wht, node left, node right, string co ){
            content=con;
            weight=wht;
            leftchild=left;
            rightchild=right;
            code=co;
            }
        string content;
        float weight;
        node leftchild;
        node rightchild;
        string code;
     };
void insertion_sort(node array, int low, int high){
    for(int i=low+1;i<high;i++){
        node tem=array[i];
        int j=i-1;
        while(array[j]->weight>tem->weight&&j>=low){
            array[j+1]=array[j];
            j--;
            }
        array[j+1]=tem;
        }
    }
void create_huffman_tree(string s, float* w,int n,node array){
    for(int i=0;i<n;i++){
        array[i]=new node(s[i],w[i],NULL,NULL,"");
        }
    insertion_sort(array,0,n);
    //~ for(int i=0;i<n;i++){
        //~ cout<<array[i]->content<<"";
        //~ }
    int p=0;
    while(p!=n-1){
        node min_1=array[p];
        node min_2=array[p+1];
        node new_node=new node("",min_1->weight+min_2->weight,min_1,min_2,"");
        //cout<<new_node->weight<<endl;
        array[p+1]=new_node;
        p=p+1;
        insertion_sort(array,p,n);
        }

}


void create_huffman_code(node p){
    queue<node> nq;
    nq.push(p);
    while(nq.size()!=0){
        node cur=nq.front();
        nq.pop();
        node l=cur->leftchild;
        if(l!=NULL){l->code=cur->code+"0"; nq.push(l);}
        node r=cur->rightchild;
        if(r!=NULL){r->code=cur->code+"1"; nq.push(r);}
        if(l==NULL&&r==NULL){
            cout<<cur->content<<": "<<cur->code<<endl;
            }
        }
    }
 int main(int argc, char** argv){
     node array[8];
     string s[8]={"a","b","c","d","e","f","g","h"};
     float w[8]={1,1,2,3,5,8,13,21};
     create_huffman_tree(s,w,8,array);
     create_huffman_code(array[7]);
     }</pre>