赫夫曼树

1. 基本介绍：

二叉树

• 路径：从一个节点到达其后辈节点的通路，称为路径。通路中分支的数目称为路径长度。上面这棵二叉树，黄色的线就是50这个节点到15这个节点的路径，路径长度为3。树有n层，那么根节点到第n层节点的路径长度为(n-1)。

• 带权路径长度：就是路径长度乘以该节点的值。比如50到15的带权路径长度就是 3 * 15 = 45。

• 树的带权路径长度：所有叶子结点的带权路径长度之和，记作wpl。

• 赫夫曼树：树的带权路径长度最小的的树称为最优二叉树，也称为赫夫曼树。也就说，wpl最小的树就叫做赫夫曼树。从树的带权路径长度的定义可以知道，要想该值最小，离根节点越近的值应该越大，才能使带权路径长度最小。

给定13, 7, 8, 3这四个数作为叶子结点，构建成二叉树，部分情况如下：

二叉树

这种情况，权值为 2 * 13 + 2 * 7 + 2 * 8 + 2 * 3 = 62。

二叉树

这种情况，权值为1 * 13 + 2 * 8 + 3 * 7 + 3 * 3 = 59。

显然第二种情况权值更小，确保没有更小的情况下，这棵二叉树就叫做赫夫曼树。

2. 构建赫夫曼树：

假如现在要将13, 7, 8, 3, 29, 6, 1构建成赫夫曼树，步骤如下：

• 首先将数组升序排序；结果就是1, 3, 6, 7, 8,13, 29。

• 取出排序后的前两个数，构建成一棵二叉树，根节点为两个子节点之和；即取出1和3，构建出如下二叉树：

第一步

• 此时数组中的1和3就已经用掉了，将上一步构建的二叉树的根节点4放入数组中排序，结果就是：4, 6, 7, 8, 13, 29。

• 再从序列中取出两个数，即4和6，构建成一棵二叉树，如下图：

第二步

• 再将10放到序列中，此时的序列就是这样的：7, 8, 10, 13, 29。

• 再从序列中取出7和8，构建二叉树，如下：

第三步

• 将15放到序列中，此时序列就变成了：10, 13, 15, 29，并且此时构建出了两棵二叉树，还没关联起来，先不用急。

• 取出10和13，构建成二叉树，此时二叉树就变成了：

第四步

• 将23放到序列中，序列就变成了：15, 23, 29。

• 取出15和23，构建成二叉树，15和23是两棵树的根节点，经过这一步，两棵树就合并了：

第五步

• 现在序列中就剩下29和38了，所以将29加到这棵树上就好了，如下图：

第六步

• 经过上面的步骤，就将给定的这个序列构建成了赫夫曼树。

3. 代码实现：

/**
 * 赫夫曼树
 * @author zhu
 *
 */
public class HuffmanTree {
    
    /**
     * 构建赫夫曼树
     * @param arr
     * @return
     */
    public static Node buildHufmanTree(int[] arr) {
        // 将数组转成集合，方便增删元素
        List<Node> nodes = new ArrayList<>();
        for (int i=0; i<arr.length; i++) {
            nodes.add(new Node(arr[i]));
        }
        // 对集合进行排序
        Collections.sort(nodes);
        // 循环构建
        while (nodes.size() > 1) {
            // 取出前两个节点，构建二叉树
            Node leftNode = nodes.get(0);
            Node rightNode = nodes.get(1);
            Node parentNode = new Node(leftNode.getValue() + rightNode.getValue());
            parentNode.setLeft(leftNode);
            parentNode.setRight(rightNode);
            // 移除用掉了的元素，将parent的值添加进集合
            nodes.remove(leftNode);
            nodes.remove(rightNode);
            nodes.add(parentNode);
            // 重新排序
            Collections.sort(nodes);
        }
        // 返回赫夫曼树的根节点
        return nodes.get(0);
    }
    
    /**
     * 前序遍历
     * 
     * @param root
     */
    public static void preOrder(Node root) {
        // 先输出当前节点
        System.out.println(root.getValue());
        // 判断左子节点是否为空，不为空就递归
        if (root.getLeft() != null) {
            preOrder(root.getLeft());
        }
        // 判断右子节点是否为空，不为空就递归
        if (root.getRight() != null) {
            preOrder(root.getRight());
        }
    }
    
    /**
     * 节点内部类，实现compareble接口，方便对node排序
     * @author zhu
     *
     */
    static class Node implements Comparable<Node>{
        private int value;
        private Node left;
        private Node right;
        public Node(int val) {
            this.value = val;
        }
        public int getValue() {
            return value;
        }
        public void setValue(int value) {
            this.value = value;
        }
        public Node getLeft() {
            return left;
        }
        public void setLeft(Node left) {
            this.left = left;
        }
        public Node getRight() {
            return right;
        }
        public void setRight(Node right) {
            this.right = right;
        }
        @Override
        public String toString() {
            return "Node [value=" + value + "]";
        }
        @Override
        public int compareTo(Node o) {
            // 升序
            return this.value - o.value;
        }
    }
    
    public static void main(String[] args) {
        int[] arr = {13, 7, 8, 3, 29, 6, 1};
        Node node = buildHufmanTree(arr);
        preOrder(node);
    }

}

上面是创建赫夫曼树的完整代码，构件好之后，用前序遍历方法遍历一下，然后看看与上面图中的赫夫曼树前序遍历结果是否一致，如果一致，表示构建成功。