哈弗曼树定义

给定 N 个权值作为 N 个叶子结点，构造一棵二叉树，若该树的带权路径长度（WPL）达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

结点的带权路径长度：从根到该结点的路径长度与该结点的权值乘积。
树的带权路径长度：树中所有叶子结点的带权路径长度之和，通常记为 WPL。

哈弗曼树的构建过程：
在一个二叉树的权的集合中，取出根结点权值最小的两颗二叉树，组成一颗新的二叉树，前面取出的两颗二叉树是新二叉树的两个子树，根结点的权值是前两个取出的两颗二叉树的根结点的权值之和。

哈弗曼树示例

给出每个结点的权值，如下：

首先将权值排序，（每个元素相当于一颗只有根结点的二叉树）

取出权值最小的两个二叉树，将它们合并为一个新的二叉树（相加后的权值再放入原来的权值集合中），如图 3 和 5 合并成为了 8，并放入权值集合中：

7 和 8 合并成为了 15，放入权值集合中：

8 和 11 合并成为了 19，放入权值集合中：

14 和 15 合并成为了 29，放入权值集合中：

19 和 23 合并成了 42，放入权值集合中：

29 和 29 合并成了 58，放入集合中：

42 和 58 合并成了100，最后形成了如下二叉树，即哈弗曼树。

哈弗曼树代码实现

二叉树的节点代码：实现了 Comparable 接口，实现对类的比较大小（compareTo () 方法），实现 toString() 方便输出结果。

public class Node implements Comparable<Node> {
    int value;
    Node left;
    Node right;
    public Node(int value){
        this.value = value;
    }

    @Override
    public int compareTo(Node o) {
        return -(this.value - o.value);
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }
}

创建赫夫曼树代码：

 // 创建赫夫曼树，返回赫夫曼树的根结点的权值
    public static Node createHuffmanTree(int [] arr){
        List<Node> nodes = new ArrayList<>(); // 先使用数组中所有的元素创建若干个二叉树（只有一个节点）
        for (int value: arr){
            nodes.add(new Node(value));
        }
        while (nodes.size() > 1){ // 循环处理
            Collections.sort(nodes); // 降序排序
            // 取出权值最小的两个二叉树
            Node left = nodes.get(nodes.size() - 1); // 权值最小的二叉树
            Node right = nodes.get(nodes.size() - 2); // 权值次小的二叉树
            Node parent = new Node(left.value + right.value);  // 创建一个新的二叉树
            // 把取出来的两个二叉树移除
            nodes.remove(left);
            nodes.remove(right);
            nodes.add(parent);// 放入原来的二叉树集合中
        }
        return nodes.get(0); // 最后权值集合中，只剩一个权值，即构建的赫夫曼树的根的权值。
    }

测试案例：

public static void main(String[] args) {
    int [] arr = {3, 7, 8, 29, 5, 11, 23, 14};
    Node node = createHuffmanTree(arr);
    System.out.println(node);
}

运行效果：构建了一棵根的权为100的二叉树，此时整个权值集合中仅剩根的权值，所以输出为 100 。

Node{value=100}