java实现哈夫曼树

                       哈夫曼树的生成
哈夫曼树又叫做最优二叉树，是一种带权值路径最短的树，这种树在信息检索等方面都很重要。构造哈夫曼树的方法很多，而且你也可以构造出你自己定义的树，下面是我构造哈夫曼树的方法。
首先，把树上的每个节点定义为一个类，我的定义如下：

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); 
  } 
}

 }这个方法很简单，但是它能够确保新添加的节点是位于节点在左边，即代分枝的节点总在左边。