哈夫曼树的生成
哈夫曼树又叫做最优二叉树,是一种带权值路径最短的树,这种树在信息检索等方面都很重要。构造哈夫曼树的方法很多,而且你也可以构造出你自己定义的树,下面是我构造哈夫曼树的方法。
首先,把树上的每个节点定义为一个类,我的定义如下:
public class treeNode { //定义节点的属性,下面是必须有的,你也可以根据需呀定义更多 private treeNode parent; //上一个节点(父节点) private treeNode childLeft; //子节点为左节点 private treeNode childRight; //子节点的为右节点 private int value;//该节点的权值,主要是根据它来构造树 //重载构造方法,在创建对象时必须传入value数据 public treeNode(int value){ this.value=value; } //设置是一个父节点的方法(即上一个节点) public void setParent(treeNode parent){ this.parent=parent; } ///获得上一个节点的方法 public treeNode getParent(){ return parent; } //设置子节点(左节点)的方法 public void setChildLeft(treeNode childLeft){ this.childLeft=childLeft; } //获得子节点(左节点)的方法 public treeNode getChildLeft(){ return childLeft; } //设置子节点(左节点)的方法 public void setChildRight(treeNode childRight){ this.childRight=childRight; } //获得子节点(左节点)的方法 public treeNode getChildRight(){ return childRight; } //设置权值的方法 public void setValue(int value){ this.value=value; } //获得权值的方法 public int getValue(){ return value; } }
****************************************************
节点类定义好了之后,就可以开始建立树了,这里要说的是,我们是通过已知的权值创建的节点只用作这个树的叶节点。根据这点,下面是我创建树的思想,
首先根据给定的权值数组,把它进行排序,先排序可以减少后面再进行的工作,排序的方法很多,可以用冒泡排序法,也可以用插入排序法,或者其他的,我用的是冒泡排序法,而且在排序的过程中,同时创建出节点对象,并且把它们装入队列中。代码如下:
//冒泡法对数组进行排序,即对权值进行排序,按从小到大进行排序,同时封装成节点,装入队列中,list是创建的一个队列对象 public void sortValue(int[] array){ //冒泡排序的过程 for(int i=0;i<array.length;i++){ for(int j=i+1;j<array.length;j++){ if(array[i]>array[j]){//比较大小 int temp=array[i]; array[i]=array[j]; array[j]=temp; } } //创建节点对象,并把它装入队列中 treeNode node=new treeNode(array[i]); list.add(node); } } //冒泡法对数组进行排序,即对权值进行排序,按从小到大进行排序,同时封装成节点,装入队列中,list是创建的一个队列对象 public void sortValue(int[] array){ //冒泡排序的过程 for(int i=0;i<array.length;i++){ for(int j=i+1;j<array.length;j++){ if(array[i]>array[j]){//比较大小 int temp=array[i]; array[i]=array[j]; array[j]=temp
**************************************************
建树的过程很简单,就是从队列中取出权值最小的两个节点,然后再根据这两个节点创建它们的上一个节点。然后再将这个节点放入队列中(时放入相应的位置),建树的代码如下:
//生成哈夫曼树的方法 public void createTree(int[] array){ //调用sortValue方法,将叶子节点进行封装 this.sortValue(array); //根据哈夫曼编码的原理,建立哈夫曼树 while(list.size()>1){//节点树大于一时,才进行如下操作 treeNode leftnode=list.remove(0);//获得左节点 treeNode rightnode=list.remove(0);//获得右节点 //根据这两个节点,创建它们的父节点 int value=leftnode.getValue()+rightnode.getValue(); treeNode parentnode=new treeNode(value); //给这三个节点建立对应的关系 leftnode.setParent(parentnode); rightnode.setParent(parentnode); parentnode.setChildLeft(leftnode); parentnode.setChildRight(rightnode); //将这两个节点的父节点装入队列中,并对它们进行排列 this.sortAgain(parentnode); } }
*******************************************************
上面的sortAgain方法就是如何将新节点放入相应的位置,具体代码如下:
public void sortAgain(treeNode newnode){ //因为里面的节点已经排好序了,所以只是将新节点插入对应的位置就可以了 int size=list.size(); if(size>0){//里面至少有一个节点才能进行比较 if(newnode.getValue()>list.get(size-1).getValue()){//如果要加入的节点的权值大于队列中最后一个节点的权值,则放到最后面 list.add(newnode); }else{//否则才去进行比较 for(int i=0;i<list.size();i++){ treeNode node=list.get(i);//按顺序得到节点 if(newnode.getValue()<=node.getValue()){//比较它们的权值 list.add(i, newnode);//将新节点添加到指定的位置 break;//结束循环 } } } }else{//否则直接加进去 list.add(newnode); } }
}这个方法很简单,但是它能够确保新添加的节点是位于节点在左边,即代分枝的节点总在左边。
相关推荐
哈夫曼树
数据结构课设——HuffMan编码和解码(Java)。根据要编码的文件中字符出现的频率生成对应的哈夫曼编码;得到采用哈夫曼编码后的目标文件,并保存;根据要解码的文件对应的哈夫曼码表对文件进行解码; 得到解码后的...
所谓哈夫曼树就是要求最小加权路径长度,这是什么意思呢?简而言之,就是要所有的节点对应的路径长度(高度-1)乘以该节点的权值,然后保证这些结果之和最小。下面这篇文章就给大家详细介绍
哈夫曼树和哈夫曼编码的Java实现,供新手学习使用。希望能给需要的人以帮助。
哈夫曼编码、哈夫曼树构建、哈夫曼树Java实现.docx哈夫曼编码、哈夫曼树构建、哈夫曼树Java实现.docx
实现哈夫曼树
基于JAVA实现的Huffman哈夫曼树编码与解码
哈夫曼树实现的压缩工具源代码,用netbeans导入可以看见源代码,仅供学习参考
前面一篇图文详解JAVA实现哈夫曼树对哈夫曼树的原理与java实现方法做了较为详尽的描述,这里再来看看C++实现方法。 具体代码如下: #include using namespace std; #if !defined(_HUFFMANTREE_H_) #define _...
哈夫曼编码的原理是构建一棵哈夫曼树(Huffman Tree),也称为最优二叉树,树的每个叶子节点表示一个字符,字符的频率(或权重)作为叶子节点的权值,从根节点到叶子节点的路径上的左分支用0表示,右分支用1表示,...
NULL 博文链接:https://128kj.iteye.com/blog/1637940
大家都知道哈夫曼是用来做压缩解压的算法,通过...你也可以说是“每个字符出现的次数”或者“哈夫曼树”,不管是“每个字符出现的次数”还是“哈夫曼树”,你都需要通过他们得到“每个字符的编码”之后才能进行解码。
自适应哈弗曼Java版实现,内有可执行文件
哈夫曼树的基本创建,同时还有哈夫曼编码的创建,用了动态申请内存空间的知识
java基础复习笔记数据结构哈夫曼树,讲述了哈夫曼树的原理和java实现。
排序二叉树 AVL树 哈夫曼树增删改查Java实现
主要为大家介绍了java哈夫曼树实例代码,感兴趣的小伙伴们可以参考一下
这样的数据结构课程设计的设计和实现过程,绝对让你对把它实现的开发者佩服,有了它,你对编程的兴趣和感受到它的强大也会倍增,有了它,你的数据结构课程设计之 哈夫曼树的应用 的实现也不会感到困难,绝不再是一个...
严蔚敏奶奶数据结构一书中,第六章树,哈夫曼编码的实现程序
哈夫曼树的Java实现, 哈夫曼树又叫做最优二叉树,是一种带权值路径最短的树,这种树在信息检索等方面都很重要。