哈夫曼编码（构建哈夫曼树） 目录 1.哈夫曼树 （1）相关概念 （2）定义 （3）哈夫曼算法 2.哈夫曼编码 （1）相关概念 （2）定义 （3）代码实现 3.完整代码 4.测试输出 1.哈夫曼树 （1）相关概念 叶子结点的权值：对叶子结点赋予的一个有意义的数值量（往往体现了访问的频率）二叉树的带权路径长度：设二叉树具有n个带权值的叶子结点，从根结点到各个叶子结点的路径长度与相应叶子结点权值的乘积之和（所有的叶子加起来) （2）定义 哈夫曼树：给定一组具有确定权值的叶子结点，带权路径长度最小的二叉树 特点： 1，权值越大的叶子结点越靠近根结点，而权值越小的叶子结点越远离根结点 2，只有度为0(叶子结点）和度为2（分支结点）的结点，不存在度为1的结点 （3）哈夫曼算法 1.基本步骤： （1）初始化：由给定的n个权值构造n棵只有一个结点的二叉树，构成集合F （2）选取与合并：在上述结点二叉树集合F中，选取权值最小的两棵树，分别作为左，右子树构建一棵新的二叉树，其权值为左右子树权值之和 （3）删除与加入：在集合F中删除作为左右子树的两棵二叉树，并将新二叉树加入F （4）重复：（2）（3），直至集合F中只剩下一棵二叉树时，即为哈夫曼树 基本步骤实现如下图： （图片来自懒猫老师《数据结构》相关课程笔记） 
2.存储结构 设置一个数组huffTree[2n-1]保存哈夫曼树中各点的信息，数组素的结点结构如下： 为什么存储数组的素个数为2n-1呢？ 这里要引入二叉树的性质，推导过程如下： 
3.代码实现 过程图解： 每一次进行合并后，将新二叉树加入数组，修改结点的双亲和左右孩子的下标，构建起结点之间的链接关系；并更新合并后结点的权值 i1 :最小权值结点的下标 i2 :次小权值结点的下标 k :合并后的新结点下标 
代码实现： void HuffmanTree(element *huffTree, int *w, int n) 参数分别为，哈曼夫树的数组，存放权值的数组，最初的结点个数（也是权值个数） select(element *huffTree, int k, int *i1, int *i2) 参数分别为，哈曼夫树的数组，合并后的新结点下标，最小权值结点下标，次小权值结点下标 （最下面有相关的测试完整代码） 2.哈夫曼编码 （1）相关概念 编码：给每一个对象标记一个二进制位串来表示一组对象 前缀编码：一组编码中任一编码都不是其它任何一个编码的前缀（前缀编码保证了在解码时不会有多种可能） （2）定义 哈夫曼编码就是在哈夫曼树的基础上，从叶子结点开始向上遍历，左孩子记录码为0；右孩子记录码为1。 哈夫曼编码： 
（3）代码实现 每次循环生成一个权值对应的哈夫曼编码，并从尾部开始存入temp数组中，再赋值给huffCode[n]数组 储存结构实现可以参考下图： 
3.完整代码 4.测试输出 
初学小白，有错误欢迎指正喔！X
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/79371.html
