哈夫曼树与哈夫曼编码：聪明的数据压缩技术

1、根据给定的n个权值{w1,w2,…,wn}构成n棵二叉树的集合F={T1,T2,…,Tn}，其中每棵二叉树Ti中只有一个带权为wi根结点，其左右子树均为空。
2、在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和。
3、在F中删除这两棵树，同时将新得到的二叉树加入F中。
4、重复2和3步骤，直到F只含一棵树为止。这棵树便是哈夫曼树。

/**
 * 哈夫曼树
 *
 */
public class HuffmanTree {
    public static void main(String[] args) {
        HashMap<String, Integer> hashMap = new HashMap<>(8);
        hashMap.put("A", 5);
        hashMap.put("B", 87);
        hashMap.put("C", 4);
        hashMap.put("D", 2);
        hashMap.put("E", 2);
        hashMap.put("F", 9);

        ArrayList<HuffmanTreeNode> huffmanTreeNodes = new ArrayList<>();
        for (String key : hashMap.keySet()) {
            HuffmanTreeNode huffmanTreeNode = new HuffmanTreeNode(key, hashMap.get(key));
            huffmanTreeNodes.add(huffmanTreeNode);
        }

        HuffmanTreeNode root = createTree(huffmanTreeNodes);

        printTree(root);
    }

    /**
     * 先序遍历哈夫曼树 根左右
     *
     * @param root
     */
    private static void printTree(HuffmanTreeNode root) {
        if (root == null) {
            return;
        }
        System.out.println("key:" + root.key + " weight:" + root.weight);
        printTree(root.leftChildren);
        printTree(root.rightChildren);
    }

    /**
     * 创建哈夫曼树
     *
     * @param huffmanTreeNodes
     * @return
     */
    private static HuffmanTreeNode createTree(ArrayList<HuffmanTreeNode> huffmanTreeNodes) {
        HuffmanTreeNode huffmanTreeNodeNew = null;
        while (huffmanTreeNodes.size() >= 2) {
            // 取出权值最小的两个值
            huffmanTreeNodes.sort(Comparator.comparing(o -> o.weight));
            String newKey = huffmanTreeNodes.get(0).key + huffmanTreeNodes.get(1).key;
            int newWeight = huffmanTreeNodes.get(0).weight + huffmanTreeNodes.get(1).weight;
            System.out.println(newKey + newWeight);
            huffmanTreeNodeNew = new HuffmanTreeNode(newKey, newWeight);
            huffmanTreeNodeNew.leftChildren = huffmanTreeNodes.get(0);
            huffmanTreeNodeNew.rightChildren = huffmanTreeNodes.get(1);
            huffmanTreeNodes.remove(0);
            huffmanTreeNodes.remove(1);
            huffmanTreeNodes.add(huffmanTreeNodeNew);
        }
        return huffmanTreeNodeNew;
    }

    /**
     * 哈夫曼树节点
     */
    static class HuffmanTreeNode {
        String key;
        // 权重
        Integer weight;

        HuffmanTreeNode leftChildren;

        HuffmanTreeNode rightChildren;

        public HuffmanTreeNode(String key, Integer weight) {
            this.key = key;
            this.weight = weight;
        }
    }
}