哈夫曼樹與編碼原理詳解及 C++ 模板完整實現

核心概念：帶權路徑長度 (WPL)

• 路徑：節點間分支序列
• 路徑長度：分支條數
• 節點權值：賦予節點的數值 (如字符頻率)
• 帶權路徑長度：節點到根的路徑長度 × 權值
• WPL：所有葉子節點帶權路徑長度之和
• 哈夫曼樹：給定葉子權值下，WPL 最小的二叉樹 (最優二叉樹)

構建算法：貪心策略

1. 初始化：每個權值建單節點樹，形成森林 F。
2. 選取合併：從 F 中取出權值最小的兩棵樹，作左右子樹建新樹，新根權值 = 兩子樹權值之和。
3. 更新森林：刪除那兩棵樹，加入新樹。
4. 重複：執行 n-1 次，直到森林僅剩一棵樹 —— 哈夫曼樹。

示例：權值 {1, 3, 6, 9} 構建過程見文中圖解，最終根節點權值 19 (WPL)。

C++ 模板實現：節點與樹類

template <typename T>
struct HuffmanNode {
    T key;                    // 權值
    HuffmanNode* lchild;      // 左子
    HuffmanNode* rchild;      // 右子
    int flag = 0;             // 是否已從森林移除
    HuffmanNode(T k, HuffmanNode* l, HuffmanNode* r) : key(k), lchild(l), rchild(r) {}
};

template <typename T>
class Huffman {
    static const int MAXSIZE = 100;
    HuffmanNode<T>* root = nullptr;
    HuffmanNode<T>* forest[MAXSIZE]; // 陣列模擬森林

    void my_sort(int size) {        // 簡單選擇排序，按權值升序
        for (int i = 0; i < size-1; ++i)
            for (int j = i+1; j < size; ++j)
                if (forest[i]->key > forest[j]->key)
                    std::swap(forest[i], forest[j]);
    }

public:
    void creat(T a[], int size) {   // 構建哈夫曼樹
        // 1. 初始化森林
        for (int i = 0; i < size; ++i)
            forest[i] = new HuffmanNode<T>(a[i], nullptr, nullptr);

        int k = 0;
        // 2. 重複合併 n-1 次
        for (int i = 0; i < size-1; ++i) {
            my_sort(size + k);      // 每次重新排序 (可優化為優先隊列)
            // 找第一個未被標記的兩棵樹
            int j = 0;
            while (forest[j]->flag || forest[j+1]->flag) ++j;
            // 合併
            auto* node = new HuffmanNode<T>(forest[j]->key + forest[j+1]->key, forest[j], forest[j+1]);
            forest[size + k++] = node;
            forest[j]->flag = forest[j+1]->flag = 1;
        }
        root = forest[size + k - 1];
    }

    // 遍歷與銷毀略...
    void print() { print(root); }
    void destory() { destory(root); }
    ~Huffman() { destory(); }
};

測試與輸出

int main() {
    Huffman<int> huff;
    int a[] = {10, 20, 30, 40};
    huff.creat(a, 4);
    huff.print();
}

輸出結構展示根 100，左 40，右 60 等層級關係，驗證構建正確性。

優化方向與哈夫曼編碼預告

• 優先隊列 (min-heap)：替換陣列排序，構建複雜度從 O(n²) 降至 O(n log n)。
• 編碼生成：從根到葉遍歷，左分支編 0，右分支編 1，葉子路徑即為該字符編碼。
• 解碼：利用樹結構，按位流走向還原字符。

下篇將補充編碼/解碼完整實現，並討論標準庫 priority_queue 的應用。