C++實例解析哈夫曼樹

給定n個權值作為n個葉子結點，構造一棵二叉樹，若帶權路徑長度達到最小，稱這樣的二叉樹為最優二叉樹，也稱為哈夫曼樹(Huffman tree)。
1、路徑和路徑長度
在一棵樹中，從一個結點往下可以達到的孩子或子孫結點之間的通路，稱為路徑。通路中分支的數目稱為路徑長度。若規定根結點的層數為1，則從根結點到第L層結點的路徑長度為L-1。
2、結點的權及帶權路徑長度
若將樹中結點賦給一個有著某種含義的數值，則這個數值稱為該結點的權。結點的帶權路徑長度為：從根結點到該結點之間的路徑長度與該結點的權的乘積。
3、樹的帶權路徑長度
樹的帶權路徑長度規定為所有葉子結點的帶權路徑長度之和，記為WPL
哈夫曼樹的構造

哈夫曼樹的構造
假設有n個權值，則構造出的哈夫曼樹有n個葉子結點。 n個權值分別設為 w1、w2、…、wn，則哈夫曼樹的構造規則為：
(1) 將w1、w2、…，wn看成是有n 棵樹的森林(每棵樹僅有一個結點)；
(2) 在森林中選出兩個根結點的權值最小的樹合并，作為一棵新樹的左、右子樹，且新樹的根結點權值為其左、右子樹根結點權值之和；
(3)從森林中刪除選取的兩棵樹，并將新樹加入森林；
(4)重復(2)、(3)步，直到森林中只剩一棵樹為止，該樹即為所求得的哈夫曼樹

using namespace std;

const int MaxValue = 10000; //初始設定的權值最大值
const int MaxBit = 4;       //初始設定的最大編碼位數
const int MaxN = 10;        //初始設定的最大結點個數
struct HaffNode                      //哈夫曼樹的結點結構
{
    int weight;         //權值
    int flag;               //標記
    int parent;         //雙親結點下標
    int leftChild;          //左孩子下標
    int rightChild;         //右孩子下標
};
struct Code                           //存放哈夫曼編碼的數據元素結構
{
    int bit[MaxN];          //數組
    int start;          //編碼的起始下標
    int weight;         //字符的權值
};
void Haffman(int weight[], int n, HaffNode haffTree[])
//建立葉結點個數為n權值為weight的哈夫曼樹haffTree
{
    int j, m1, m2, x1, x2;
//哈夫曼樹haffTree初始化。n個葉結點的哈夫曼樹共有2n-1個結點
    for(int i = 0; i < 2 * n - 1 ; i++)  {
        if(i < n) haffTree[i].weight = weight[i];
        else      haffTree[i].weight = 0;
        haffTree[i].parent = 0;
        haffTree[i].flag   = 0;
        haffTree[i].leftChild = -1;
        haffTree[i].rightChild = -1;
    }
    //構造哈夫曼樹haffTree的n-1個非葉結點
    for(i = 0;i < n-1;i++)   {
        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;
            }
        }

    //將找出的兩棵權值最小的子樹合并為一棵子樹
    haffTree[x1].parent  = n+i;  
    haffTree[x2].parent  = n+i;
    haffTree[x1].flag    = 1;
    haffTree[x2].flag    = 1;
    haffTree[n+i].weight = haffTree[x1].weight+haffTree[x2].weight;
    haffTree[n+i].leftChild = x1;
    haffTree[n+i].rightChild = x2;
}

}
void HaffmanCode(HaffNode haffTree[], int n, Code haffCode[])
//由n個結點的哈夫曼樹haffTree構造哈夫曼編碼haffCode
{
    Code *cd = new Code;
    int child, parent;

//求n個葉結點的哈夫曼編碼
for(int i = 0; i < n; i++)   {
    cd->start = n-1;                    //不等長編碼的最后一位為n-1
    cd->weight = haffTree[i].weight; //取得編碼對應權值的字符
    child = i;
    parent = haffTree[child].parent;

    //由葉結點向上直到根結點
    while(parent != 0)
    {
       if(haffTree[parent].leftChild == child)
          cd->bit[cd->start] = 0; //左孩子結點編碼0
       else                
          cd->bit[cd->start] = 1;//右孩子結點編碼1
       cd->start--;
       child = parent;
       parent = haffTree[child].parent;
    }

    //保存葉結點的編碼和不等長編碼的起始位
    for(int j = cd->start+1; j < n; j++)
       haffCode[i].bit[j] = cd->bit[j];
    haffCode[i].start  = cd->start;
    haffCode[i].weight = cd->weight;  //保存編碼對應的權值
}

}
void main(void){
    int i, j, n = 4;
    int weight[] = {1,3,5,7};
    HaffNode myHaffTree = new HaffNode[2n+1];
    Code *myHaffCode = new Code[n];
    if(n > MaxN) {
        cout << "定義的n越界，修改MaxN! " << endl;
        exit(0);
    }
    Haffman(weight, n, myHaffTree);
    HaffmanCode(myHaffTree, n, myHaffCode);
//輸出每個葉結點的哈夫曼編碼
    for(i = 0; i < n; i++)   {
        cout << "Weight = " << myHaffCode[i].weight << "   Code = ";
        for(j = myHaffCode[i].start+1; j < n; j++)
            cout << myHaffCode[i].bit[j];
        cout << endl;
    }
}
 </pre>