【摘要】：①实训说明普通编码都是定长的，而哈夫曼编码是一种压缩算法的技术，它研究如何根据使用频率得到最优的编码方案，从而整体上缩短信息的长度。实现了二叉树的存储结构和基本算法后，可以借助构造哈夫曼树得到实际问题的最优编码。②程序分析本程序主要分为两个部分：首先建立哈夫曼树，然后根据叶结点所处的位置得到哈夫曼编码。
①实训说明
普通编码都是定长的，而哈夫曼编码是一种压缩算法的技术，它研究如何根据使用频率得到最优的编码方案，从而整体上缩短信息的长度。
实现了二叉树的存储结构和基本算法后，可以借助构造哈夫曼树得到实际问题的最优编码。本实训是有关二叉树算法应用的实例。
②程序分析
本程序主要分为两个部分：首先建立哈夫曼树，然后根据叶结点所处的位置得到哈夫曼编码。
1）建立哈夫曼树
主要思想：
（1）对List集合中的所有结点进行排序。(www.xing528.com)
（2）找出List集合中权值最小的两个结点。
（3）以权值最小的两个结点作为子结点创建新结点。
（4）从List集合中删除权值最小的两个结点，并将新结点添加到List集合中。
2）进行哈夫曼编码
求叶结点编码的过程实质上就是在已建立的哈夫曼树中，从叶结点开始，沿结点的双亲链域回退到根结点，每回退一步，就走过了哈夫曼树的一个分支，从而得到一位哈夫曼码值。由于一个字符的哈夫曼编码是从根结点到相应叶结点所经过的路径上各分支所组成的0，1序列，因此先得到的分支代码为所求编码的低位码，后得到的分支代码为所求编码的高位码。
程序实现过程：先通过哈夫曼树方法构造哈夫曼树，然后在哈夫曼编码中自底部开始（也就是从数组序号为零的结点开始）向上层层判断。若在父结点左侧，则置码为0；若在父结点右侧，则置码为1。最后，通过输出生成编码。
③程序源代码
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
