哈夫曼樹(Huffman Tree)

給定N個權(quán)值作為N個葉子結(jié)點，構(gòu)造一棵二叉樹，若該樹的帶權(quán)路徑長度達到最小，稱這樣的二叉樹為最優(yōu)二叉樹，也稱為哈夫曼樹(Huffman Tree)。哈夫曼樹是帶權(quán)路徑長度最短的樹，權(quán)值較大的結(jié)點離根較近。
路徑：在一棵樹中，一個結(jié)點到另一個結(jié)點之間的通道，稱為路徑。上圖中，從根結(jié)點到a之間的通路就是一條路徑。
路徑長度：在一條路徑上，每經(jīng)過一個結(jié)點，路徑的長度就要加1。在一棵樹中，規(guī)定根結(jié)點所在層數(shù)為1層，那么根結(jié)點到第i層結(jié)點的路徑長度為i-1。
結(jié)點的權(quán)：給每一個結(jié)點賦予一個新的數(shù)值，稱為結(jié)點的權(quán)。例如上圖中a結(jié)點的權(quán)為7。
結(jié)點的帶權(quán)路徑長度：指的是從根結(jié)點到每一個結(jié)點的路徑長度和該結(jié)點權(quán)值的乘積。上圖中c結(jié)點的帶權(quán)路徑長度為2*3=6。
樹的帶權(quán)路徑長度為樹中所有葉子結(jié)點的帶權(quán)路徑長度之和。記做WPL。下圖中這棵樹的帶權(quán)路徑長度為：
WPL = 7 * 1 + 5 * 2 + 2 * 3 + 4 * 3 = 30

。
樹的構(gòu)建基本思想：
(1) 將w1、w2、…，wn看成是有n 棵樹的森林(每棵樹僅有一個結(jié)點)；
(2) 在森林中選出兩個根結(jié)點的權(quán)值最小的樹合并，作為一棵新樹的左、右子樹，且新樹的根結(jié)點權(quán)值為其左、右子樹根結(jié)點權(quán)值之和；
(3)從森林中刪除選取的兩棵樹，并將新樹加入森林；
(4)重復(2)、(3)步，直到森林中只剩一棵樹為止，該樹即為所求得的哈夫曼樹。
以2 4 5 7為例

哈夫曼編碼

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

哈夫曼樹的應用很廣，哈夫曼編碼就是其在電訊通信中的應用之一。廣泛地用于數(shù)據(jù)文件壓縮的十分有效的編碼方法。其壓縮率通常在20%～90%之間。在電訊通信業(yè)務中，通常用二進制編碼來表示字母或其他字符，并用這樣的編碼來表示字符序列。

例：如果需傳送的電文為 ‘BADCADFEED’，它只用到6種字符，用兩位二進制編碼便可分辨。假設 A, B, C, D，E，F(xiàn) 的編碼分別為 00, 01,10, 11，則上述電文便為 ‘001 000 011 010 000 011 101 100 100 011’（共 30 位），譯碼員按兩位進行分組譯碼，便可恢復原來的電文。

A 01
B 1001
C 101
D 00
E 11
F 1001
BADCADFEED 編碼
原編碼?進制: 001 000 011 010 000 011 101 100 100 011(共30個字符)
新編碼?進制: 1001 01 00 101 01 00 1001 11 11 00(共25個字符)
顯然利用haffman coding 極大的縮短了字符個數(shù)

哈夫曼樹的實現(xiàn)思路:

獲取根據(jù)權(quán)值構(gòu)建的哈夫曼樹
循環(huán)遍歷[0,n]個結(jié)點;
創(chuàng)建臨時結(jié)點cd ,從根結(jié)點開始對?進?編碼,左孩?為0,右孩?為1;
將編碼后的結(jié)點存儲haffCode[i]
設置HaffCode[i]的開始位置以及權(quán)值;

代碼實現(xiàn)：

#include "string.h"
#include "stdio.h"
#include "stdlib.h"

const int MaxValue = 10000;//初始設定的權(quán)值最大值
const int MaxBit = 4;//初始設定的最大編碼位數(shù)
const int MaxN = 10;//初始設定的最大結(jié)點個數(shù)

//節(jié)點
typedef struct HaffNode {
    int weight;//權(quán)重
    int flag;//是否插入過
    int parent;//父節(jié)點
    int leftChild;//左孩子
    int rightChild;//右孩子
}HaffNode;

//哈夫曼編碼數(shù)據(jù)結(jié)構(gòu)元素
typedef struct Code//存放哈夫曼編碼的數(shù)據(jù)元素結(jié)構(gòu)
{
    int bit[MaxBit];//數(shù)組
    int start;  //編碼的起始下標
    int weight;//字符的權(quán)值
}Code;


//1.
//根據(jù)權(quán)重值,構(gòu)建哈夫曼樹;
//{2,4,5,7}
//n = 4;

