简单哈夫曼树

一、基本概念

1. 哈夫曼树即最优二叉树，是只有叶节点才能存放数据，且使所有数据到根节点的距离与
  其权值乘积和最小的二叉树。 

  2.建立哈夫曼树的步骤：
     step1.从所有数据中找到权值最小的两个数据A和B,把A和B作为两个子节点，建立
     一个二叉树，设它们的父节点为C，C的权值是A和B权值的和。
     step2.在原来的所有数据中用C替换A和B，重复step1。
     step3.直到只剩下一个数据时哈夫曼树完成。
    
二、用程序获得哈夫曼树
1.建立结点类
         哈夫曼树中的结点包括数据权值（int型）、左侧子结点（结点型）、右侧子结点（结点型）
对于按字符串中字符出现次数画哈夫曼树，结点基本包括以下几个属性(字符、权值、左结点、右结点)

 private char c;
	private int weight;
	private HfmNode left;
	private HfmNode right;

2.把权值形成的数组转化为结点组成的数组（如果是在一个字符串中，以每个字符出现的次数作为权值建立哈夫曼树，需要新建一个字符串用于存储出现的字符并计算每个字符的权值）

 private String content;//the original string
	private String simContent;//the simplified string which consists of the 
	                          //letter content does but every letter just 
	                          //appears once
	private static HfmNode[] nodes;//the array saving the nodes
/**
	 * traverse the content,use the letter that content consists of to create a
	 * new string simContent,and in simContent does every letter just appear once
	 */
	public void simplifyContent(){
		simContent="";
		for(int i=0;i<content.length();i++){
			char letter=content.charAt(i);
			if(simContent.indexOf(letter)==-1){
				simContent+=letter;
				
			}
		}
	}
	/**
	 * use the letter simContent consists of to create a array
	 */
	public void toCharArray(){
		nodes=new HfmNode[simContent.length()];
		for(int i=0;i<simContent.length();i++){
			char letter=simContent.charAt(i);
			HfmNode node=new HfmNode(letter);
			nodes[i]=node;
		}
	}
	/**
	 * count the frequency every letter in simContent appears,and set the 
	 * weight of each HfmNode in nodes[]
	 */
	public void countLetter(){
		for(int i=0;i<simContent.length();i++){
			int count=0;
			char letter1=simContent.charAt(i);
			for(int j=0;j<content.length();j++){
				char letter2=content.charAt(j);
				if(letter1==letter2)
					count++;
			}
			nodes[i].setWeight(count);
		}
	}

3.用结点型数组建立哈夫曼树，建立过程中，每次选择权值最小的两个数据时都要进行排序

/**
	 * sort the elements in nodes[] according to the value of each HfmNode's
	 * weight 
	 */
	public void sortNodeWeight(){
		for(int i=0;i<nodes.length;i++){
			for(int j=i+1;j<nodes.length;j++){
				if(nodes[i].getWeight()>nodes[j].getWeight()){
					HfmNode tem=new HfmNode();
					tem=nodes[i];
					nodes[i]=nodes[j];
					nodes[j]=tem;
				}
			}
		}
	}
	
	/**
	 * create a tree
	 * step1.find the two smallest weights,make their node as the sub-nodes,
	 * then build a binary tree ,the weight of this binary tree's root is the 
	 * sum of the two smallest weights' values
	 * step2.the root of this new binary tree takes place of the two former
	 * nodes,regard the root as a member of nodes[],then repeat step1 until 
	 * there is only one node in nodes[]
	 */
	public HfmNode createHfmTree(){
		while(nodes.length>1){
			this.sortNodeWeight();
			HfmNode root=new HfmNode(nodes[0].getWeight()+nodes[1].getWeight());
			root.setLeft(nodes[0]);
			root.setRight(nodes[1]);
			
			HfmNode[] newNodes=new HfmNode[nodes.length-1];
			newNodes[0]=root;
			for(int i=0;i<nodes.length-2;i++){
				newNodes[i+1]=nodes[i+2];
			}
			nodes=newNodes;
		}
		return nodes[0];
	}

4.打印出每个数据的哈夫曼编码

/**
	 * traverse the HfmTree and print the code of every node
	 * @param n:parent node
	 * @param code:HfmCode
	 */
	public void printHfmTreeCode(HfmNode n,String code){
		if(n.getLeft()==null&&n.getRight()==null){
			System.out.println("the weight of "+n.getC()+" is "+
		n.getWeight()+",and its HfmCode is "+code);
		}else 
			if(n.getLeft()!=null){
				printHfmTreeCode(n.getLeft(),code+"0");
			}
		    if(n.getRight()!=null){
			    printHfmTreeCode(n.getRight(),code+"1");
		    }
	}
	

5.打印出哈夫曼树图形
哈夫曼图形绘出的方法和打印编码的方法类似，最终可以得到下图所示的哈弗曼图形