利用JAVA构造一棵哈夫曼树

哈夫曼树原理:

步骤:

• 统计每个字符出现的次数,放入集合中

• 每次选出次数最低的两个字符,从集合中取出来合并成一个,重新放入

• 重复步骤直到合并为一个,就是哈夫曼树

• 设置哈夫曼树的左右边对应0,1

• 遍历到叶子结点,路径就是哈夫曼编码

代码:

import java.util.HashMap;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;

public class Huffman {
    HashMap map=new HashMap<>();
    Queue que=new PriorityQueue<>();//小根堆,但放的是TreeNode,所以在TreeNode类里面写好比较器,放到队列里面自动排序
    HashMap hfm=new HashMap<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();

        Huffman x=new Huffman();
        x.getmap(s);
        
        x.hfm.forEach((c,value)->{
            System.out.println(c + ":" + value);
        });
    }

    public void getmap(String str) {
        char[] chars=str.toCharArray();
        
        //把字符的出现频率输入到Hashmap的map表中
        for (char c : chars) {
            if (!map.containsKey(c)) {
                map.put(c, 1);
            }else{
                map.put(c, map.get(c) + 1);
            }
        }
        
		//把每个节点添加到队列当中
        map.forEach((c,value)->{
            TreeNode node=new TreeNode();
            node.c=c;
            node.value=value;
            que.offer(node);
        });
		
        //构建哈夫曼树
        while (que.size() > 1) {
            TreeNode left=que.poll();//每次取出的节点都是value最小值,因为队列是PriorityQueue,最小堆队列,而且节点里面也用了比较器
            TreeNode right=que.poll();

            TreeNode parent=new TreeNode();
            parent.value=(left.value + right.value);
            parent.left=left;
            parent.right=right;

            que.offer(parent);//添加到队列里,继续进行最小值比较
        }

        TreeNode head=que.poll();//只剩一个节点
        pretraveral(head, "");

    }

    public void pretraveral(TreeNode head, String s) {
        if (head == null) {
            return;
        }
        pretraveral(head.left, s + "0");
        if (head.c != null) {//head不为空,但可能head.c为空,所以需要加个判断条件
            hfm.put(head.c, s);
        }
        pretraveral(head.right, s + "1");
    }
}

 //implements Comparable  就可以利用值去比较节点,对节点进行排序,还不是对节点的值排序且不动节点
class TreeNode implements Comparable{
    int value;
    Character c;
    TreeNode left;
    TreeNode right;

    @Override
    public int compareTo(Object o) {
        return this.value-((TreeNode)o).value;
    }
    @Override
    public String toString() {
        return "TreeNode{" +
                "value=" + value +
                ", c=" + c +
                ", left=" + left +
                ", right=" + right +
                '}';
    }
}