哈夫曼树的构造和编码

时间:2021-10-30 22:46:24

看了半天,写出了属于自己的代码。不正之处请指出

public class Haffman {
 static class MyNode{
 String code="";
 int weight;
 Character character;
 MyNode left;
 MyNode right;
 public MyNode(Character character,int weight){
 this.weight=weight;
 this.character=character;
 }
 }
public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        while(scanner.hasNext()){
         
        String string=scanner.next();
        MyNode root=create(string);
        visit(root);
             getHalmanCode(root);
        }
}    
public static MyNode create(String string){

  char[]characters=string.toCharArray();
    HashMap<Character,Integer>hashMap=new HashMap<Character, Integer>();
    for (int i = 0; i < characters.length; i++) {
    if (hashMap.containsKey(characters[i])) {
hashMap.put(characters[i],hashMap.get(characters[i])+1);
}else {
hashMap.put(characters[i], 1);
}
}
         ArrayList<MyNode>nodes=new ArrayList<Haffman.MyNode>();
         for (char key:hashMap.keySet()) {
nodes.add(new MyNode(key,hashMap.get(key)));
}
         while(true){
        if (nodes.size()<=1) {
break;
}
        Collections.sort(nodes, new Comparator<MyNode>() {


@Override
public int compare(MyNode o1, MyNode o2) {
// TODO Auto-generated method stub
 if (o1.weight==o2.weight) {
}

return o1.weight-o2.weight;
}
});
            MyNode minNode=nodes.get(0);
            MyNode sNode=nodes.get(1);
          nodes.remove(minNode);
        nodes.remove(sNode);
        MyNode newNode=new MyNode(null, minNode.weight+sNode.weight);
        newNode.left=minNode;
        newNode.right=sNode;
        nodes.add(newNode);
         }
return nodes.get(0);
}
public static void visit(MyNode root){
if (root!=null) {
 Queue<MyNode>myNodes=new LinkedList<Haffman.MyNode>();
 myNodes.offer(root);
 while(!myNodes.isEmpty()){
 MyNode currentNode=myNodes.poll();
 System.out.print(currentNode.weight+" ");
 
 if (currentNode.left!=null) {
myNodes.offer(currentNode.left);

}
 if (currentNode.right!=null) {

 myNodes.offer(currentNode.right);
}
 }
}
System.out.println();
}
public static void getHalmanCode(MyNode root)
    {
         if (root==null) {
return ;
}
            Queue<MyNode>queue=new LinkedList<Haffman.MyNode>();
            queue.offer(root);

//层次遍历进行编码的过程
            while(!queue.isEmpty()){
           
            MyNode currentNode=queue.poll();
           
            if (currentNode.left!=null) {

            if (currentNode.left.character==null) {

             currentNode.left.code=currentNode.code+"0";
             queue.offer(currentNode.left);
}else {
//说明是编码的字符,也即是叶子节点
System.out.println(currentNode.left.character+":"+currentNode.code+"0");
}
}
            
            if (currentNode.right!=null) {
if (currentNode.right.character==null) {
currentNode.right.code=currentNode.code+"1";
queue.offer(currentNode.right);
}else {

  System.out.println(currentNode.right.character+":"+currentNode.code+"1");
}
           
           
}
           
            }

    }


}