C語言實現 Huffman 樹與 Huffman 編碼：從構建到編碼的完整教學代碼

前言

Huffman 樹（最優二叉樹）是帶權路徑長度最短的二叉樹，廣泛用於資料壓縮（Huffman 編碼）。本文提供完整 C 實現：權值輸入 → 樹構建（選最小兩棵合併） → 編碼生成（葉節點向根回溯） → 編碼輸出，採用一維陣列順序存儲，代碼清晰適合教學與嵌入式移植。

一、核心資料結構

typedef struct Node {
    int weight;      // 權值（葉節點有效，內部節點為子樹權值和）
    int parent;      // 父節點索引，0 表示根
    int lchild, rchild; // 左/右孩子索引，0 表示無（葉節點）
} HTNode, *HuffmanTree; // 結點陣列指針

typedef char **HuffmanCode; // 編碼表：每個字元一個字串

二、樹構建演算法

步驟：
1. n 個權值 → n 棵單節點樹（陣列前 n 位）。
2. 重複 n-1 次：從**親為 0** 的節點中選**權值最小的兩個** → 建新節點為父，權值求和 → 存入陣列後續位置。
3. 最後剩一棵樹（索引 2n-2），即 Huffman 樹根。

HuffmanTree create_HuffmanTree(int *weight, int n) {
    int total = 2 * n - 1;
    HuffmanTree HT = (HuffmanTree)malloc(total * sizeof(HTNode));
    if (!HT) exit(-1);

    // 初始化葉節點
    for (int i = 0; i < n; i++) {
        HT[i].weight = weight[i];
        HT[i].parent = HT[i].lchild = HT[i].rchild = 0;
    }
    // 初始化內部節點位置
    for (int i = n; i < total; i++) {
        HT[i].weight = HT[i].parent = HT[i].lchild = HT[i].rchild = 0;
    }

    // 構建 n-1 個內部節點
    for (int i = n; i < total; i++) {
        int min1, min2;
        select_minimum(HT, i, &min1, &min2); // 選權值最小且親=0的兩個
        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;
}

三、選最小兩棵樹 select_minimum

void select_minimum(HuffmanTree HT, int limit, int *min1, int *min2) {
    *min1 = find_min(HT, limit);
    *min2 = find_min(HT, limit);
}

int find_min(HuffmanTree HT, int limit) {
    int i = 0;
    while (HT[i].parent != 0) i++; // 找第一個親=0
    int min_idx = i;
    int min_w = HT[i].weight;
    for (; i < limit; i++) {
        if (HT[i].parent == 0 && HT[i].weight < min_w) {
            min_w = HT[i].weight;
            min_idx = i;
        }
    }
    HT[min_idx].parent = 1; // 標記已選（暫時置 1，區別於真正父節點）
    return min_idx;
}

技巧：將「已選」節點 parent 暫設為 1（非 0），下輪選擇時自動跳過，構建完成後真正父節點會覆蓋為正確索引。

四、Huffman 編碼生成（葉節點向根回溯）

void HuffmanCoding(HuffmanTree HT, HuffmanCode *HC, int n) {
    *HC = (HuffmanCode)malloc(n * sizeof(char*));
    if (!*HC) exit(-1);

    char *code = (char*)malloc(n * sizeof(char)); // 臨時緩衝區，最長 n-1 位
    if (!code) exit(-1);
    code[n-1] = '\0';

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

五、測試案例：權值 {5,4,3,2,1}

int main() {
    int w[] = {5,4,3,2,1};
    int n = 5;
    HuffmanTree HT = create_HuffmanTree(w, n);
    HuffmanCode HC;
    HuffmanCoding(HT, &HC, n);

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

    // 釋放記憶體（略）
    return 0;
}

六、輸出結果

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

對應樹結構：權值大的節點（5,4）靠近根（編碼短），權值小的（1,2）較遠（編碼長），符合 Huffman 最優前綴碼性質。

七、複雜度與優化方向

八、總結

這份代碼以 順序存儲 + 親/孩子索引 實現 Huffman 樹，避免了指針操作複雜性，極適合嵌入式、教學、資料壓縮入門。核心邏輯——**貪心選最小合併、回溯生成前綴碼**——是資訊論與演算法設計的經典範例。

1. 上一篇文章： 遞迴法求費波那契數列（C 語言版）
2. 下一篇文章： GLSL 動態變色三角形（C 語言 + OpenGL）

關於C

C語言深度解析：為什麼函數參數從右往左入棧？

呼叫慣例與棧框架：C語言參數傳遞的歷史與邏輯 C語言函數參數

C 語言語義陷阱：陣列與指標的訪問差異

前言 陣列與指標是 C 語言最核心也最易混淆的概念。許多教材

C語言基礎模擬：不漲薪、不投資、不消費，軟工幾年買得起 200 萬年增 10% 的房

最悲觀假設：房價 200 萬年增 10%，軟工年薪固定 40

Qt 使用 QTreeWidget 實現類 QQ 的用戶列表界面

Qt 使用 QTreeWidget 實現類 QQ 的用戶列表