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

导读哈夫曼树的应用很广，哈夫曼编码就是其中的一种。在电报通讯中，电文是以二进制的0、1序列传送的。在发送端需要将电文中的字符序列转换成二进制的0、1序列（即编码....

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

在电报通讯中，电文是以二进制的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