哈夫曼树构造过程：
列表里选出权重（或者出现次数）最低的两个，构成新树的左右子节点，新树父节点的权重为这两个子节点权重之和，将父节点（树）丢进列表里，重复操作，最后列表只剩一个，即哈夫曼树，所有子树的左边标0右边标1，节点的路径即哈夫曼编码；
Demo：
package testHuffman; import java.util.Comparator; import java.util.HashMap; import java.util.Map; import java.util.PriorityQueue; public class TestHuffman { public static void main(String[] args) { //优先级队列，自动排序 PriorityQueue<Node> q = new PriorityQueue<>(new Comparator<Node>() { @Override public int compare(Node o1, Node o2) { if(o1.priority == o2.priority) { return o1.n-o2.n; }else { return o1.priority - o2.priority; } } }); //初始数据 Map<String,Integer> map = new HashMap<>(); map.put("A",5); map.put("B",24); map.put("C",7); map.put("D",17); map.put("E",34); map.put("F",5); map.put("G",13); //初始数据放入队列 for(String v:map.keySet()) { System.out.println("放入队列："+v+":"+map.get(v)); q.add(new Node(map.get(v), v, null, null, 1)); } System.out.println("=队列="+q); //构造哈夫曼树 while(q.size()>1) { //取出优先级最小的两个 Node n1 = q.poll(); Node n2 = q.poll(); System.out.println("取出："+n1+n2); //构成新树 Node newNode = new Node(n1.priority+n2.priority, "("+n1.name+""+n2.name+")", n1, n2, n1.n>n2.n?n1.n+1:n2.n+1); System.out.println("放入："+newNode); //重新放入队列 q.add(newNode); System.out.println("=队列="+q); } //取出哈夫曼树 Node tree = q.poll(); Map<String, String> code_word = getTreeCode(tree); System.out.println(code_word); Map<String, String> word_code = new HashMap<>(); for(String code:code_word.keySet()) { word_code.put(code_word.get(code), code); } //测试 String msg = "DCABCFDBFABEGA"; for(String word:word_code.keySet()) { msg = msg.replaceAll(word, word_code.get(word)); } System.out.println("编码："+msg); String subCode = ""; String reMsg = ""; for(int i=0;i<msg.length();i++) { subCode += msg.substring(i, i+1); if(code_word.containsKey(subCode)) { reMsg += code_word.get(subCode); subCode = ""; } } System.out.println("消息："+reMsg); } private static Map<String,String> getTreeCode(Node root) { Map<String,String> m = new HashMap<>(); getRoad("",root,m); return m; } //构造路径，左0右1 private static Map<String,String> getRoad(String r, Node n, Map<String,String> m) { if(n.left == null) { m.put(r, n.name); }else { getRoad(r+"0", n.left, m); } if(n.right == null) { m.put(r, n.name); }else { getRoad(r+"1", n.right, m); } return m; } } class Node{ public int priority; public String name; public Node left; public Node right; public int n;//用于保存树层级，优先级相同按层级排序，每次选层级最小的两个 public Node(int priority, String name, Node left, Node right, int n) { this.priority = priority; this.name = name; this.left = left; this.right = right; this.n = n; } @Override public String toString() { return "{"+priority + ":" + name+"}"; } }结果：
同组数据产生的哈夫曼树可能不唯一，存在超过两个相同权重节点的选择问题和左右子树的位置问题；
