赫夫曼树

/**
 * 赫夫曼树
 * @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);
    }

}