数据结构哈夫曼树代码java语言

哈夫曼树是一种特殊的二叉树，它的每个叶子节点都对应一个权值，而非叶子节点则没有权值。哈夫曼树的构建过程是通过不断合并权值最小的两个节点来实现的，直到最终只剩下一个节点为止。哈夫曼树常用于数据压缩算法中。

以下是哈夫曼树的Java代码实现：

import java.util.PriorityQueue;

public class HuffmanTree {
    private Node root;

    private static class Node implements Comparable<Node> {
        private final char ch;
        private final int freq;
        private final Node left, right;

        Node(char ch, int freq, Node left, Node right) {
            this.ch = ch;
            this.freq = freq;
            this.left = left;
            this.right = right;
        }

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

        public int compareTo(Node that) {
            return this.freq - that.freq;
        }
    }

    public HuffmanTree(String s) {
        int[] freq = new int[256];
        for (int i = 0; i < s.length(); i++) {
            freq[s.charAt(i)]++;
        }

        PriorityQueue<Node> pq = new PriorityQueue<>();
        for (char c = 0; c < 256; c++) {
            if (freq[c] > 0) {
                pq.offer(new Node(c, freq[c], null, null));
            }
        }

        while (pq.size() > 1) {
            Node left = pq.poll();
            Node right = pq.poll();
            Node parent = new Node('\0', left.freq + right.freq, left, right);
            pq.offer(parent);
        }

        root = pq.poll();
    }

    public String encode(String s) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            Node x = root;
            while (!.isLeaf()) {
                if (s.charAt(i) == x.left.ch) {
                    sb.append('0');
                    x = x.left;                } else {
                    sb.append('1');
                    x = x.right;
                }
            }
            sb.append(x.ch);
        }
        return sb.toString();
    }

    public String decode(String s) {
        StringBuilder sb = new StringBuilder();
        Node x = root;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '0') {
                x = x.left;
            } else {
                x = x.right;
            }
            if (x.isLeaf()) {
                sb.append(x.ch);
                x = root;
            }
        }
        return sb.toString();
    }
}