赫夫曼树之代码实现
最后更新于：2022-04-01 15:58:28
定义它的存储结构，典型的二叉树，只是多了一个权值。
~~~
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