1. 簡介

哈夫曼樹（Huffman Tree），又名：最優(yōu)二叉樹，赫夫曼樹

其標(biāo)準(zhǔn)含義是：給定N個權(quán)值作為N個葉子結(jié)點，構(gòu)造一棵二叉樹，若該樹的帶權(quán)路徑長度達(dá)到最小，稱這樣的二叉樹為最優(yōu)二叉樹，也稱為哈夫曼樹。哈夫曼樹是帶權(quán)路徑長度最短的樹，權(quán)值較大的結(jié)點離根較近。

2. 相關(guān)名詞

由于本篇存在一定的難度，因此在開始相關(guān)的學(xué)習(xí)之前，請讓我們來鞏固以下本文所涉及的名詞知識點。

a) 路徑：在一棵樹中，一個結(jié)點到另一個結(jié)點之間的通路，稱為路徑。

b) 路徑長度：在一條路徑中，每經(jīng)過一個結(jié)點，路徑長度都要加 1 。例如在一棵樹中，規(guī)定根結(jié)點所在層數(shù)為1層，那么從根結(jié)點到第 i 層結(jié)點的路徑長度為 i - 1 。

c) 結(jié)點的權(quán)：給每一個結(jié)點賦予一個新的數(shù)值，被稱為這個結(jié)點的權(quán)。

d) 結(jié)點的帶權(quán)路徑長度：指的是從根結(jié)點到該結(jié)點之間的路徑長度與該結(jié)點的權(quán)的乘積。

e)  樹的帶權(quán)路徑長度為樹中所有葉子結(jié)點的帶權(quán)路徑長度之和。通常記作 “WPL”。

3.構(gòu)建哈夫曼樹

在構(gòu)建哈夫曼樹時，只需要遵循一個原則，那就是權(quán)重越大的結(jié)點距離樹根越近。

因此，在構(gòu)建過程中，有如下的規(guī)律：

首先，選出我們數(shù)據(jù)中最小的兩個數(shù)據(jù)，構(gòu)建成二叉樹的左孩子和右孩子，而根的數(shù)據(jù)為兩者之和

其次，將剛才合成的數(shù)據(jù)作為右孩子，左孩子從未處理的數(shù)據(jù)中選出最小的一個，作為左孩子，他們的根同樣為左右孩子的權(quán)值和

不斷重復(fù)上述的步驟，直到將所有的數(shù)據(jù)全部處理完并構(gòu)建出二叉樹，這棵二叉樹就是我們的哈夫曼樹。

 如圖這顆哈夫曼樹的WPL值為：WPL= 8*1+ 6*2 + 1*3 + 4*3 = 273

4. 哈夫曼樹的結(jié)點結(jié)構(gòu)

與一般的二叉樹并沒有什么實質(zhì)的不同，甚至可以說結(jié)構(gòu)都完全一致，由于性值，因此其需要利用parent進(jìn)行訪問雙親結(jié)點

其代碼表示為：

//哈夫曼樹結(jié)點結(jié)構(gòu)
typedef struct {
    int weight; //結(jié)點權(quán)重
    int parent, left, right;    //父結(jié)點、左孩子、右孩子在數(shù)組中的位置下標(biāo)
} HTNode, *HuffmanTree;

其中weight為結(jié)點權(quán)重，

5.構(gòu)建哈夫曼樹

由上文的分析可知，構(gòu)建哈夫曼樹時，我們需要根據(jù)各個結(jié)點的權(quán)重值，篩選出其中值最小的兩個結(jié)點，構(gòu)建二叉樹。

其代碼為：

//HT為地址傳遞的存儲哈夫曼樹的數(shù)組，w為存儲結(jié)點權(quán)重值的數(shù)組，n為結(jié)點個數(shù)
void CreateHuffmanTree(HuffmanTree *HT, int *w, int n) {
    if(n <= 1)
        return; // 如果只有一個編碼就相當(dāng)于0
    int m = 2*n-1; // 哈夫曼樹總節(jié)點數(shù)，n就是葉子結(jié)點
    *HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode)); // 0號位置不用
    HuffmanTree p = *HT;
// 初始化哈夫曼樹中的所有結(jié)點
    for(int i = 1; i <= n; i++) {
        (p+i)->weight = *(w+i-1);
        (p+i)->parent = 0;
        (p+i)->left = 0;
        (p+i)->right = 0;
    }
//從樹組的下標(biāo) n+1 開始初始化哈夫曼樹中除葉子結(jié)點外的結(jié)點
    for(int i = n+1; i <= m; i++) {
        (p+i)->weight = 0;
        (p+i)->parent = 0;
        (p+i)->left = 0;
        (p+i)->right = 0;
    }
//構(gòu)建哈夫曼樹
    for(int i = n+1; i <= m; i++) {
        int s1, s2;
        Select(*HT, i-1, &s1, &s2);    //查找內(nèi)容，需要用到查找算法
        (*HT)[s1].parent = (*HT)[s2].parent = i;
        (*HT)[i].left = s1;
        (*HT)[i].right = s2;
        (*HT)[i].weight = (*HT)[s1].weight + (*HT)[s2].weight;
    }
}