Java 實現哈夫曼樹構建演算法

哈夫曼樹是一種帶權路徑長度最短的二叉樹，廣泛應用於數據壓縮編碼（如 ZIP、JPEG、MP3）中。本文通過 Java 代碼完整演示哈夫曼樹的構建過程，包含節點定義、優先隊列排序、樹構建邏輯及輸出驗證。

節點類設計

節點需實現 Comparable 接口以支持優先隊列排序，包含權值、左右子節點引用及樹形打印方法：

/**
 * 二叉樹節點
 */
public class Node implements Comparable<Node> {

    private int value;
    private Node leftChild;
    private Node rightChild;

    public Node(int value) {
        this.value = value;
    }

    // Getter/Setter 省略...

    /**
     * 樹形結構字符串輸出，便於調試驗證
     */
    public String toString(int level) {
        String indent = "";
        for (int i = 0; i < level; i++) {
            indent += "  ";
        }
        return indent + value + "\n" +
               (leftChild != null ? leftChild.toString(level + 1) : "") +
               (rightChild != null ? rightChild.toString(level + 1) : "");
    }

    @Override
    public int compareTo(Node that) {
        // 權值越小優先級越高（用於構建最小堆）
        return Integer.compare(this.value, that.value);
    }
}

哈夫曼樹構建核心邏輯

採用經典「貪心演算法」：每次從節點集合中取出權值最小的兩個節點合併為新父節點，放回集合，重複直到只剩根節點。

import java.util.*;

public class HuffmanTreeBuilder {

    public static void main(String[] args) {
        List<Node> nodes = Arrays.asList(
            new Node(40), new Node(8), new Node(10),
            new Node(30), new Node(10), new Node(2)
        );

        Node root = HuffmanTreeBuilder.build(nodes);
        System.out.println("哈夫曼樹結構：");
        System.out.println(root.toString(0));
    }

    /**
     * 構建哈夫曼樹
     * @param nodes 初始葉子節點集合
     * @return 樹根節點
     */
    private static Node build(List<Node> nodes) {
        // 防御性拷貝，避免修改原參數
        nodes = new ArrayList<>(nodes);
        sortList(nodes); // 初始排序

        while (nodes.size() > 1) {
            createAndReplace(nodes);
        }
        return nodes.get(0);
    }

    /**
     * 取出權值最小的兩個節點合併，父節點放回集合並重新排序
     */
    private static void createAndReplace(List<Node> nodes) {
        // 列表已按權值升序排列，末尾兩個為最小
        Node left = nodes.get(nodes.size() - 1);
        Node right = nodes.get(nodes.size() - 2);

        Node parent = new Node(left.getValue() + right.getValue());
        parent.setLeftChild(left);
        parent.setRightChild(right);

        nodes.remove(nodes.size() - 1);
        nodes.remove(nodes.size() - 1);
        nodes.add(parent);

        sortList(nodes); // 重新排序維持有序性
    }

    private static void sortList(List<Node> nodes) {
        Collections.sort(nodes); // 利用 Node 實現的 compareTo
    }
}

執行結果示例

輸入權值：[40, 8, 10, 30, 10, 2]

100
  40
  60
    30
    30
      10
      20
        10
        10
          8
          2

關鍵點總結

• 防禦性拷貝：build 方法開頭 new ArrayList<>(nodes) 避免副作用修改調用方傳入的列表
• 排序策略：權值升序排列，配合 ArrayList 末尾取值效率最高
• 樹形打印：toString(int level) 遞歸實現，縮進直觀展示樹結構層級
• 時間複雜度：每次合併需排序，總體 O(n² log n)；若用優先隊列可優化至 O(n log n)

優化建議：使用 PriorityQueue

private static Node buildOptimized(List<Node> nodes) {
    PriorityQueue<Node> pq = new PriorityQueue<>(nodes);
    while (pq.size() > 1) {
        Node left = pq.poll();
        Node right = pq.poll();
        Node parent = new Node(left.getValue() + right.getValue());
        parent.setLeftChild(left);
        parent.setRightChild(right);
        pq.offer(parent);
    }
    return pq.poll();
}

採用 PriorityQueue 可顯著提升大數據量下的構建性能，是生產環境推薦的實現方式。