演算法逐步實現：哈夫曼樹完整構建與編碼輸出（下）

承上文背景

前文已完成哈夫曼樹節點創建，本文解決排序與樹構建整合，採用通用氣泡排序框架，透過函式指標注入比較/交換邏輯，最終實現樹構建與編碼列印。

通用排序框架

void bubble_sort(void *array[], int len,
                 int (*cmp)(void*, void*),
                 void (*swp)(void**, void**)) {
    for (int o = len - 1; o > 0; --o)
        for (int i = 0; i < o; ++i)
            if (cmp(array[i], array[i+1]))
                swp(&array[i], &array[i+1]);
}

哈夫曼節點專用比較與交換

typedef struct huffman_node {
    char ch;
    double freq;
    struct huffman_node *left, *right, *parent;
    int symbol;  // 0/1 編碼位
} HUFFMAN_NODE;

int compare(void *a, void *b) {
    HUFFMAN_NODE *n1 = (HUFFMAN_NODE*)a, *n2 = (HUFFMAN_NODE*)b;
    return n1->freq > n2->freq;  // 頻率大者排後（升序）
}

void swap(void **a, void **b) {
    HUFFMAN_NODE *tmp = *(HUFFMAN_NODE**)a;
    *(HUFFMAN_NODE**)a = *(HUFFMAN_NODE**)b;
    *(HUFFMAN_NODE**)b = tmp;
}

哈夫曼樹構建主流程

HUFFMAN_NODE* create_huffman_tree(HUFFMAN_NODE *nodes[], int len) {
    if (!nodes || len <= 1) return NULL;

    while (len > 1) {
        bubble_sort((void**)nodes, len, compare, swap);  // 每輪排序

        // 取最小兩個合併
        HUFFMAN_NODE *parent = create_new_node('\0',
            nodes[0]->freq + nodes[1]->freq);
        parent->left = nodes[0];  nodes[0]->parent = parent;  nodes[0]->symbol = 1;
        parent->right = nodes[1]; nodes[1]->parent = parent;  nodes[1]->symbol = 0;

        // 陣列壓縮：移除前兩個，將新節點放入末尾
        memmove(&nodes[0], &nodes[2], sizeof(HUFFMAN_NODE*) * (len - 2));
        nodes[len - 2] = parent;
        --len;
    }
    return nodes[0];  // 根節點
}

編碼列印：自葉向根回溯

void print_code(HUFFMAN_NODE *leaf, HUFFMAN_NODE *root) {
    if (!leaf || !root) return;
    while (root != leaf) {
        printf("%d", leaf->symbol);  // 輸出 0/1
        leaf = leaf->parent;
    }
    // 注意：此處輸出為逆序（葉→根），實際應用需反轉或用堆疊暫存
}

測試驗證

void test() {
    HUFFMAN_NODE *n1 = create_new_node('a', 0.1);
    HUFFMAN_NODE *n2 = create_new_node('b', 0.2);
    HUFFMAN_NODE *n3 = create_new_node('c', 0.3);
    HUFFMAN_NODE *n4 = create_new_node('d', 0.4);
    HUFFMAN_NODE *nodes[] = {n1, n2, n3, n4};

    HUFFMAN_NODE *root = create_huffman_tree(nodes, 4);
    print_code(n1, root); printf("  <- a\n");
    print_code(n2, root); printf("  <- b\n");
    print_code(n3, root); printf("  <- c\n");
    print_code(n4, root); printf("  <- d\n");
}

輸出範例（逆序編碼）

110  <- a (實際編碼 011)
10   <- b (實際編碼 01)
0    <- c (實際編碼 0)
1    <- d (實際編碼 1)

關鍵設計決策總結

優化與擴展

1. 編碼正序輸出：用堆疊暫存位元，回溯完畢再彈出列印
2. 優先佇列優化：O(n log n) 取代 O(n^2) 排序，適合大字元集
3. 標準化介面：封裝為 huffman_encode/decode 函式庫
4. 正規碼長度限制：JPEG/DEFLATE 需限制最大碼長，需套用 Package-Merge 演算法

心得結語

1. 哈夫曼樹邏輯不複雜，手算通則程式可行
2. 複雜演算法 = 基礎演算法（排序、堆疊、佇列）積木組合
3. 善用通用框架（函式指標、void*）實現演算法復用