【数据结构与算法学习笔记】20 哈夫曼树 搞要： 本文主要介绍数据结构与算法中的哈夫曼树，是本人的学习笔记。对于想学习数据结构与算法的读者，可以作为参考。 以C语言为主，有些地方与C++混合实现。 由于很多草稿图片都绘制在本子上，所以本系列笔记中很多地方并没有给出图片，如有需要读者可自行根据笔记内容绘制图片。 如有错误或者遗漏之处，欢迎指出。 目录： 1，基本概念 2，03 哈夫曼树.h 3，哈弗曼树的算法实现（思路一） 4，哈弗曼树的算法实现（思路二） 1，基本概念 /* 哈夫曼(Huffman)编码是首个实用的压缩编码方案，无损压缩； 哈夫曼编码在通信中能构造出一种不等长的二进制，使唤编码后的电文长度最短，且不产生二义性； 哈夫曼编码的生成需要用到哈夫曼编码树； 哈夫曼树基本概念： 1，权：树结点间的连线相关的数值（可以理解成线的长度，或者孩子的权重）叫做权，weight； 2，路径：在一棵树中，一个结点到另一个结点之间的通路，称为路径； 3，结点的路径长度：从根结点到该结点的路径上的连接数； 4，树的路径长度：树中每个叶结点的路径长度之和； 5，结点带权路径长度：结点的路径长度与结点权值的乘积； 6，树的带权路径长度(WPL,Weighted Path Length)：树中所有叶结点的带权路径长度之和； WPL的值越小，说明构造出来的二叉树的性能就越优！ 7，哈夫曼树：当用 n 个结点（都做叶结点且都有各自的权值）试图构建一棵树时，如果构建的这棵树的带权路径长度（WPL）最小， 称这棵树为“最优二叉树”，也叫“赫夫曼树”或者“哈夫曼树”； 构造原则：权重越大的结点离树根越近； 哈夫曼树的构造过程： 对于给定的有各自权值的 n 个结点，步骤如下： 1，在 n 个权值中选出两个最小的权值，对应的两个结点组成一个新的二叉树（小的放左边），且新二叉树的根结点的权值为左右孩子权值的和； 2，在原有的 n 个权值中删除那两个最小的权值，同时将新的权值加入到 n–2 个权值的行列中，小的永远放左边，以此类推； 3，重复 1 和 2 ，直到所以的结点构建成了一棵二叉树为止，这棵树就是哈夫曼树。 哈弗曼树中结点结构： 构建哈夫曼树时，首先需要确定树中结点的构成。 由于哈夫曼树的构建是从叶子结点开始，不断地构建新的父结点，直至树根，所以结点中应包含指向双亲结点的指针。 但是在使用哈夫曼树时是从树根开始，根据需求遍历树中的结点，因此每个结点需要有指向其左孩子和右孩子的指针。 */ 2，03 哈夫曼树.h 3，哈弗曼树的算法实现（思路一） /* 哈弗曼树的算法实现（思路一）： 需要每次根据各个结点的权重值，筛选出其中值最小的两个结点，然后构建二叉树。 查找权重值最小的两个结点的思想是：从树组起始位置开始，首先找到两个无双亲结点的结点（说明还未使用其构建成树）， 然后和后续无双亲结点的结点依次做比较，有两种情况需要考虑： 1，如果比两个结点中较小的那个还小，就保留这个结点，删除原来较大的结点； 2，如果介于两个结点权重值之间，替换原来较大的结点； */ //HT数组中存放的哈夫曼树，end表示HT数组中存放结点的最终位置，s1和s2传递的是HT数组中权重值最小的两个结点在数组中 //注意：s1和s2传入的是实参的地址，所以函数运行完成后，实参中存放的自然就是哈夫曼树中权重值最小的两个结点在数组中的位置 4，哈弗曼树的算法实现（思路二） /* 哈夫曼编码基本概念： 1，定长编码：单个编码的长度是固定的，例如ASCII码； 2，变长编码：单个编码的长度可以不一致，可以根据出现频率来调节； 3，前缀码：没有任何码字是其他码字的前缀，例如哈夫曼编码； 4,哈夫曼编码左子树都用0表示，右子树都用1表示； 构造步骤： 1，创建一个队列，按出现次数从小到大排列； 2，构建哈夫曼树； 3，构建哈夫曼表； 4，encode，编码 5, decode，解码 */ 哈弗曼树的算法实现（思路二）： //by CODspielen
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/86276.html