void Haffman(int weight[], int n, HaffNode *haffTree) {
    int j,m1,m2,x1,x2;
    //1.哈夫曼樹初始化，n個葉子節(jié)點，哈夫曼樹總結(jié)點個數(shù)為2n-1
    //所有節(jié)點都賦初值
    for (int i = 0; i < 2*n-1; i++) {
        if (i<n) {
            haffTree[i].weight = weight[I];
        } else {
            haffTree[i].weight = 0;
        }
        
        haffTree[i].flag = 0;
        haffTree[i].parent = 0;
        haffTree[i].leftChild = -1;
        haffTree[i].rightChild = -1;
    }
    //2.構(gòu)造haffTree的 n-1個非葉子節(jié)點，找到最小的兩個子樹合并
    
    for (int i = 0; i<n-1; i++) {//構(gòu)建節(jié)點
        m1 = m2 = MaxValue;
        x1 = x2 = 0;
        //找最小值
        for (j = 0; j<n+i; j++) {
            //沒插入過才找最小值，插入過的不取
            if (haffTree[j].weight<m1 && haffTree[j].flag == 0) {
                m2 = m1;
                x2 = x1;
                m1 = haffTree[j].weight;
                x1 = j;
            } else if (haffTree[j].weight<m2 && haffTree[j].flag == 0) {
                m2 = haffTree[j].weight;
                x2 = j;
            }
        }
        //3.將最小將找出的兩棵權(quán)值最小的子樹合并為一棵子樹
        haffTree[x1].parent = I+n;
        haffTree[x2].parent = I+n;
        //4.將2個結(jié)點的flag 標記為1,表示已經(jīng)加入到哈夫曼樹中
        haffTree[x1].flag = 1;
        haffTree[x2].flag = 1;
        //5.修改n+i結(jié)點的權(quán)值
        haffTree[i+n].weight = haffTree[x1].weight + haffTree[x2].weight;
        //6.修改n+i左右孩子的值
        haffTree[i+n].leftChild = x1;
        haffTree[i+n].rightChild = x2;
    }
}


/*
9.2 哈夫曼編碼
由n個結(jié)點的哈夫曼樹haffTree構(gòu)造哈夫曼編碼haffCode
//{2,4,5,7}
*/
void HaffmanCode(HaffNode *haffTree, int n, Code HaffCode[]) {
    //1.創(chuàng)建臨時節(jié)點cd
    Code *cd = (Code * )malloc(sizeof(Code));
    int child, parent;
    //2.求n個節(jié)點的哈夫曼編碼
    for (int i = 0; i<n; i++) {
        cd->start = 0;
        cd->weight = haffTree[i].weight;
        //當前節(jié)點設為孩子節(jié)點
        child = I;
        //找到孩子節(jié)點的父節(jié)點
        parent = haffTree[child].parent;
        //由葉子節(jié)點向上遍歷找到根節(jié)點
        while (parent != 0) {
            if (haffTree[parent].leftChild == child) {
                cd->bit[cd->start] = 0;
            } else {
                cd->bit[cd->start] = 1;
            }
            //編碼加一
            cd->start++;
            //讓當前的雙親節(jié)點成為孩子節(jié)點
            child = parent;
            //找雙親節(jié)點
            parent = haffTree[child].parent;
        }
        int temp = 0;
        //bit是反的，要反轉(zhuǎn)過來
        for(int j = cd->start-1; j>=0; j--) {
            temp = cd->start-1-j;
            HaffCode[i].bit[temp] = cd->bit[j];
        }
        //把cd中的數(shù)據(jù)賦值到haffCode[I]中.
        //保存好haffCode 的起始位以及權(quán)值;
        HaffCode[i].weight = haffTree[i].weight;
         //保存編碼對應的權(quán)值
        HaffCode[i].start = cd->start;

    }
   
}

int main(int argc, const char * argv[]) {
    printf("Hello, 哈夫曼編碼!\n");
    int i, j, n = 4, m = 0;
    
    //權(quán)值
    int weight[] = {2,4,5,7};
    
    //初始化哈夫曼樹, 哈夫曼編碼
    HaffNode *myHaffTree = malloc(sizeof(HaffNode)*2*n-1);
    Code *myHaffCode = malloc(sizeof(Code)*n);
    
    //當前n > MaxN,表示超界. 無法處理.
    if (n>MaxN)
    {
        printf("定義的n越界，修改MaxN!");
        exit(0);
    }
    
    //1. 構(gòu)建哈夫曼樹
    Haffman(weight, n, myHaffTree);
    //2.根據(jù)哈夫曼樹得到哈夫曼編碼
    HaffmanCode(myHaffTree, n, myHaffCode);
    //3.
    for (i = 0; i<n; I++)
    {
        printf("Weight = %d\n",myHaffCode[i].weight);
        for (j = 0; j<myHaffCode[i].start; j++)
            printf("%d",myHaffCode[i].bit[j]);
        m = m + myHaffCode[i].weight*myHaffCode[i].start;
        printf("\n");
    }
    printf("Huffman's WPS is:%d\n",m);
    return 0;
}