哈夫曼编码java实现

哈夫曼编码是一种数据压缩算法，用于将数据压缩为更小的数据集。在哈夫曼编码中，频率越高的字符被编码为较短的编码，频率较低的字符被编码为较长的编码。以下是一个基本的Java实现：

1. 定义一个节点类，表示哈夫曼树上的节点。

class Node {
    char data; // 字符
    int freq; // 频率
    Node left, right; // 左子树和右子树

    // 构造函数
    public Node(char data, int freq) {
        this.data = data;
        this.freq = freq;
        left = null;
        right = null;
    }
}

2. 定义一个比较器类，用于按照频率比较节点。

class NodeComparator implements Comparator<Node> {
    public int compare(Node node1, Node node2) {
        return node1.freq - node2.freq;
    }
}

3. 定义一个构建哈夫曼树的方法。

public static Node buildHuffmanTree(char[] chars, int[] freqs) {
    PriorityQueue<Node> pq = new PriorityQueue<Node>(new NodeComparator());

    // 将所有字符和频率的节点加入优先队列
    for (int i = 0; i < chars.length; i++) {
        pq.offer(new Node(chars[i], freqs[i]));
    }

    // 构建哈夫曼树
    while (pq.size() > 1) {
        Node left = pq.poll();
        Node right = pq.poll();
        Node parent = new Node('$', left.freq + right.freq);
        parent.left = left;
        parent.right = right;
        pq.offer(parent);
    }

    // 返回根节点
    return pq.poll();
}

4. 定义一个打印哈夫曼编码的方法。

public static void printHuffmanCodes(Node root, String code) {
    if (root == null) {
        return;
    }

    if (root.data != '$') {
        System.out.println(root.data + ": " + code);
    }

    printHuffmanCodes(root.left, code + "0");
    printHuffmanCodes(root.right, code + "1");
}

5. 调用以上方法，实现哈夫曼编码。

public static void main(String[] args) {
    char[] chars = { 'a', 'b', 'c', 'd', 'e', 'f' };
    int[] freqs = { 5, 9, 12, 13, 16, 45 };

    Node root = buildHuffmanTree(chars, freqs);
    printHuffmanCodes(root, "");
}

以上代码将输出以下内容：

a: 1100
c: 100
b: 1110
e: 01
d: 101
f: 00