c语言实现霍夫曼编码（数据结构-哈夫曼编码）

哈夫曼树的应用很广，哈夫曼编码就是其中的一种。

在电报通讯中，电文是以二进制的0、1序列传送的。在发送端需要将电文中的字符序列转换成二进制的0、1序列（即编码），在接收端又需要把接收的0、1序列转换成对应的字符序列（即译码）。

（1）等长编码

最简单的二进制编码方式是等长编码。例如，假定电文中只使用A、B、C、D、E、F这6种字符，若进行等长编码，它们分别需要三位二进制字符，可依次编码为000、001、010、011、100、101。若用这6个字符作为6个叶子结点，生成一棵二叉树，让该二叉树中每个分支结点的左、右分支分别用0和1编码，从树根结点到每个叶子结点的路径上所经分支的0、1编码序列应等于该叶子结点的二进制编码，则对应的编码二叉树如图6-13所示。

编码二叉树

由常识可知，电文中每个字符的出现频率（即次数）一般是不同的。假定在一份电文中，这6个字符的出现频率依次为4、2、6、8、3、2，则电文被编码后的总长度L可由下式计算得到：

其中n表示电文中使用的字符种数，c _i 和 l _i 分别表示对应字符k _i 在电文中的出现频率和编码长度。结合我们的例子，可求出L为：

可知，采用等长编码时，传送电文的总长度为75。

（2）不等长编码

现在讨论如何能缩短传送电文的总长度，从而节省传送时间呢？我们自然想到，若采用不等长编码，让出现频率高的字符具有较短的编码，让出现频率低的字符具有较长的编码，这样有可能缩短传送电文的总长度。采用不等长编码要避免译码的二义性或多义性。假设用0表示字符D，用01表示字符C，则当接收到编码串…01…，并译到字符0时，是立即译出对应的字符D，还是接着与下一个字符1一起译为对应的字符C，这就产生了二义性。因此，若对某一字符集进行不等长编码，则要求字符集中任一字符的编码都不能是其他字符编码的前缀。符合此要求的编码叫做无前缀编码。显然等长编码是无前缀编码，这从等长编码所对应的编码二叉树也可直观地看出，任一叶子结点都不可能是其他叶子结点的双亲，也就是说，只有当一个结点是另一个结点的双亲时，该结点的字符编码才会是另一个结点的字符编码的前缀。

为了使不等长编码成为无前缀编码，可用该字符集中的每个字符作为叶子结点生成一棵编码二叉树，为了获得传送电文的最短长度，可将每个字符的出现频率作为字符结点的权值赋予该结点，此树的最小带权路径长度就等于传送电文的最短长度。因此，求传送电文的最短长度问题就转化为求由字符集中的所有字符作为叶子结点，由字符的出现频率作为其权值所产生的哈夫曼树的问题。

根据上面所讨论的例子，生成的编码哈夫曼树如图6-14所示。由编码哈夫曼树得到的字符编码称作哈夫曼编码（Huffman Code）。在图6-14中，A、B、C、D、E、F这6个字符的哈夫曼编码依次为：00、1010、01、11、100、1011。电文的最短传送长度为：

显然，这比等长编码所得到的传送电文总长度75要小得多。

编码哈夫曼树

（3）求哈夫曼编码的算法描述

对已经介绍过的求哈夫曼树的带权路径长度的算法略加修改，就可以得到哈夫曼编码的算法描述，具体给出如下。

求哈夫曼编码算法

void HuffManCoding(struct BTreeNode* FBT, int len) /*根据FBT所指向的哈夫曼树输出每个叶子的编码，len初值为0*/ { /*定义一个静态数组a，保存一个叶子的编码，数组的长度要 至少等于哈夫曼树的深度减1*/ static int a[10]; if(FBT!=NULL) { /*访问到叶子结点时输出其保存在数组a中的0和1序列编码*/ if(FBT->left==NULL && FBT->right==NULL) { int i; printf("结点权值为%d的编码:",FBT->data); for(i=0; i<len; i ) printf("%d ",a[i]); printf("\n"); } /*访问到非叶子结点时分别向左、右子树递归调用，并把分支上的 0、1编码保存到数组a的对应元素中，向下深入一层时len值增1*/ else { a[len]=0; HuffManCoding(FBT->left,len 1); a[len]=1; HuffManCoding(FBT->right,len 1); } } }