数据结构【哈夫曼树】 哈夫曼树 哈夫曼树的概念哈夫曼树的构造构造算法的实现哈夫曼树应用哈夫曼编码哈夫曼编码的算法实现 哈夫曼树的概念 最优二叉树也称哈夫曼 (Huffman) 树，是指对于一组带有确定权值的叶子结点，构造的具有最小带权路径长度的二叉树。权值是指一个与特定结点相关的数值。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。 涉及到的几个概念： 路径: 从树中一个结点到另一个结点之间的分支构成这两个结点间的路径。 结点的路径长度: 两结点间路径上的分支数。 树的路径长度: 从树根到每一个结点的路径长度之和。记作: TL。 权(weight): 将树中结点赋给一个有着某种含义的数值则这个数值称为该结点的权。 结点的带权路径长度: 从根结点到该结点之间的路径长度与该结点的权的乘积。 树的带权路径长度: 树中所有叶子结点的带权路径长度之和。 二叉树的带权路径长度 (Weighted Path Length)： 二叉树的路径长度是指由根结点到所有叶子结点的路径长度之和。 如果二叉树中的所有叶子结点都具有一个特定的权值，则可将这一概念加以推广。设二叉树具有n个带权值的叶子结点，那么从根结点到各个叶子结点的路径长度与该叶子结点相应的权值的乘积之和叫做又树的带权路径长度，记为： 
其中，wk为第k个叶子结点的权值，Lk为第k个叶子结点的路径长度。 
最优树：带权路径长度(WPL)最短的树 最优二叉树：带权路径长度(WPL)最短的二叉树 哈夫曼树的构造 哈夫曼算法(构造哈夫曼树的四句口诀) (1)根据n个给定的权值{ w1、w2、…、wn}构成n棵二叉树的森林F=(T1、T2、…、Tn}，其中Ti只有一个带权为 wi的根结点。 构造森林全是根 (2)在F中选取两棵根结点的权值最小的树作为左右子树，构造一棵新的二叉树，且设置新的二叉树的根结点的权值为其左右子树上根结点的权值之和。 选用两小造新树 (3)在F中删除这两棵树，同时将新得到的二又树加入森林中。 删除两小添新人 (4)重复(2)和(3)，直到森林中只有一棵树为止，这棵树即为哈夫曼树。 重复 2、3 剩单根 
可以得出： 1）哈夫曼树的节点的度为0或2，没有度为1的节点。 2）包含n个叶子节点的哈夫曼树中共有2n-1个节点。 3）包含n棵树的森林要经过n-1次合并才能形成哈夫曼树，共产生n-1个新节点。 构造算法的实现 顺序结构存储–一维结构数组 先初始化再构造 1.初始化HT[1…2n-1]: lch=rch=parent=0； 2. 输入初始n个叶子结点: 置HT[1…n]的weight值； 
3.进行以下n-1次合并，依次产生n-1个结点HT[i]，i=n+1…2n-1: a) 在HT[1.i-1]中选两个未被选过(从parent ==_0 的结点中选)的weight最小的两个结点HT[s1]和HT[s2],s1、s2为两个最小结点下标; 修改HT[s1]和HT[s2]的parent值: HT[s1] .parent=i; HT[s2] .parent=i;b)修改新产生的HT[i]: HT[il.weight=HT[s1].weight + HT[s2].weight HT[i]. lch=s1; HT[i]. rch=s2; 
哈夫曼树应用 哈夫曼编码 
哈夫曼编码的算法实现 
示例： 
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/25798.html
