哈弗曼树的创建

First~~~~
  //树的节点类
public class NodeTree {
     public NodeTree left;
     public NodeTree right;
     public NodeTree parents;
     public NodeData data;
    
     //用构造器直接传入数据
     public NodeTree(NodeData data){
    this.data = data;
     }
}


Second~~~~
//数据类

public class NodeData {
public char s;
public int weight;
}


Third~~~~~
//哈弗曼树的建立
import java.util.ArrayList;
import java.util.List;
import java.util.Map;

public class TreeHFM {
   
   //创建HFM树，并返回根节点
    public NodeTree creatHFM(List<NodeTree> node){
NodeTree tem = null;
//1排序 2更新队列 3算法
while(!(node.size()<2)){
sort(node);//队列排序  从小到大
NodeTree a1 = node.remove(0);//取得最小的两个元素
NodeTree a2 = node.remove(0);
//建树
NodeData da = new NodeData();//节点对象的数据
da.weight = a1.data.weight+a2.data.weight;
NodeTree root = new NodeTree(da);//创建节点对象
root.left = a1;
root.right = a2;
a1.parents = root;
a2.parents = root;
node.add(root);//将节点放入队列
tem=root;
          }
return tem;
}

//排序     从小到大  冒泡
  public void sort(List<NodeTree> node){

for(int i=0;i<node.size();i++){
NodeTree i1 = node.get(i);
   for(int j=i+1;j<node.size();j++){
NodeTree j1 = node.get(j);
if(i1.data.weight > j1.data.weight){//如果i1小于j1，则交换
   NodeTree temp = node.get(i);
   node.set(i, node.get(j));
   node.set(j, temp);
      }
    }
           }
}
   //获得哈弗曼编码  返回   数据NodeData 与 编码String  形成映射的Map
   public Map<NodeData,String>  creatCode(NodeTree root,String code){
java.util.Map<NodeData,String> ma = new java.util.HashMap<NodeData,String>();

         if(root.left!=null){//根节点的左子树不为空，+1 到码表中

  ma.putAll(creatCode(root.left,code+"1"));

}

if(root.right!=null){//根节点的右子树不为空，+0到码表中
  ma.putAll(creatCode(root.right,code+"0"));

}

if((root.right==null)&&(root.left==null)){//如果是叶子节点，返回码表
  ma.put(root.data, code);
}

return ma;
}



//遍历打印树  格式  (char)a   011
public void printHFM(NodeTree root){//,Map<NodeData,String> ma

   if(root!=null){//先序排列
       System.out.println(root.data.weight); 
              
               NodeTree left = root.left;  
      printHFM(left);   

      NodeTree right = root.right;   
      printHFM(right);   
   }
}

//生成一个模拟数据     返回 存放树节点的队列
public List<NodeTree> datacreat(){
List<NodeTree> node = new ArrayList<NodeTree>();
for(int i=0;i<10;i++){
NodeData da = new NodeData();
da.s = (char)(97+i);
da.weight = (10-i)*2;
NodeTree no = new NodeTree(da);
node.add(no);
}
return node;
}


public static void main(String[] args) {
TreeHFM tr = new TreeHFM();

List<NodeTree> node = tr.datacreat();

NodeTree root = tr.creatHFM(node);
tr.printHFM(root);

//遍历码表
String code = "";
java.util.Map<NodeData,String> ma = tr.creatCode(root, code);
java.util.Set<NodeData> se = ma.keySet();
java.util.Iterator<NodeData> it = se.iterator();

while(it.hasNext()){
NodeData no = it.next();
String code1 = ma.get(no);
System.out.println("字节是："+no.s + "    weight是："+no.weight +"码表为："+code1);
}