Java 哈夫曼樹 (Huffman Tree) 完整實作與編碼原理

哈夫曼樹簡介

哈夫曼樹 是帶權路徑長度 (WPL) 最小的二元樹，廣泛應用於資料壓縮編碼 (如 ZIP、JPEG、MP3)。核心思想：權重越大的節點離根節點越近，權重越小的節點離根節點越遠，以達到整體編碼長度最短。

建樹演算法步驟

1. 將所有葉子節點 (字元及其權重) 放入優先隊列 (最小堆)
2. 重複執行直到隊列剩一個節點：
   1. 取出權重最小的兩個節點
   2. 建立新父節點，權重 = 兩子節點權重之和
   3. 將父節點放回隊列
3. 剩下的節點即為哈夫曼樹根節點

Java 完整實作

package boom;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Queue;

class Node<T> implements Comparable<Node<T>> {
    private T data;
    private int weight;
    private Node<T> left;
    private Node<T> right;

    public Node(T data, int weight) {
        this.data = data;
        this.weight = weight;
    }

    @Override
    public int compareTo(Node<T> other) {
        // 由小排到大，權重小的優先
        if (this.weight < other.getWeight()) return -1;
        if (this.weight > other.getWeight()) return 1;
        return 0;
    }

    // Getter/Setter 省略...
    public T getData() { return data; }
    public int getWeight() { return weight; }
    public Node<T> getLeft() { return left; }
    public void setLeft(Node<T> left) { this.left = left; }
    public Node<T> getRight() { return right; }
    public void setRight(Node<T> right) { this.right = right; }
    
    @Override
    public String toString() {
        return "data:" + data + ";weight:" + weight;
    }
}

public class Huffman<T> {
    
    // 建立哈夫曼樹
    public static <T> Node<T> create(List<Node<T>> nodes) {
        while (nodes.size() > 1) {
            Collections.sort(nodes); // 簡單實作，生產環境建議用 PriorityQueue
            
            Node<T> right = nodes.remove(nodes.size() - 1); // 權重最小
            Node<T> left = nodes.remove(nodes.size() - 1);  // 次小
            
            Node<T> parent = new Node<>(null, left.getWeight() + right.getWeight());
            parent.setLeft(left);
            parent.setRight(right);
            
            nodes.add(parent);
        }
        return nodes.get(0);
    }

    // 層序遍歷 (廣度優先)
    public static <T> List<Node<T>> breadth(Node<T> root) {
        List<Node<T>> result = new ArrayList<>();
        Queue<Node<T>> queue = new ArrayDeque<>();
        queue.offer(root);
        
        while (!queue.isEmpty()) {
            Node<T> current = queue.poll();
            result.add(current);
            if (current.getLeft() != null) queue.offer(current.getLeft());
            if (current.getRight() != null) queue.offer(current.getRight());
        }
        return result;
    }

    public static void main(String[] args) {
        List<Node<String>> nodes = new ArrayList<>();
        nodes.add(new Node<>("a", 7));
        nodes.add(new Node<>("b", 5));
        nodes.add(new Node<>("c", 4));
        nodes.add(new Node<>("d", 2));
        
        Node<String> root = create(nodes);
        System.out.println("層序遍歷結果: " + breadth(root));
        
        // 預期輸出結構:
        // root(weight=18)
        //   ├── left: a(7)
        //   └── right: internal(11)
        //         ├── left: b(5)
        //         └── right: internal(6)
        //               ├── left: c(4)
        //               └── right: d(2)
    }
}

哈夫曼編碼產生

由根節點出發，左分支編碼 0，右分支編碼 1：

• a: 0 (權重 7，最短)
• b: 10 (權重 5)
• c: 110 (權重 4)
• d: 111 (權重 2，最長)

驗證 WPL = 7×1 + 5×2 + 4×3 + 2×3 = 7 + 10 + 12 + 6 = 35 (最小)

效能優化建議

• 使用 PriorityQueue 替代 Collections.sort，建樹複雜度從 O(n²log n) 降為 O(n log n)
• 編碼表建議用 Map<Character, String> 快速查找
• 大規模資料壓縮可考慮 canonical Huffman coding 減少編碼表儲存空間

應用場景

• 檔案壓縮 (GZIP, ZIP, PNG, JPEG)
• 網路傳輸壓縮 (HTTP Content-Encoding)
• 電信訊號編碼
• 資料庫欄位壓縮儲存