哈夫曼树的建立

mrzhufeng

浏览: 8977 次
性别:
来自: 安徽

最近访客更多访客>>

谷歌7788

13650731644

tannotour

java_ncb

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

J#数据结构 C C++C#

哈夫曼算法一般用来实现数据压缩，以另外一种规则存储数据，从而达到压缩的功能。

以下是我编写的一个哈夫曼树的例子：

程序描述：1.传入一个字符串，将之分解，得到每个字符的个数，个数即为权值

2.将每一个字符和他的权值传入一个HFMNode对象中，再将该对象传入一个队列中

3.将队列中的HFMNode对象按权值大小排序，每次取其中权值最小的两个对象，生成一个二叉树，

向array中删除这两个权值最小的节点，同时添加该两对象的父节点

4.编码按规则：从根节点开始，向左走一步编码加+1，向右走一步编码+0

以下为源码：

哈夫曼节点的类

package tree;

public class HFMNode {

//节点一共有三种：
//1.根节点          根节点没有父节点
//2.叶节点          没有子节点
//3.中间节点     有父节点和子节点
private HFMNode parent ;
private HFMNode leftChild ;
private HFMNode rightChild;
private char s ;//节点所储存的字符
private int weight=0 ;//所储存节点的权值
private String code="" ;//字符对应的哈夫曼编码

public void setParent(HFMNode parent){
   this.parent = parent ;
}
public HFMNode getParent(){
   return this.parent ;
}



public void setLeftChild(HFMNode leftChild){
   this.leftChild = leftChild ;
}
public HFMNode getLeftChild(){
   return this.leftChild ;
}



public void setRightChild(HFMNode rightChild){
   this.rightChild = rightChild ;
}
public HFMNode getRightChild(){
   return this.rightChild ;
}



public void setWeight(int weight){
   this.weight = weight ;
}
public int getWeight(){
   return this.weight ;
}



public void setChar(char s){
   this.s = s ;
}
public char getChar(){
   return this.s ;
}



public void setCode(String code){
   this.code = code ;
}
public String getCode(){
   return this.code ;
}
}

哈夫曼树的类

package tree;

import java.util.ArrayList;

