结丹期简介

结丹期主要阐述的是对哈夫曼树的思路分析与创建分析

提供完整代码,代码在筑基期中     

目录

哈夫曼树(huffman)的创建思想:

哈夫曼树的代码实现与分析:

创建一个节点类  

代码分析:

创建一个HuffmanTree(哈夫曼树类)

代码分析:

创建一个创建哈夫曼树的方法 

代码分析:

结论

 哈夫曼树(huffman)的创建思想:

1.  将列表从小到大的进行排序
2.  将列表中的最小权的子树(节点)取出
3.  将这两个子树创建成一个新子树,新子树的根节点的权等于这两个子树的权之和
4.  将新的子树放回列表中,重新进行上述操作,直到形成一个哈夫曼树

哈夫曼树的代码实现与分析:

创建一个节点类  

代码分析:

1. 属性: value代表的是节点的权,left和right分别表示左子节点和右子节点
2. 构造方法: 用于初始化节点
3. toString方法: 方便输出节点,里面有一个字符串拼接的操作哦
4. 实现Comparable接口: 由于思路中有提及需要进行排序的操作,所以节点类要实现Comparable接口,并实现compareTo方法
   1. compareTo方法,如果返回值是value – node.value 则表示从小到大,反之,从大到小

创建一个HuffmanTree(哈夫曼树类)

代码分析:

略

创建一个创建哈夫曼树的方法 

该方法的目的是将一个数组的数据变成一颗哈夫曼树 

代码分析:

1.  我们先创建一个集合,并指定泛型为Node,构造方法中指定集合的大小,即数组的长度   array.length
2.  遍历数组,用增强for循环,将数组里面的元素放入构造方法中,将new出来的节点对象放入集合中
   1. 没有集合的后果
      1. 如果没有集合,直接用数组对节点类进行排序是困难的,不方便
      2. 而且直接用数组进行取节点操作的时候还得考虑覆盖的情形,效率极低
   2. 集合的好处
      1. 相关工具类中有排序的方法,方便我们去调用和管理
      2. 我们不需要考虑底层覆盖问题,直接取出即可
3. 根据思路,
   1. 先对集合进行排序,即Collection.sort(list)操作
   2. 再将最小的两个权的子树取出.即get(0),get(1),分别放入left和right辅助引用中
   3. 创建一个新节点,即新的根节点parent,其权的值等于刚取出来的权值之和
   4. 把新的根节点的左右节点分别于取出来的子树挂上
   5. 注意:由于前面两颗子树已经被取走,理论上已经不存在了,但是实际代码上没做出对应操 作时仍然存在,所以我们要调用remove()方法去删除
      1. 注意:一定要先删除下标为1的节点后删除下标为0的节点,否则最后一次删除会出现异常
      2. 最后一次第一个节点被删除,只剩下一个节点,没有下标为1的节点了
   6. 将新的父节点添加到集合中
4. 循环执行步骤3,如果集合中只剩下最后一个元素的时候,说明哈夫曼树已经完成,可以结束循环,即list.size()>0

结论

        哈夫曼树是真个压缩软件的核心部件,大家一定要学会哦 

文章知识点与官方知识档案匹配，可进一步学习相关知识算法技能树首页概览34188 人正在系统学习中