哈夫曼樹構建算法詳解：原理、步驟演示與 C 語言完整實現

哈夫曼樹定義

給定 n 個權值 {W1, W2, ..., Wn} 作為葉子節點，構造一棵二叉樹，使帶權路徑長度 (WPL) 最小：

WPL = Σ (Wi × Li)，其中 Li 為葉子到根的路徑長度 (根層數為 0)。

權值越大的葉子越靠近根，編碼長度越短，實現最優前綴編碼。

經構建算法 (貪心策略)

1. 初始化：每個權值構成單節點樹，放入集合 F，按權值升序排列。
2. 選取：從 F 中取出權值最小的兩棵樹 T1, T2。
3. 合併：新建樹 T，根權值 = W1 + W2，左右子樹分別為 T1, T2。
4. 更新：從 F 刪除 T1, T2，將 T 按權值插入 F 保持有序。
5. 重複：執行 2-4 直到 F 僅剩一棵樹，即哈夫曼樹。

演示：權值序列 {7, 9, 2, 6, 32, 3, 21, 10}

初始:  2  3  6  7  9  10  21  32
步驟1: (2+3)=5           →  5  6  7  9  10  21  32
步驟2: (5+6)=11          →  7  9  10  11  21  32
步驟3: (7+9)=16          →  10  11  16  21  32
步驟4: (10+11)=21        →  16  21  21  32
步驟5: (16+21)=37        →  21  32  37
步驟6: (21+32)=53        →  37  53
步驟7: (37+53)=90        →  90 (根)
最終 WPL = 2×4 + 3×4 + 6×3 + 7×3 + 9×3 + 10×3 + 21×2 + 32×2 = 280

C 語言完整實現 (含編碼/解碼)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_LEAF 30
#define MAX_NODE (MAX_LEAF * 2 - 1)
#define MAX_BIT  100
#define INF 10000

typedef struct { int bit[MAX_BIT]; int start; } HCode;  // 編碼
typedef struct {
    int weight, parent, lchild, rchild, value;
} HNode;  // 節點

/* 構建哈夫曼樹 */
void HuffmanTree(HNode tree[], int n) {
    int i, j, m1, m2, x1, x2;
    for (i = 0; i < 2*n-1; i++) {
        tree[i].weight = 0; tree[i].parent = -1;
        tree[i].lchild = -1; tree[i].rchild = -1;
        tree[i].value = i;
    }
    for (i = 0; i < n; i++) {
        printf("Weight of leaf %d: ", i); scanf("%d", &tree[i].weight);
    }
    for (i = 0; i < n-1; i++) {
        m1 = m2 = INF; x1 = x2 = 0;
        for (j = 0; j < n+i; j++) {
            if (tree[j].parent == -1) {
                if (tree[j].weight < m1) {
                    m2 = m1; x2 = x1;
                    m1 = tree[j].weight; x1 = j;
                } else if (tree[j].weight < m2) {
                    m2 = tree[j].weight; x2 = j;
                }
            }
        }
        tree[x1].parent = tree[x2].parent = n + i;
        tree[n+i].weight = tree[x1].weight + tree[x2].weight;
        tree[n+i].lchild = x1; tree[n+i].rchild = x2;
        printf("Merge: %d(%d) + %d(%d) = %d\n", x1, m1, x2, m2, n+i);
    }
}

/* 生成葉子編碼 (自底向上) */
void HuffmanCode(HNode tree[], HCode code[], int n) {
    HCode cd; int c, p;
    for (int i = 0; i < n; i++) {
        cd.start = n-1; c = i; p = tree[c].parent;
        while (p != -1) {
            cd.bit[cd.start--] = (tree[p].lchild == c) ? 0 : 1;
            c = p; p = tree[c].parent;
        }
        for (int j = cd.start+1; j < n; j++) code[i].bit[j] = cd.bit[j];
        code[i].start = cd.start;
    }
}

/* 解碼演示 */
void Decode(HNode tree[], int n) {
    char str[1024]; int m = 2*n-1;
    printf("Input code string (0/1): "); scanf("%s", str);
    int node = m-1;  // 從根開始
    for (char *p = str; *p; p++) {
        node = (*p == '0') ? tree[node].lchild : tree[node].rchild;
        if (tree[node].lchild == -1) {  // 葉子
            printf("%d ", tree[node].value);
            node = m-1;  // 回根繼續
        }
    }
    puts("");
}

int main() {
    HNode tree[MAX_NODE]; HCode code[MAX_LEAF];
    int n; printf("Leaf count: "); scanf("%d", &n);
    HuffmanTree(tree, n);
    HuffmanCode(tree, code, n);
    for (int i = 0; i < n; i++) {
        printf("%d: ", i);
        for (int j = code[i].start+1; j < n; j++) putchar('0'+code[i].bit[j]);
        puts("");
    }
    Decode(tree, n);
    return 0;
}

關鍵數據結構設計要點

複雜度分析

• 時間：O(n²) (朴素選最小)，用最小堆可優化至 O(n log n)。
• 空間：O(n) 節點數組 + O(n log n) 編碼存儲。

應用場景

1. 數據壓縮：ZIP (Deflate)、JPEG、MP3、PNG 皆採用哈夫曼編碼作為熵編碼階段。
2. 通訊協議：前綴碼無需分隔符，解碼唯一、即時。
3. 決策樹優化：最小化期望查詢成本。