C 語言實現霍夫曼樹與霍夫曼編碼完整指南

霍夫曼樹定義

給定 n 個權值 {w1, w2, ..., wn}，構造含 n 個葉子節點的二叉樹，葉子權值為給定權值，**帶權路徑長度 (WPL) 最小** 的樹稱為霍夫曼樹 (最優二叉樹)。

WPL = Σ (葉子權值 × 到根路徑長度)。權值越大的葉子越靠近根。

特性

• 同一組權值可能構造多棵霍夫曼樹 (左右子樹可交換)
• 所有帶權節點皆為葉子，非葉子節點無權值
• 無度為 1 的節點
• n 個葉子 → 共 2n-1 個節點

構建演算法

1. 將 n 個權值視為 n 棵單節點樹，放入集合 HT
2. 從 HT 選取權值最小的兩棵樹，合併為新樹，權值為兩者之和
3. 從 HT 移除那兩棵，加入新樹
4. 重複 2-3 直到 HT 僅剩一棵樹 → 霍夫曼樹

資料結構設計 (循序儲存)

#define MAX_NODES 1000

typedef struct {
    int weight;      // 權值
    int parent;      // 父節點索引 (0 表根)
    int lchild, rchild; // 左右孩子索引 (0 表無)
} HTNode;

typedef HTNode *HuffmanTree; // 大小 2n-1 的陣列
typedef char **HuffmanCode;  // 每個葉子的編碼字串陣列

核心代碼實現

1. 選取最小權值節點

void select_min(HuffmanTree HT, int k, int *min1, int *min2) {
    int i, min_idx = -1, min_w = INT_MAX;
    // 找第一個 parent==0
    for (i = 0; i < k; ++i)
        if (HT[i].parent == 0) { min_w = HT[i].weight; min_idx = i; break; }
    // 找最小
    for (; i < k; ++i)
        if (HT[i].parent == 0 && HT[i].weight < min_w) { min_w = HT[i].weight; min_idx = i; }
    *min1 = min_idx;
    HT[min_idx].parent = 1; // 暫時標記避免重複選中

    // 找第二小
    min_idx = -1; min_w = INT_MAX;
    for (i = 0; i < k; ++i)
        if (HT[i].parent == 0) { min_w = HT[i].weight; min_idx = i; break; }
    for (; i < k; ++i)
        if (HT[i].parent == 0 && HT[i].weight < min_w) { min_w = HT[i].weight; min_idx = i; }
    *min2 = min_idx;
    HT[min_idx].parent = 1;
}

2. 建立霍夫曼樹

HuffmanTree create_huffman(int *weights, int n) {
    int total = 2 * n - 1;
    HuffmanTree HT = calloc(total, sizeof(HTNode));
    // 初始化葉子節點
    for (int i = 0; i < n; ++i) {
        HT[i].weight = weights[i];
        HT[i].parent = HT[i].lchild = HT[i].rchild = 0;
    }
    // 初始化內部節點
    for (int i = n; i < total; ++i)
        HT[i].parent = HT[i].lchild = HT[i].rchild = 0, HT[i].weight = 0;

    // 合併 n-1 次
    for (int i = n; i < total; ++i) {
        int min1, min2;
        select_min(HT, i, &min1, &min2);
        HT[min1].parent = i;
        HT[min2].parent = i;
        HT[i].lchild = min1;
        HT[i].rchild = min2;
        HT[i].weight = HT[min1].weight + HT[min2].weight;
    }
    return HT;
}

3. 霍夫曼編碼 (葉子到根逆向遍歷)

void huffman_coding(HuffmanTree HT, HuffmanCode *HC, int n) {
    *HC = malloc(n * sizeof(char*));
    char *code = malloc(n * sizeof(char));
    code[n-1] = '\0';

    for (int i = 0; i < n; ++i) {
        int cur = i, parent = HT[i].parent;
        int start = n - 1;
        while (parent != 0) {
            if (HT[parent].lchild == cur) code[--start] = '0';
            else code[--start] = '1';
            cur = parent;
            parent = HT[parent].parent;
        }
        (*HC)[i] = malloc((n - start) * sizeof(char));
        strcpy((*HC)[i], code + start);
    }
    free(code);
}

完整範例與輸出

int main() {
    int weights[] = {5, 4, 3, 2, 1};
    int n = 5;
    HuffmanTree HT = create_huffman(weights, n);
    HuffmanCode HC;
    huffman_coding(HT, &HC, n);

    for (int i = 0; i < n; ++i)
        printf("Weight %d: Code = %s\n", weights[i], HC[i]);

    // 釋放記憶體
    for (int i = 0; i < n; ++i) free(HC[i]);
    free(HC);
    free(HT);
    return 0;
}

輸出結果 (其中一種可能)

Weight 5: Code = 11
Weight 4: Code = 10
Weight 3: Code = 00
Weight 2: Code = 011
Weight 1: Code = 010

應用場景

• 檔案壓縮 (ZIP, gzip, PNG, MP3 等)
• 通訊協議壓縮傳輸
• 資料庫索引壓縮
• 編譯器關鍵字編碼

複雜度

工程實務中建樹採用最小堆 (Priority Queue) 將建樹優化至 O(n log n)。