您当前的位置: 首页 >  数据结构与算法

星拱北辰

暂无认证

  • 0浏览

    0关注

    1205博文

    0收益

  • 0浏览

    0点赞

    0打赏

    0留言

私信
关注
热门博文

【数据结构与算法】哈夫曼树的Java实现

星拱北辰 发布时间:2019-10-01 19:13:02 ,浏览量:0

哈夫曼树

最优二叉树也称哈夫曼树,讲的直白点就是每个结点都带权值,我们让大的值离根近、小的值离根远,实现整体权值(带权路径长度)最小化。

哈夫曼算法的思想我认为就是上面讲的,而它的算法实现思路是这样的: 从根结点中抽出权值最小的两个(涉及排序,但是我这个实现代码没做严格的排序,只有比较)合并出新的根结点重新加入排序(被抽出来的两个自然是变成非根结点了啊),就这样循环下去,直到合并完成,我们得到一颗最优二叉树——哈夫曼树。

说明:

  1. 哈夫曼树有n个叶子结点,则我们可以推出其有n-1个分支结点。因此我在定义名为huffmanTree的HuffmanNode类型数组时定义长度为2*n-1。
  2. 这里排序相关没有做得很好,只是为了实现而实现,以后慢慢完善。
  3. 理论上讲哈夫曼树应该是不仅仅局限于数值,能compare就行,但这里只用int表示。
定义哈夫曼树结点
public class HuffmanNode {
   
    
    private int weight =
关注
打赏
1660750074
查看更多评论
立即登录/注册

微信扫码登录

0.0401s