编辑代码

import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

public class HuffmanCoding {

    static class Node {
        char character;
        int frequency;
        Node left, right;

        Node(char character, int frequency) {
            this.character = character;
            this.frequency = frequency;
        }
    }

    public static void main(String[] args) {
        // 字符和频率
        Map<Character, Integer> frequencyMap = new HashMap<>();
        frequencyMap.put('a', 5);
        frequencyMap.put('b', 9);
        frequencyMap.put('c', 12);
        frequencyMap.put('d', 13);
        frequencyMap.put('e', 16);

        // 创建 Huffman 树
        Node root = buildHuffmanTree(frequencyMap);

        // 生成 Huffman 编码
        Map<Character, String> huffmanCodes = generateHuffmanCodes(root);

        // 打印编码结果
        System.out.println("字符\t频率\t编码");
        for (Map.Entry<Character, String> entry : huffmanCodes.entrySet()) {
            System.out.println(entry.getKey() + "\t" + frequencyMap.get(entry.getKey()) + "\t" + entry.getValue());
        }
    }

    // 构建 Huffman 树
    private static Node buildHuffmanTree(Map<Character, Integer> frequencyMap) {
        // 使用优先队列存储节点，优先级按频率升序排列
        PriorityQueue<Node> queue = new PriorityQueue<>(Comparator.comparingInt(n -> n.frequency));

        // 将所有字符节点添加到队列
        for (Map.Entry<Character, Integer> entry : frequencyMap.entrySet()) {
            queue.offer(new Node(entry.getKey(), entry.getValue()));
        }

        // 构建 Huffman 树
        while (queue.size() > 1) {
            Node left = queue.poll();
            Node right = queue.poll();

            Node parent = new Node('\0', left.frequency + right.frequency); // '\0' 表示内部节点没有字符
            parent.left = left;
            parent.right = right;

            queue.offer(parent);
        }

        return queue.poll();
    }

    // 生成 Huffman 编码
    private static Map<Character, String> generateHuffmanCodes(Node root) {
        Map<Character, String> huffmanCodes = new HashMap<>();
        generateCodes(root, "", huffmanCodes);
        return huffmanCodes;
    }

    // 递归生成编码
    private static void generateCodes(Node node, String code, Map<Character, String> huffmanCodes) {
        if (node == null) {
            return;
        }

        if (node.character != '\0') {
            huffmanCodes.put(node.character, code);
        }

        generateCodes(node.left, code + "0", huffmanCodes);
        generateCodes(node.right, code + "1", huffmanCodes);
    }
}