哈夫曼

HT,int a,int *p1,int *p2) //Select 函数，选出 HT 树到 a为止，权值最小且 parent 为 0 的 2 个节点 void main() 主 函数： 利用已建好的哈夫曼树（如不在内存，则从文件 中读入） 对文件中的正文进行编码，然后将结果存入文件 中。 如果正文中没有要编码的字符，则键盘读入并存储到 ToBeTran 文件中。 读入 ToBeTran

是课间给我的精辟回答使我有了更为明晰的思路，才有最终的设计结果。 14 七 附录 （此部分不用打印） 程序清单 在此，给出 的程序清单。 Dos 版本的程序清单在此略过。 include pragma hdrstop include include include include vector include set include utility include iterator

1,T2,… ,Tn}， 其中每一棵二叉树 Ti中只有一个带权为 wi的根结点 ， 其左右子树为空。 ② 在 F中选取两棵权值最小的树作为左右子树以构造一棵新的二叉树，且新二叉树的根结点的权值为其左右子树根结点权值之和。 ③ 在 F中删除这两棵树，同时将新得到的二叉树加入 F中。 ④ 重复 (2)和 (3)，直到 F中只含一棵树为止。 Hu Junfeng 16 哈夫曼树的构造过程 6 12 2

两个值作为叶子节点构成一棵二叉树，值较 大的叶子节点在左，两个叶子节点对应的频率之和作为根节点。 把原排列中最小的两个节点删除，新的根节点插入排列保持大小从左到右的排列顺序不变；重复执行 2），直到最后得到值为 1 的根节点。 得到一棵哈夫曼 树，如下图所示： 图 哈夫曼编码树 在得到的 哈夫曼 树上左分支标记 1，右分支标记 0，所有的字符根据其频率标记到对应的叶子节点上

作为根节点。 把原排列中最小的两个节点删除，新的根节点插入排列保持大小从左到右的排列顺序不变；重复执行 2），直到最后得到值为 1 的根节点。 得到一棵哈夫曼 树，如下图所示： 图 哈夫曼编码树 在得到的 哈夫曼 树上左分支标记 1，右分支标记 0，所有的字符根据其频率标记到对应的叶子节点上，从根节点到叶子节点路径上遇到的 0、 1 字符串即为对应叶子节点所在字符的武汉理工大学《