圖文詳解 Java 實現哈夫曼樹構建與編碼

什麼是哈夫曼樹

哈夫曼樹（Huffman Tree），又稱最優二叉樹，是帶權路徑長度（WPL）最小的二叉樹。它廣泛應用於數據壓縮（如 ZIP、JPEG）、加密編碼等領域。

核心概念

• 路徑長度：樹中兩節點間分支數之和。
• 樹的路徑長度：根節點到每個節點路徑長度之和。
• 帶權路徑長度 (WPL)：葉子節點權值 × 其到根路徑長度的總和。WPL 越小，樹越優化。

構建步驟圖解

以字符串 aaaaaaaaaabbbbbaaaaaccccccccddddddfff 為例：

1. 統計權值：a=15, b=5, c=8, d=6, f=3
2. 取最小兩權值合併：f(3) + b(5) = 新節點(8)
3. 重新排序並重複：依次合併 d(6)+c(8)=14，再合併 14+8=22，最後與 a(15) 合併得根節點 37

最終得到的哈夫曼樹所有原始字符均位於葉子節點，WPL 最小。

算法流程總結

1. 統計字符頻率
2. 創建葉子節點並按權值升序排列
3. 循環：取出權值最小的兩個節點 → 創建父節點（權值為兩者之和） → 將父節點放回隊列並重新排序
4. 直到隊列剩單一節點，即為根節點

Java 完整實現

節點類

package huffman;

public class Node {
    public String code;      // 哈夫曼編碼
    public int codeSize;     // 編碼長度
    public String data;      // 字符數據
    public int count;        // 權值
    public Node lChild, rChild;

    public Node() {}
    public Node(String data, int count) { this.data = data; this.count = count; }
    public Node(int count, Node l, Node r) { this.count = count; this.lChild = l; this.rChild = r; }
    public Node(String data, int count, Node l, Node r) { this.data = data; this.count = count; this.lChild = l; this.rChild = r; }
}

哈夫曼樹構建與遍歷

package huffman;
import java.util.*;

public class Huffman {
    private String str;
    private String newStr = "";
    private Node root;
    private ArrayList<String> charList;
    private ArrayList<Node> nodeList;

    public void creatHfmTree(String str) {
        this.str = str;
        charList = new ArrayList<>();
        nodeList = new ArrayList<>();

        // 1. 統計字符頻率
        for (int i = 0; i < str.length(); i++) {
            char ch = str.charAt(i);
            boolean flag = true;
            for (int j = 0; j < charList.size(); j++) {
                if (charList.get(j).charAt(0) == ch) {
                    charList.set(j, charList.get(j) + ch);
                    flag = false;
                    break;
                }
            }
            if (flag) charList.add(ch + "");
        }

        // 2. 創建節點
        for (int i = 0; i < charList.size(); i++) {
            String data = charList.get(i).charAt(0) + "";
            int count = charList.get(i).length();
            nodeList.add(new Node(data, count));
        }

        // 3. 排序並合併
        sort(nodeList);
        while (nodeList.size() > 1) {
            Node left = nodeList.remove(0);
            Node right = nodeList.remove(0);
            Node parent = new Node(left.count + right.count, left, right);
            nodeList.add(0, parent);
            sort(nodeList);
        }
        root = nodeList.get(0);
    }

    private void sort(ArrayList<Node> list) {
        for (int i = 0; i < list.size() - 1; i++) {
            for (int j = i + 1; j < list.size(); j++) {
                if (list.get(i).count > list.get(j).count) {
                    Node t = list.get(i);
                    list.set(i, list.get(j));
                    list.set(j, t);
                }
            }
        }
    }

    // 中序遍歷輸出權值
    public void output(Node node) {
        if (node.lChild != null) output(node.lChild);
        System.out.print(node.count + " ");
        if (node.rChild != null) output(node.rChild);
    }

    public static void main(String[] args) {
        Huffman huff = new Huffman();
        huff.creatHfmTree("sdfassvvdfgsfdfsdfs");
        huff.output();
    }
}

總結

本文通過概念解析、圖解步驟、完整 Java 代碼，系統講解了哈夫曼樹的構建原理與實現。掌握該算法有助於理解數據壓縮核心邏輯，也是經典面試考點。