哈夫曼树Java实现

哈夫曼树是一种带权路径长度最短的树，常用于数据压缩。在Java中，可以通过构建哈夫曼树来实现哈夫曼编码。下面是一个简单的哈夫曼树Java实现的步骤：

1. 定义一个Node类作为哈夫曼树的节点，包含权值和左右子节点等属性。
2. 构建哈夫曼树，可以通过优先队列（PriorityQueue）来实现。首先将所有节点加入队列中，然后每次取出权值最小的两个节点，合并成一个新节点，再将新节点加入队列中，直到队列中只剩下一个节点，即为哈夫曼树的根节点。
3. 根据哈夫曼树生成哈夫曼编码，可以通过递归遍历哈夫曼树来实现。从根节点开始遍历，每次向左走为0，向右走为1，直到叶子节点，即可得到该节点对应的哈夫曼编码。

下面是一个简单的Java代码实现：

public class HuffmanTree {
    private Node root;

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

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

        public int compareTo(Node other) {
            return this.weight - other.weight;
        }

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

        public String toString() {
            return "Node(" + 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<Character, String> getCodes() {
        Map<Character, String> codes = new HashMap<>();
        getCode(root, "", codes);
        return codes;
    }

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