哈弗曼编码

国庆假期一直没时间完善自己写的哈弗曼树这一块,打印哈弗曼树的功能还没有实现,只实现了打印编码.等这些天再完善一下没实现的功能,现在浅谈一下自己写哈弗曼编码的过程.

 

1.首先,哈弗曼树要建立结点是必须要有的,先建立节点类是必要的

定义结点的属性,其次是获得该属性的set以及get方法

 

private char ch;//字符属性
private int number;//字符出现的次数相当于字符的权值
private haFuManNode left;//左子树
private haFuManNode right;//右子树

 set及get方法就不一一列举了.

 

2.完成第一步的工作后我们的结点就完成了,接下来的工作就是写哈弗曼树了.建立哈弗曼树自己的思路是,一棵树要有自己的符号,然后要有自己的权值.基于这样思路接下来的工作就是就是写权值的方法以及数据了.

 

(1)考虑权值我是根据某一个字符出现的次数然后计算出来作为该字符的权值

获得权值的方法如下:

//字符出现的次数的方法
public int getNumber(char ch,String str){
	//计数器
	int count = 0;
	//遍历字符串
	for(int i = 0;i<str.length();i++){
	//根据索引的位置返回字符
	char c = str.charAt(i);
	if(c==ch){//查到需要的字符
	count++;
	}
    }
    return count;//返回次数
}

 

(2)接下来的工作就是要将上述重复的字符串分离出来,这样便于树的建立.思路是将分离出来字符串放到节点数组中去.

1>怎样将字符串分离出来,我查找了一个方法实现如下:

private String content;//该属性为要输入的字符串,分离就是该字符串中重复的字符

//定义一个空的字符串
String empty = "";
		
//遍历所列出的字符串(属性字符串)
for(int i = 0;i<content.length();i++){
			
//索引的位置返回一个字符
char c = content.charAt(i);
//System.out.println("content的内容是: "+content);
//System.out.println("索引的字符为: "+c);
//System.out.println("-----"+content.indexOf(c));
			
//判断该字符是否重复了,重复了只写一次
if(empty.indexOf(c)==-1){
				
empty = empty + c;//放入该字符到空字符串中
System.out.println("新的字符串empty是: "+empty);
}
}

 该方法执行完毕后,组成了一个没有重复字符的新的字符串empty.

 

2>然后就是将该字符放入到结点数组中,在放入到结点数组之前还是要重复之前的工作找到指定字符的权值,找权值就是调用getNumber()的方法即可.

//遍历刚存入的字符串
		
for(int j=0;j<empty.length();j++){
			
//索引位置返回字符
			
char cha = empty.charAt(j);
			
//调用字符出现次数的方法
			
int number = getNumber(cha,content);
			
System.out.println(cha+"的权值是:　"+number);

 3>.该步就是将上述带有权值的字符放入结点数组中去.

//创建一个结点对象
haFuManNode hfmNode = new haFuManNode();
hfmNode.setCh(cha);//结点保存字符信息
hfmNode.setNumber(number);//结点中存入权值信息
//将结点的信息存入节点数组
hfmArray[j] = hfmNode;
}

 

3.建树的前提就是要知道权值的大小,该步骤就是实现结点数组的排序,实现如下:

//用来两个循环实现排序(冒泡排序)
for(int i=0;i<hf.length;i++){
    for(int j=i+1;j<hf.length;j++){
        //从小到大的顺序进行排序
      if(hf[i].getNumber() > hf[j].getNumber()){
	//定义一个中间变量
	haFuManNode middle = hf[i];
	//将权值大的放到后面
	hf[i] = hf[j];
	hf[j] = middle;
               }
       }
}

 

4.上述步骤实现完了,接下来的工作是寻找树的根节点\建树.寻根节点放在了一个whill(node.length>1){}循环中完成的,根据哈弗曼树的规则,那么接下来的方法就是两个较小的权值的结点相加,然后将新的权值保存,新的权值保存在新建的结点数组中.

实现如下:

//将结点数组重新排序
this.rank(node);
//该节点的左右子树
haFuManNode nod1 = node[0];
//System.out.println("左子树是: "+nod1);
System.out.println("左子树的权值是: "+nod1.getNumber());
haFuManNode nod2 = node[1];
//System.out.println("右子树是: "+nod2);
System.out.println("右子树的权值是:　"+nod2.getNumber());
//创建一个新的结点用于保存左右子树权值相加后的新结点
	haFuManNode nod3 = new haFuManNode();
	nod3.setLeft(nod1);
	nod3.setRight(nod2);
	nod3.setNumber(nod1.getNumber()+nod2.getNumber());//新节点权值
         System.out.println("新节点nod3的权值: "+nod3.getNumber());

 接下来就是将新的结点保存在新的结点数组中,然后将剩余的结点也添加到新建的结点数组中去

//新建一个元素个数少1的结点数组
haFuManNode [] node1 = new haFuManNode[node.length - 1];
	//将nod3存入新数组
//	nod3 = node1[0];
	node1[0] = nod3;
	//将剩余的元素放入新建的结点数组中
	for(int i=0;i<node.length-2;i++){
	node1[i+1] = node[i+2];
	}
	//将新的结点数组对象与旧的结点数组对象交换,继续进行该循环
	node = node1;
	System.out.println("重新组合的新数组的长度:　"+node.length);

 

5.哈弗曼树建好后就是打印编码了,打印编码的方法如下:

 

//打印哈弗曼树的方法
 public void printTree(haFuManNode node,String code){
  
  //找出叶结点
  if(node.getLeft() ==null && node.getRight()==null){
   
   System.out.println("字符: "+node.getCh()+" 权值是: "+node.getNumber()+" 编码是: "+code);
  }
  
  if(node.getLeft()!=null){
   printTree(node.getLeft(),code+"0");//左子树 设为0
  }
  
  if(node.getRight()!=null){
   printTree(node.getRight(),code+"1");//右子树为1
  }
 }

利用递归的思想再次调用,打印哈弗曼编码.

 //定义哈弗曼编码的规则
public void codeObey(){
		
	printTree(this.creatTree(),"");
}

  至此,哈弗曼编码就结束了,接下来就是完善我的画树这一步了.