哈夫曼树操作

树节点

public class TreeNode<T> {
    private T data;
    private TreeNode<T> left;
    private TreeNode<T> right;

    public T getData() {
        return data;
    }

    public void setData(T data) {
        this.data = data;
    }

    public TreeNode<T> getLeft() {
        return left;
    }

    public void setLeft(TreeNode<T> left) {
        this.left = left;
    }

    public TreeNode<T> getRight() {
        return right;
    }

    public void setRight(TreeNode<T> right) {
        this.right = right;
    }
}

创建哈夫曼树（最优二叉树）

public static TreeNode createHuffmanTree(int[] arr) {

    ArrayList<TreeNode<Integer>> list = new ArrayList<>();

    for (int value : arr) {
        TreeNode<Integer> node = new TreeNode<>();
        node.setData(value);
        list.add(node);
    }

    while (list.size() > 1) {
        /**
         * 将所有节点按照节点的权升序排序
         */
        Collections.sort(list, Comparator.comparingInt(TreeNode::getData));

        TreeNode<Integer> left = list.get(0);
        TreeNode<Integer> right = list.get(1);
        TreeNode<Integer> node = new TreeNode<>();
        node.setData(left.getData() + right.getData());
        node.setLeft(left);
        node.setRight(right);

        list.remove(left);
        list.remove(right);
        list.add(node);
    }
    return list.get(0);
}