赫夫曼树 | 半卷书

赫夫曼树

赫夫曼树,又称最优二叉树：它是n个带权叶子结点构成的所有二叉树中,带权路径长度最小的二叉树.

树的带权路径长度 WPL：树种所有叶子结点的带权路径长度之和.

叶子节点的带权路径值：叶子结点的权值乘以根节点到叶子结点的路径(层)

节点定义：

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 class HuffmanTree {

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

    public static Node huffmanTree(int[] arr) {
        List<Node> list=new ArrayList<>();
        //构建树
        for(int value:arr) {
            list.add(new Node(value));
        }
        while(list.size()>1) {
            //排序
            Collections.sort(list);
            //查找出最小的树
            Node left=list.get(list.size()-1);
            //查找出次小的树
            Node right=list.get(list.size()-2);
            //组成新树
            Node newNode=new Node(left.value+right.value);
            list.remove(left);
            list.remove(right);
            //添加新树
            list.add(newNode);
        }
        return list.get(0);
    }
}