哈夫曼树 构造_哈夫曼树只有度为0和度为2

哈夫曼树 构造_哈夫曼树只有度为0和度为2数据结构-哈夫曼树(C语言看了就懂教程)1.概念:哈夫曼树(Huffman Tree)是一种常用的数据结构,用于实现数据压缩和编码。它是由美国计算机科学家David A. Huffman于1952年提出的,被广泛应用于通信、压缩算法和信息存储等领域。2.性质:1.哈夫曼树的结点

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

2024最新激活全家桶教程,稳定运行到2099年,请移步至置顶文章:https://sigusoft.com/99576.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请联系我们举报,一经查实,本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处:https://sigusoft.com/62320.html

(0)
上一篇 2024年 8月 28日 下午6:14
下一篇 2024年 8月 28日

相关推荐

关注微信