哈夫曼树与哈夫曼编码详解：原理、构建过程与示例

WPL = 1×3 + 1×3 + 2×3 + 2×3 + 3×2 + 3×2 = 30

// 构建节点对象
public class HuffmanNode implements Comparable<HuffmanNode> {
    Character character; // 叶子节点存字符，内部节点为 null
    int frequency;       // 使用原始类型，避免 Long 装箱
    HuffmanNode left;
    HuffmanNode right;

    public HuffmanNode(Character character, int frequency) {
        this.character = character;
        this.frequency = frequency;
    }

    @Override
    public String toString() {
        return "HuffmanNode{" +
                "character=" + character +
                ", frequency=" + frequency +
                '}';
    }

    @Override
    public int compareTo(HuffmanNode o) {
        return Integer.compare(this.frequency, o.frequency);
    }
}

// frequencyHuffman — 统计字符串中各字符的频率
public static Map<Character, Integer> frequencyHuffman(final String data) {
    if (data == null || data.isEmpty()) {
        return Map.of();
    }

    Map<Character, Integer> map = new HashMap<>();
    for (char c : data.toCharArray()) {
        map.merge(c, 1, Integer::sum);
    }
    return map;
}

// 构建哈夫曼树
public static HuffmanNode buildHuffmanTree(Map<Character, Integer> frequencyMap) {
    PriorityQueue<HuffmanNode> priorityQueue = new PriorityQueue<>();
    frequencyMap.forEach((ch, freq) -> priorityQueue.add(new HuffmanNode(ch, freq)));

    // 每次取出两个频率最小的节点，合并成一个新节点，直到队列中只剩下一个节点
    while (priorityQueue.size() > 1) {
        HuffmanNode left = priorityQueue.poll();
        HuffmanNode right = priorityQueue.poll();
        HuffmanNode parent = new HuffmanNode(null, left.frequency + right.frequency);
        parent.left = left;
        parent.right = right;
        priorityQueue.add(parent);
    }
    return priorityQueue.poll();
}

// 深度搜索：在哈夫曼树中查找目标字符对应的编码
public static String findCode(HuffmanNode node, char targetChar, String path) {
    if (node == null) {
        return null;
    }
    if (node.character != null && node.character == targetChar) {
        return path;
    }
    String leftPath = findCode(node.left, targetChar, path + "0");
    if (leftPath != null) {
        return leftPath;
    }
    return findCode(node.right, targetChar, path + "1");
}

// 编码：通过树 + DFS 动态生成编码（不显式保存编码表）
public static String huffmanEncode(String data, HuffmanNode root) {
    if (data == null || data.isEmpty() || root == null) {
        return "";
    }

    StringBuilder encodedData = new StringBuilder();
    for (char c : data.toCharArray()) {
        String code = findCode(root, c, "");
        if (code == null) {
            throw new IllegalArgumentException("Character not found in Huffman tree: " + c);
        }
        encodedData.append(code);
    }
    return encodedData.toString();
}

// 解码：沿哈夫曼树根据 0/1 路径还原原始数据
public static String huffmanDecode(String encodedData, HuffmanNode root) {
    if (encodedData == null || encodedData.isEmpty() || root == null) {
        return "";
    }

    StringBuilder decodedData = new StringBuilder();
    HuffmanNode current = root;
    for (char c : encodedData.toCharArray()) {
        if (c == '0') {
            current = current.left;
        } else if (c == '1') {
            current = current.right;
        } else {
            throw new IllegalArgumentException("Invalid bit in encoded data: " + c);
        }

        // 到达叶子节点，输出字符
        if (current.left == null && current.right == null) {
            decodedData.append(current.character);
            current = root; // 回到根节点继续解码
        }
    }
    return decodedData.toString();
}

public static void main(String[] args) {
    String data = "this is an example for huffman encoding";

    Map<Character, Integer> frequencyMap = frequencyHuffman(data);
    System.out.println("Character Frequencies: " + frequencyMap);

    System.out.println("example: " + data);

    HuffmanNode root = buildHuffmanTree(frequencyMap);
    System.out.println("Huffman Tree Root Frequency: " + root.frequency);

    String encodedData = huffmanEncode(data, root);
    System.out.println("Encoded Data: " + encodedData);

    String decodedData = huffmanDecode(encodedData, root);
    System.out.println("Decoded Data: " + decodedData);
}

Character Frequencies: { =6, a=3, c=1, d=1, e=3, f=3, g=1, h=2, i=3, l=1, m=2, n=4, o=2, p=1, r=1, s=2, t=1, u=1, x=1}
example: this is an example for huffman encoding
Huffman Tree Root Frequency: 39
Encoded Data: 0000100011100001011111000010111100101111110110011110010100101011100011011111110101011010011100011000011011101010010010111111011011001100101000001100011101010
Decoded Data: this is an example for huffman encoding