定義它的存儲結構，典型的二叉樹，只是多了一個權值。
~~~
typedef struct
{
int weight;
int parent, lchild, rchild;
}HTNode, *HuffmanTree;
typedef char **HuffmanCode;
~~~
HuffmanCode是一個字符串數組，用來保存葉子結點最終的編碼結果。
存儲空間是多少呢? 從前一章講的構造赫夫曼樹的過程可以找出規律，n個葉子結點所構造的赫夫曼樹共有2n-1個結點，這就是我們要分配的空間。
~~~
int m = 2 * n - 1;
*HT = (HuffmanTree)malloc((m+1)*sizeof(HTNode));//多分配一個空間，0號不用
~~~
函數的接口形式如下:
~~~
bool HuffmanCoding(HuffmanTree *HT, HuffmanCode *HC, int *w, int n)
~~~
HT是最終構造的赫夫曼樹，是個輸出參數，HC也是個輸出函數，就是個字符串數組，輸出最終的編碼。W存放n個葉子結點的權值，當然都是大于0的整數，n是葉子結點的個數, 最后這兩個都是輸入參數。
構造赫夫曼樹的過程代碼其實很簡單:
~~~
//構建赫夫曼樹
for (i = n + 1; i <= m; i++)
{
if (!Select(*HT, i - 1, &s1, &s2)) return false;
(*HT)[s1].parent = i;
(*HT)[s2].parent = i;
(*HT)[i].lchild = s1;
(*HT)[i].rchild = s2;
(*HT)[i].weight = (*HT)[s1].weight + (*HT)[s2].weight;
}
~~~
select函數從HT[1...nEnd]中選出parent為0, 并且weight最小的兩個結點，序號分別由s1 和 s2返回，它的實現如下:
~~~
static bool Select(HuffmanTree HT, int nEnd, int *s1, int *s2)
{
int i = 0;
int nComp = 0;
nComp = MAX;
*s1 = MAX;
*s2 = MAX;
//第一輪循環，找到最小的給s1
for (i = 1; i <= nEnd; i++)
{
if ((HT[i].weight < nComp) && (HT[i].parent == 0))
{
nComp = HT[i].weight;
*s1 = i;
}
}
//第二輪循環，找到次小的給s2
nComp = MAX;
for (i = 1; i <= nEnd; i++)
{
if ((HT[i].weight < nComp) && (i != *s1) && (HT[i].parent == 0))
{
nComp = HT[i].weight;
*s2 = i;
}
}
if ((*s1 == MAX) || (*s2 == MAX))
{
return false;
}
return true;
}
~~~
編碼的結果是保存在HC中的，為了方便采用逆向保存的形式，即從葉子到根求編碼，然后輸出時就是正向的了。
~~~
for (i = 1; i <= n; i++)
{
start = n - 1;
for (c = i, f = (*HT)[i].parent; f != 0; c = f, f = (*HT)[f].parent)
{
//左0右1
if ((*HT)[f].lchild == c)
{
cd[--start] = '0';
}
else
{
cd[--start] = '1';
}
}
(*HC)[i] = (char *)malloc((n - start));
strcpy((*HC)[i], &cd[start]);
}
~~~
代碼下載地址:
http://download.csdn.net/detail/pony_maggie/8209175
或
https://github.com/pony-maggie/HuffmanCode
