在數(shù)據(jù)傳輸?shù)倪^程當中，我們總是希望用盡可能少的帶寬傳輸更多的數(shù)據(jù)，哈夫曼就是其中的一種較少帶寬傳輸?shù)姆椒ā９蚵幕舅枷氩粡碗s，那就是對于出現(xiàn)頻率高的數(shù)據(jù)用短字節(jié)表示，對于頻率比較低得數(shù)據(jù)用長字節(jié)表示。

比如說，現(xiàn)在有4個數(shù)據(jù)需要傳輸，分別為A、B、C、D，所以一般來說，如果此時沒有考慮四個數(shù)據(jù)出現(xiàn)的概率，那么我們完全可以這么分配，平均長度為2，

/* 
*  A - 00         B - 01 
*  C - 10         D - 11 
*/  

但是，現(xiàn)在條件發(fā)生了改變，四個數(shù)據(jù)出現(xiàn)的頻率并不一樣，分別為0.1/0.2/0.3/0.4。那么這時候應該怎么分配長度呢，其實也簡單。我們只要把所有數(shù)據(jù)按照頻率從低到高排列，每次取前兩位合并成新的節(jié)點，再把這個新節(jié)點放到隊列中重新排序即可。新節(jié)點的左結點默認設為1，右結點默認設為0。然后重復上面的過程，直到所有的節(jié)點都合并成一個節(jié)點為止。如果應用到實際的示例中，合并的過程應該是這樣的， 第一步，首先合并A和B，因為A和B是概率最小的

/* 
*   
*           total_1(0.3)           C (0.3)   D(0.4) 
*          /         \ 
*        A(0.1)      B(0.2) 
*/  

第二步，接著合并total_1和C，

/* 
*                 total_2 (0.6) 
*               /          \      
*           total_1(0.3)    C (0.3)    D(0.4) 
*          /         \ 
*        A(0.1)      B(0.2) 
*/  

最后一步，合并total_2和D，

/* 
*            final (1.0) 
*          /       \           
*       D (0.4)    total_2 (0.6)     
*                /          \      
*           total_1(0.3)    C (0.3)    
*          /         \ 
*        A(0.1)      B(0.2) 
*/  

所以按照上面的生成樹，數(shù)據(jù)的編號應該這么安排，

/* 
*   A - 011       B - 010 
*   C - 00        D - 1 
*/ 

看上去A和B的長度還增加了，但是D的長度減少了。那么整個數(shù)據(jù)的平均長度有沒有減少呢？我們可以計算一下。3 0.1 + 3 0.2 + 2 0.3 + 0.4 = 1.9 < 2。我們發(fā)現(xiàn)調(diào)整后的數(shù)據(jù)平均長度比原來減少了近（2 - 1.9）/2 100% = 10 %，這可是巨大的發(fā)現(xiàn)啊。

為了完成整個哈夫曼樹的創(chuàng)建，我們還需要定義一個數(shù)據(jù)結構：

typedef struct _HUFFMAN_NODE  
{  
    char str;  
    double frequence;  
    int symbol;  
    struct _HUFFMAN_NODE* left;  
    struct _HUFFMAN_NODE* right;  
    struct _HUFFMAN_NODE* parent;  

}HUFFMAN_NODE;  

其中str記錄字符，frequency記錄字符出現(xiàn)的頻率， symbol記錄分配的數(shù)據(jù)，左子樹為1、右子樹為0，left為左子樹，right為右子樹，parent為父節(jié)點。接下來，我們從創(chuàng)建huffman結點開始。

HUFFMAN_NODE* create_new_node(char str, double frq)  
{  
    HUFFMAN_NODE* pNode = (HUFFMAN_NODE*)malloc(sizeof(HUFFMAN_NODE));  
    assert(NULL != pNode);  

    pNode->str = str;  
    pNode->frequence = frq;  
    pNode->symbol = -1;  
    pNode->left = NULL;  
    pNode->right = NULL;  
    pNode->parent = NULL;  
    return pNode;  
}