哈夫曼编码（java版+详细代码）

哈夫曼编码：

根据数据出现的频率对数据进行编码，从而压缩原始数据。

例如对一个文本we年其中各种字符出现的次数;

a:10

b:20

c:40

d:80

我们可以把啊，abcd，设为00,01,10,11，但是这样没有考虑权值频率。

哈夫曼编码采用的是贪心算法，使出现频率最高的编码路径最短，这样总路径就最短。

实现如下;

首先生成一颗哈夫曼树，每次生成过程中，选出频率最小的两个构成一个新的父节点，父节点是这两个节点频率的和。

这样频率小的会在最底层，总路径也就越短。

生成编码的时候，从根节点出发，向左遍历则添加0，向右遍历添加1.直到遍历到叶子节点。

代码如下;

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

public class Huffman {
    public class Node implements Comparable<Node>{
        char ch;//传入节点
        int freq;//节点频率
        boolean isLeaf;//是否为叶子节点
        Node left,right;//左右子节点、
        //初始化一个节点
    public Node(char ch,int freq){
        this.ch=ch;
        this.freq=freq;
        isLeaf=true;
    }
    //初始化非叶子节点
    public Node(Node left,Node right,int freq){
        this.left=left;
        this.right=right;
        this.freq=freq;
        isLeaf=false;
    }
        @Override
        public int compareTo(Node o) {
            return this.freq-o.freq;
        }
    }
    public Map<Character,String> encode(Map<Character,Integer> frequencyForChar){
        PriorityQueue<Node> priorityQueue=new PriorityQueue<>();
        for(Character c:frequencyForChar.keySet()){
            priorityQueue.add(new Node(c,frequencyForChar.get(c)));
        }
        while (priorityQueue.size()!=1){
            Node node1=priorityQueue.poll();
            Node node2=priorityQueue.poll();
            priorityQueue.add(new Node(node1,node2,node1.freq+node2.freq));
        }
        return encode(priorityQueue.poll());
    }

    private Map<Character,String> encode(Node root) {
        Map<Character, String> encodingForChar = new HashMap<>();
        encode(root, "", encodingForChar);
        return encodingForChar;
    }

    private void encode(Node node, String encoding, Map<Character,String> encodingForChar) {
        if (node.isLeaf) {
            encodingForChar.put(node.ch, encoding);
            return;
        }
        encode(node.left, encoding + '0', encodingForChar);
        encode(node.right, encoding + '1', encodingForChar);
    }
    


}