树节点
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);
}
