数据结构—哈夫曼树(C语言看了就懂教程) 1.概念: 哈夫曼树(Huffman Tree)是一种常用的数据结构,用于实现数据压缩和编码。它是由美国计算机科学家David A. Huffman于1952年提出的,被广泛应用于通信、压缩算法和信息存储等领域。 2.性质: 1.哈夫曼树的结点的度数为0或2,没有度数为1的结点。 2.包含n个叶子结点的哈夫曼树中共有2n-1个结点。 3.其带权路径长度WPL最小的二叉树,且称为最优二叉树或哈夫曼树。 WPL = 权值 * 深度; 3.步骤 口诀: ①构造森林全是根 ②选用两小造新树 ③删除两小添新人 ④重复②③操作,直到只剩一棵树 4.图例分析 以下图例能够简单且很直观得看出并推导出N个权值根的Huffmantree构造过程。
5.哈夫曼树算法分析 像我们已知哈夫曼树框架就是类似于连连看,先是一个个的独立的点(根),然后将其中点数最小的两个点,连接在一个新的点上,这个新的点的点数就是两个小点的点数之和,然后循环往复,获得最后一个点,此时这些点之间的关系就是哈夫曼树逻辑联系。 ①构造森林全是根 第一步应该是先将一个个独立的点(根)创建出来,你得先知道这个点(根)它包含了哪些属性,作为一个程序开发者,你需要考虑的就是用什么变量来存放且描述这个点(根) 最简单的哈夫曼树他就是一颗最基本的二叉树,他拥有权值域,指针域—(父结点,左孩子结点,右孩子结点) 此时就可以考虑用结构体来存放这些点(根) ②选用两小造新树 如何选用两个权值最小的根去造新树,这是不用细说的吧,就是使用排序算法就可以了,找到最小的两个权值的下标,将其指针域中的父节点,指向新的结点,并使新的根左右孩子指向子节点! ③删除两小添新人 找到森林中最小的两个根作为子节点去构造一颗树,然后将之前的结点删除(删除肯定是不需要删除的,只是得有个标志位) 当其作为子节点去构造一颗树的时候,那它的指针域中的父结点,肯定不为空,这就是标志位! ②③步循环逻辑使用代码逻辑 循环使用for循环,使用的次数就是,要新建结点的个数 6.代码 代码以该图去编写代码,能理解该图基本就能懂上述讲解的逻辑思路
大家对于细节不懂的问题,第一可以试着去运行代码(调试运行)这样更能深刻,且贴切的理解代码的运行过程,以及地址空间的存取过程。 原文链接:数据结构—哈夫曼树(C语言看了就懂教程)_底层电工人的博客-CSDN博客
2024最新激活全家桶教程,稳定运行到2099年,请移步至置顶文章:https://sigusoft.com/99576.html
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请联系我们举报,一经查实,本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处:https://sigusoft.com/62320.html