接口--Comparable接口【哈夫曼树】

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

    @Override
    public String toString() {
        return "[value=" + value + "]";
    }

    public int compareTo(Node o) {
//        return this.value - o.value;//从小到大
        return -(this.value - o.value);//从大到小
    }
    
    public int getValue() {
        return value;
    }
    
}

public class TestHaffmanTree {

    public static void main(String[] args) {
        int[] arr = {3,7,8,29,5,11,23,14};
        Node nodeHaffman = creatHaffman(arr);
        System.out.println(nodeHaffman);
    }
    
    public static Node creatHaffman(int[] arr) {
        //先使用数组中的所有元素创建若干二叉树
        List<Node> list = new ArrayList<Node>();
        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 parent = new Node(left.getValue()+right.getValue());
            //把原来的两个二叉树移除
            list.remove(left);
            list.remove(right);
            //将新的二叉树放入list中
            list.add(parent);
        }
        //System.out.println(list.size());
        return list.get(0);//剩下的最后那一个就是哈夫曼树了
    }

}