霍夫曼树和哈夫曼树一样吗为什么不一样呢_霍夫曼树和哈夫曼树一样吗为什么不一样呢

霍夫曼树和哈夫曼树一样吗为什么不一样呢_霍夫曼树和哈夫曼树一样吗为什么不一样呢数据结构与算法之Huffman tree(赫夫曼树 / 霍夫曼树 / 哈夫曼树 / 最优二叉树)目录 赫夫曼树概述定义构造赫夫曼树步骤代码实现赫夫曼树概述HuffmanTree因为翻译不同所以有其他的名字:赫夫曼

数据结构与算法之Huffman tree(赫夫曼树 / 霍夫曼树 / 哈夫曼树 / 最优二叉树)   目录 赫夫曼树概述定义构造赫夫曼树步骤代码实现   赫夫曼树概述   HuffmanTree因为翻译不同所以有其他的名字:赫夫曼树、霍夫曼树、哈夫曼树   赫夫曼树又称最优二叉树,是一种带权路径长度最短的二叉树。所谓树的带权路径长度,就是树中所有的叶结点的权值乘上其到根结点的路径长度(若根结点为0层,叶结点到根结点的路径长度为叶结点的层数)。树的路径长度是从树根到每一结点的路径长度之和,记为WPL=(W1L1+W2L2+W3L3+…+WnLn),N个权值Wi(i=1,2,…n)构成一棵有N个叶结点的二叉树,相应的叶结点的路径长度为Li(i=1,2,…n)。可以证明赫夫曼树的WPL是最小的。   定义   路径: 路径是指从一个节点到另一个节点的分支序列。   路径长度: 指从一个节点到另一个结点所经过的分支数目。 如下图:从根节点到a的分支数目为2   
在这里插入图片描述   树的路径长度: 树中所有结点的路径长度之和为树的路径长度PL。 如下图:PL为10   
在这里插入图片描述   节点的权: 给树的每个结点赋予一个具有某种实际意义的实数,我们称该实数为这个结点的权。如下图:7、5、2、4   
在这里插入图片描述   带权路径长度: 从树根到某一结点的路径长度与该节点的权的乘积,叫做该结点的带权路径长度。如下图:A的带权路径长度为2*7=14   
在这里插入图片描述   树的带权路径长度(WPL): 树的带权路径长度为树中所有叶子节点的带权路径长度之和   最优二叉树:权值最大的节点离跟节点越近的二叉树,所得WPL值最小,就是最优二叉树。如下图:(b)   
在这里插入图片描述 (a)(b)(c)   构造赫夫曼树步骤   第一步:使用数组中所有素创建若干个二叉树,这些值作为节点的权值(只有一个节点)。   
在这里插入图片描述   第二步:将这些节点按照权值的大小进行排序。   
在这里插入图片描述   第三步:取出权值最小的两个节点,并创建一个新的节点作为这两个节点的父节点,这个父节点的权值为两个子节点的权值之和。将这两个节点分别赋给父节点的左右节点   
在这里插入图片描述   第四步:删除这两个节点,将父节点添加进集合里   
在这里插入图片描述   第五步:重复第二步到第四步,直到集合中只剩一个素,结束循环   
在这里插入图片描述   代码实现   节点类   测试类   循环次数结果

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

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

(0)
上一篇 2024年 9月 14日
下一篇 2024年 9月 14日

相关推荐

关注微信