1.哈夫曼樹的查找算法

查找算法根據(jù)構(gòu)建哈夫曼樹算法衍生而來，我們在構(gòu)建二叉樹時需要查找出哪些數(shù)據(jù)最小，以符合我們哈夫曼樹的最優(yōu)解情況。

查找權(quán)重值最小的兩個結(jié)點的思想是：從待處理數(shù)據(jù)的頭部位置開始，首先找到兩個無父結(jié)點的結(jié)點（說明還未使用其構(gòu)建成樹），然后和后續(xù)無父結(jié)點的結(jié)點依次做比較，有兩種情況需要考慮：

l  如果比兩個結(jié)點中較小的那個還小，就保留這個結(jié)點，刪除原來較大的結(jié)點；

l  如果介于兩個結(jié)點權(quán)重值之間，替換原來較大的結(jié)點；

其代碼可以表示為：

//HT數(shù)組中存放的哈夫曼樹，end表示HT數(shù)組中存放結(jié)點的最終位置，s1和s2傳遞的是HT數(shù)組中權(quán)重值最小的兩個結(jié)點在數(shù)組中的位置
void Select(HuffmanTree HT, int end, int *s1, int *s2) {
    int min1, min2;
//遍歷數(shù)組初始下標為 1
    int i = 1;
//找到還沒構(gòu)建樹的結(jié)點
    while(HT[i].parent != 0 && i <= end) {
        i++;
    }
    min1 = HT[i].weight;
    *s1 = i;
    i++;
    while(HT[i].parent != 0 && i <= end) {
        i++;
    }
//對找到的兩個結(jié)點比較大小，min2為大的，min1為小的
    if(HT[i].weight < min1) {
        min2 = min1;
        *s2 = *s1;
        min1 = HT[i].weight;
        *s1 = i;
    } else {
        min2 = HT[i].weight;
        *s2 = i;
    }
//兩個結(jié)點和后續(xù)的所有未構(gòu)建成樹的結(jié)點做比較
    for(int j=i+1; j <= end; j++) {
//如果有父結(jié)點，直接跳過，進行下一個
        if(HT[j].parent != 0) {
            continue;
        }
//如果比最小的還小，將min2=min1，min1賦值新的結(jié)點的下標
        if(HT[j].weight < min1) {
            min2 = min1;
            min1 = HT[j].weight;
            *s2 = *s1;
            *s1 = j;
        }
//如果介于兩者之間，min2賦值為新的結(jié)點的位置下標
        else if(HT[j].weight >= min1 && HT[j].weight < min2) {
            min2 = HT[j].weight;
            *s2 = j;
        }
    }
}

2.哈夫曼編碼

哈夫曼編碼(Huffman Coding)，又稱霍夫曼編碼，是一種編碼方式，可變字長編碼(VLC)的一種。Huffman于1952年提出一種編碼方法，該方法完全依據(jù)字符出現(xiàn)概率來構(gòu)造異字頭的平均長度最短的碼字，有時稱之為最佳編碼，一般就叫做Huffman編碼（有時也稱為霍夫曼編碼）。

哈夫曼編碼，主要目的是根據(jù)使用頻率來最大化節(jié)省字符（編碼）的存儲空間。

        霍夫曼編碼是一種無前綴編碼。解碼時不會混淆。其主要應(yīng)用在數(shù)據(jù)壓縮，加密解密等場合，也包括文件傳輸?shù)膱龊稀?/p>

        如果考慮到進一步節(jié)省存儲空間，就應(yīng)該將出現(xiàn)概率大（占比多）的字符用盡量少的0-1進行編碼，也就是更靠近根（節(jié)點少），這也就是最優(yōu)二叉樹-哈夫曼樹。