哈夫曼编码与解码的实现 - 1 - 一、设计思想 (一) 哈夫曼树的设计思想 对于一组具有确定权值的叶子结点可以构造出多个具有不同带权路径长度的二叉树，其中具有最小带权路径长度的二叉树称作哈夫曼树或最优二叉树。 首先给定 n 个权值制造 n 个只含根结点的二叉树，得到一个二叉树林；再在这二叉树林里面找根结点的权值最小和次小的两棵树作成新的二叉树，其中新的二叉树的根结点的权值为左右子根结点权值之和；最后在二叉树林中把组合过的二叉树删除，再重复第二步，直到最后就剩一颗二叉树的时候得到的这棵二叉树就是哈夫曼树。 （二）哈夫曼编码与解码的设计思想 在数据通讯中，经常要将传送的文字转换为二进制字符 0 和 1 组成的二进制串，称这个过程为编码。与子相对的是解码或是译码，就是用与编码相同的方式将二进制串转换称编码前的文字的过程称作解码。在这里是通过哈夫曼树实现编码与解码的，所以称作是哈夫曼编码与解码。 首先输入一个字符串，还有相应的在哈夫曼树里的权值，这样用哈夫曼树把字符串用二进制串代替它，这个过程要注意树和编码问题，其中树的问题在上面已经解决，主要看编码的问题，就是根据我们输入的字符串和权值建立相应的树模型，这一步完成那编码就已经完成了，最后打印就行了；然后就是解码，完成编码相应的解码就相对简单了，就是先找到在编码的时候建的那个模型树，将编码中的二进制串再根据权值转换为相应的字符串，这样一步步解码就行了。 以上就是通过用哈夫曼树进行哈夫曼编码与解码如何 实现的主要设计思想。 哈夫曼编码与解码的实现 - 2 - 二、算法流程图 （一）哈夫曼树的流程图 开始初始化哈夫曼链表二叉树林找最小和次小的二叉树组合成新的二叉树删除用过的二叉树是不是最后一个二叉树结束是不是 图 1 哈夫曼树的流程图 （二）编码与解码的流程图 开始输入字符串判断权值建立路径有最小和次小循环建立二叉树根据树对路径分左 0右 1写出对应结点的编码结束开始找到树的根结点输入二进制串扫描根据树的路径打印对应字符继续扫描是否结束否输出字符串是结束 图 2 编码与解码的流程图 图片说明：（左边）编码流程图，（右边）解码流程图。 哈夫曼编码与解码的实现 - 3 - 三、源代码 下面给出的是用中缀转后缀算法实现的程序的源代码： #include "stdio.h" #include "string.h" #define MAX 100 /*定义常量*/ struct HaffNode { int weight; /*...
