哈夫曼编码Java实现

哈夫曼编码是一种用于数据压缩的技术，可以通过统计数据中各个元素出现的频率，构建一棵二叉树，并将每个元素与该二叉树中的一个叶子节点对应起来。编码时，将出现频率高的元素编码为较短的二进制字符串，而出现频率低的元素编码为较长的二进制字符串，从而达到压缩数据的目的。

以下是哈夫曼编码的Java实现示例代码：

import java.util.PriorityQueue;
import java.util.Scanner;

class Node implements Comparable<Node> {
    int freq;
    char data;
    Node left, right;

    public Node(char data, int freq) {
        this.data = data;
        this.freq = freq;
        this.left = null;
        this.right = null;
    }

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

    @Override
    public int compareTo(Node node) {
        return Integer.compare(this.freq, node.freq);
    }
}

public class HuffmanEncoding {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter the input string: ");
        String input = sc.nextLine();

        int[] freq = new int[256];
        for (char c : input.toCharArray()) {
            freq[c]++;
        }

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

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

        Node root = pq.poll();
        String[] codes = new String[256];
        generateCodes(root, "", codes);

        System.out.println("Huffman Codes are:");
        for (int i = 0; i < 256; i++) {
            if (freq[i] > 0) {
                System.out.println((char) i + " -> " + codes[i]);
            }
        }
    }

    private static void generateCodes(Node root, String code, String[] codes) {
        if (root.isLeaf()) {
            codes[root.data] = code;
            return;
        }

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

该代码使用优先队列实现哈夫曼编码。首先，统计输入字符串中每个字符出现的频率，并将它们封装为Node对象放入优先队列中。然后，从队列中依次取出两个出现频率最小的Node，合并成一个父Node，并将其放回队列。不断重复此过程，直到队列中只剩下一个Node，即为根节点。

在生成哈夫曼编码时，从根节点开始遍历哈夫曼树，如果遇到叶子节点，则将该节点对应的字符与其编