霍夫曼樹構建完整實作：通用排序與編碼輸出

霍夫曼樹回顧

霍夫曼樹是帶權路徑長度最小的二叉樹，廣泛用於無損壓縮編碼。構建步驟：

1. 建立葉節點集合，每節點含權重（頻率）。
2. 重複：取權重最小的兩棵樹合併為新樹，權重為兩者之和，放回集合。
3. 直到只剩一棵樹 → 霍夫曼樹根節點。
4. 從葉到根遍歷，左分支編 0、右分支編 1（或相反），即得各符號編碼。

關鍵資料結構

typedef struct _HUFFMAN_NODE {
    char symbol;           // 葉節點字元，內部節點為 '\0'
    double frequence;      // 權重/頻率
    struct _HUFFMAN_NODE* left;
    struct _HUFFMAN_NODE* right;
    struct _HUFFMAN_NODE* parent;
    int bit;               // 0 或 1，指示來自父節點的哪一支
} HUFFMAN_NODE;

通用排序框架複用

採用函數指針實現泛型冒泡排序，僅需提供 compare、swap 兩個適配函數：

void bubble_sort(void* array[], int length,
                 int (*compare)(void*, void*),
                 void (*swap)(void**, void**)) {
    for (int outer = length - 1; outer > 0; outer--) {
        for (int inner = 0; inner < outer; inner++) {
            if (compare(array[inner], array[inner + 1])) {
                swap(&array[inner], &array[inner + 1]);
            }
        }
    }
}

int compare_huffman(void* a, void* b) {
    HUFFMAN_NODE* n1 = (HUFFMAN_NODE*)a;
    HUFFMAN_NODE* n2 = (HUFFMAN_NODE*)b;
    return n1->frequence > n2->frequence ? 1 : 0;
}

void swap_huffman(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 length) {
    if (!nodes || length <= 1) return NULL;

    HUFFMAN_NODE* root = NULL;
    while (length > 1) {
        // 1. 排序取最小兩個
        bubble_sort((void**)nodes, length, compare_huffman, swap_huffman);

        // 2. 建立新父節點
        root = create_new_node('\0', nodes[0]->frequence + nodes[1]->frequence);
        assert(root);
        root->left = nodes[0];
        root->right = nodes[1];
        nodes[0]->parent = root;  nodes[0]->bit = 1;
        nodes[1]->parent = root;  nodes[1]->bit = 0;

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

編碼輸出：從葉到根逆序列印

void print_code_for_str(HUFFMAN_NODE* leaf, HUFFMAN_NODE* root) {
    if (!leaf || !root) return;
    while (leaf != root) {
        printf("%d", leaf->bit);  // 逆序輸出
        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_for_str(n1, root);  // 輸出編碼 (逆序)
    print_code_for_str(n2, root);
    print_code_for_str(n3, root);
    print_code_for_str(n4, root);
}

預期編碼長度：高頻符號編碼短、低頻符號編碼長，符合最優前綴碼性質。

優化方向

• 排序升級：冒泡 O(n²) → 堆/優先隊列 O(n log n)，大幅提升大規模符號集效能。
• 記憶體管理：統一分配節點池，避免頻繁 malloc/free。
• 編碼存儲：用位向量或字串存儲正序編碼，避免每次查詢逆序遍歷。
• 標準化介面：封裝為 huffman_encode/decode 函數，支援流式處理。

核心心得

1. 霍夫曼樹邏輯簡單，手算通順即可編碼；難點在工程細節（記憶體、排序、介面）。
2. 複雜演算法 = 基礎演算法（排序、堆、樹）搭積木；打牢基礎是關鍵。
3. 善用通用框架（如本文泛型排序），減少重複造輪子，提高可維護性。