数据结构—哈夫曼树(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/95647.html
