最优二叉树java算法

最优二叉树，也称为哈夫曼树，是一种带权路径长度最短的二叉树。Java中实现最优二叉树的算法可以使用贪心算法，具体步骤如下：

1. 将所有节点按照权值从小到大排序。
2. 取出权值最小的两个节点作为左右子节点，构建一个新的父节点，父节点的权值为左右子节点的权值之和。
3. 将新构建的父节点插入到原来的节点集合中，并删除原来的两个子节点。
4. 重复步骤2和3，直到只剩下一个节点为止。

以下是Java代码实现：

import java.util.*;

public class HuffmanTree {
    private Node root;

    private static class Node implements Comparable<Node> {
        int weight;
        Node left;
        Node right;

        Node(int weight) {
            this.weight = weight;
        }

        boolean isLeaf() {
            return left == null && right == null;
        }

        @Override
        public int compareTo(Node o) {
            return Integer.compare(weight, o.weight);
        }
    }

    public HuffmanTree(int[] weights) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        for (int weight : weights) {
            pq.offer(new Node(weight));
        }
        while (pq.size() > 1) {
            Node left = pq.poll();
            Node right = pq.poll();
            Node parent = new Node(left.weight + right.weight);
            parent.left = left;
            parent.right = right;
            pq.offer(parent);
        }
        root = pq.poll();
    }

    public Map<Integer, String> getCodes() {
        Map<Integer, String> codes = new HashMap<>();
        getCodes(root, "", codes);
        return codes;
    }

    private void getCodes(Node node, String code, Map<Integer, String> codes) {
        if (node.isLeaf()) {
            codes.put(node.weight, code);
        } else {
            getCodes(node.left, code + "0", codes);
            getCodes(node.right, code + "1", codes);
        }
    }
}

使用示例：

int[] weights = {5, 2, 7, 4, 1};
HuffmanTree tree = new HuffmanTree(weights);
Map<Integer, String> codes = tree.getCodes();
for (Map.Entry<Integer, String> entry : codes.entrySet()) {
    System.out.println(entry.getKey() + ": " + entry.getValue());
}

输出结果：

1: 1100
2: 101
4: 111
5: 0
7: 100