public class ConstructHFM {

private String data ;//传入的字符串
private ArrayList<HFMNode> array = new ArrayList<HFMNode>();
private ArrayList<HFMNode> nodeArray = new ArrayList<HFMNode>();//储存所有的节点


public ConstructHFM(String data){
  this.data = data ;
}
   /**

*得到字符串的编码

    */
public void getStringCode(){
  this.setTreeNode();
  this.sortAndConsTree();
  this.setEveryCharCode(array.get(0));
  String allCode = this.getAllCode();
  System.out.println("*******************************************************");
  System.out.println(data+"的哈夫曼编码是："+allCode);
}


/**
* 得到不同的字符总数，
* 将每一个字符和他的权值传入一个HFMNode对象中，
* 将此对象添加入队列中
*/
public void setTreeNode(){
  char[] s = data.toCharArray();
  int[] charCount = new int[s.length];//与字符数组相对应，记录对应字符的个数
  for(int i=0 ;i<charCount.length ;i++){
   charCount[i] = 1 ;
  }

  //得到字符的数目，以及每个字符的个数
  for(int i=0 ; i<s.length ;i++){
   for(int j=0 ; j<i ;j++){
    if(s[i]==s[j]){
     charCount[j]++;
     charCount[i]=0;
     break;
    }
   }
  }

  //将字符传入及节点对象
  for(int i=0 ;i<s.length ;i++){
   if(charCount[i]!=0){
    HFMNode h = new HFMNode();
    h.setChar(s[i]) ;
    h.setWeight(charCount[i]);
    array.add(h);
    nodeArray.add(h);
   }
  }
}


/**
* 将队列array中的每个HFMNode对象按权值排序，
* 取得最后两个对象生成二叉树，
* 删除这2个节点，添加其构成的父节点
* 且当array中只有一个元素时，该元素为根节点
*/
public void sortAndConsTree(){
  while(array.size()>=2){//冒泡排序
   for(int i=0;i<array.size();i++){
    HFMNode tem = array.get(i) ;
    for(int j=i+1;j<array.size();j++){
     if(array.get(j).getWeight()>tem.getWeight()){
      array.set(i, array.get(j));
      array.set(j, tem);
      tem = array.get(i);
     }
    }
   }

   HFMNode parent = new HFMNode();
   int len = array.size();
   HFMNode last = array.get(len-1) ;
   HFMNode lastSecond = array.get(len-2);
   parent.setLeftChild(last);
   last.setParent(parent);
   parent.setRightChild(lastSecond);
   lastSecond.setParent(parent);
   int leftWeight = last.getWeight() ;
   int rightWeight = lastSecond.getWeight() ;
   parent.setWeight(leftWeight + rightWeight);
   array.remove(len-1);
   array.remove(len-2);
   array.add(parent);
   nodeArray.add(parent);
  }
}


/**
* 打印每个字符的哈夫曼编码
* 从根节点开始，向左走一步编码为1，向右为0
*/
public void setEveryCharCode(HFMNode node){

  if(node.getLeftChild()!=null&&node.getRightChild()!=null){//判断为叶节点
   node.getLeftChild().setCode(node.getCode() + 1);
   node.getRightChild().setCode(node.getCode() + 0);
   setEveryCharCode(node.getLeftChild());
   setEveryCharCode(node.getRightChild());
  }
}


/**
* 得到字符串的编码
*/
public String getAllCode(){

  //按权值顺序打印所有叶节点的字符和编码
  for(int i=0;i<nodeArray.size();i++){
   HFMNode tem = nodeArray.get(i);
   for(int j=i+1;j<nodeArray.size();j++){
    if(nodeArray.get(j).getWeight()>tem.getWeight()){
     nodeArray.set(i, nodeArray.get(j));
     nodeArray.set(j, tem);
     tem = nodeArray.get(i);
    }
   }
  }
  //打印所有的字符的HFM编码
  System.out.println("******************以下是传入字符串的权值和哈夫曼编码");
  for(int j=0 ;j<nodeArray.size();j++){
   HFMNode h = nodeArray.get(j);
   if(h.getChar()!='\u0000'){//char型变量的默认值为'\u0000'
    System.out.println(h.getChar()+"的权值："+h.getWeight()+" 哈夫曼编码："+h.getCode());
   }
  }
  System.out.println("*******************以下是生成的哈夫曼树的结构");
  //打印生成HFM树的结构
  for(int k=0;k<nodeArray.size();k++){
   HFMNode hfm = nodeArray.get(k);
   if(hfm.getParent()==null){
    System.out.println("第"+k+"个节点为根节点，其权值为："+hfm.getWeight());
   }
   else if(hfm.getLeftChild()==null&&hfm.getRightChild()==null){
    System.out.println("第"+k+"个节点为叶节点    字符为："+hfm.getChar()+" 权值："+hfm.getWeight()+" 哈夫曼编码为："+hfm.getCode());
   }
   else{
    System.out.println("第"+k+"个节点为中间节点，其权值为："+hfm.getWeight());
   }
  }

  String allCode="" ;
  char[] c = data.toCharArray();

  for(int i=0;i<c.length;i++){
   for(int j=0;j<nodeArray.size();j++){//nodeArray中储存有所有的节点,包括根节点和中间节点
    if(c[i]==nodeArray.get(j).getChar()){
     allCode+=nodeArray.get(j).getCode();
     break ;
    }
   }
  }
  return allCode ;
}

public ArrayList<HFMNode> getArray(){
  return this.array ;
}

}

  测试类

测试描述：传入一个字符串 String s = "abbcccddddeeeeeffffff"

打印个字符的权值和哈夫曼编码，以及生成哈夫曼树的结构

package tree;

public class TestApp {
public static void main(String[] args){
  String s = "abbcccddddeeeeeffffff" ;
  ConstructHFM h = new ConstructHFM(s);
  h.getStringCode();
}
}

测试结果

******************以下是传入字符串的权值和哈夫曼编码
f的权值：6 哈夫曼编码：01
e的权值：5 哈夫曼编码：10
d的权值：4 哈夫曼编码：11
c的权值：3 哈夫曼编码：000
b的权值：2 哈夫曼编码：0010
a的权值：1 哈夫曼编码：0011
*******************以下是生成的哈夫曼树的结构
第0个节点为根节点，其权值为：21
第1个节点为中间节点，其权值为：12
第2个节点为中间节点，其权值为：9
第3个节点为中间节点，其权值为：6
第4个节点为叶节点    字符为：f 权值：6 哈夫曼编码为：01
第5个节点为叶节点    字符为：e 权值：5 哈夫曼编码为：10
第6个节点为叶节点    字符为：d 权值：4 哈夫曼编码为：11
第7个节点为叶节点    字符为：c 权值：3 哈夫曼编码为：000
第8个节点为中间节点，其权值为：3
第9个节点为叶节点    字符为：b 权值：2 哈夫曼编码为：0010
第10个节点为叶节点    字符为：a 权值：1 哈夫曼编码为：0011
*******************************************************
abbcccddddeeeeeffffff的哈夫曼编码是：001100100010000000000111111111010101010010101010101