哈夫曼樹完整實現：構建、遍歷、編碼、解碼與打印

功能清單

1. 輸入字符集與權值，構建哈夫曼樹。
2. 遍歷打印樹結構（驗證構建正確性）。
3. 生成並輸出每字符的哈夫曼編碼。
4. 編碼：輸入明文串，輸出 0/1 編碼串。
5. 解碼：輸入 0/1 編碼串，輸出原明文。

核心數據結構

#define MAX_NODES 200
#define INF 9999

typedef struct {
    char data;      // 字符
    int weight;     // 權值
    int parent;     // 父節點索引
    int lchild;     // 左子節點索引
    int rchild;     // 右子節點索引
} HuffmanNode;

typedef struct {
    char bits[50];  // 編碼位串（反向存儲）
    int start;      // 有效編碼起始位置
} HuffmanCode;

HuffmanNode HT[MAX_NODES];
HuffmanCode HC[MAX_NODES];

關鍵算法步驟

1. 構建哈夫曼樹（經典 O(n²) 選最小兩棵合併）

void buildHuffmanTree(int n) {
    // 初始化 2n-1 個節點
    for (int i = 0; i < 2*n-1; i++) {
        HT[i].parent = HT[i].lchild = HT[i].rchild = -1;
    }
    // 輸入前 n 個葉子節點
    for (int i = 0; i < n; i++) {
        printf("字符 %d: ", i); scanf(" %c", &HT[i].data);
        printf("權值 %d: ", i); scanf("%d", &HT[i].weight);
    }
    // 合併 n-1 次
    for (int i = n; i < 2*n-1; i++) {
        int min1 = INF, min2 = INF, idx1 = -1, idx2 = -1;
        for (int j = 0; j < i; j++) {
            if (HT[j].parent == -1) {  // 僅考慮無父節點
                if (HT[j].weight < min1) {
                    min2 = min1; idx2 = idx1;
                    min1 = HT[j].weight; idx1 = j;
                } else if (HT[j].weight < min2) {
                    min2 = HT[j].weight; idx2 = j;
                }
            }
        }
        HT[idx1].parent = HT[idx2].parent = i;
        HT[i].lchild = idx1; HT[i].rchild = idx2;
        HT[i].weight = min1 + min2;
    }
}

2. 樹的遍歷打印（遞歸中序，帶縮進可視化）

void printTree(int root, int depth) {
    if (root == -1) return;
    printTree(HT[root].rchild, depth + 1);
    for (int i = 0; i < depth; i++) printf("    ");
    printf("%c(%d)\n", HT[root].data ? HT[root].data : '*', HT[root].weight);
    printTree(HT[root].lchild, depth + 1);
}
// 調用：printTree(2*n-2, 0);  // 根節點索引為 2n-2

3. 生成哈夫曼編碼（從葉子向根回溯）

void generateCodes(int n) {
    for (int i = 0; i < n; i++) {
        HC[i].start = n;  // 從末尾向前填
        int c = i, p = HT[c].parent;
        while (p != -1) {
            if (HT[p].lchild == c) HC[i].bits[HC[i].start--] = '0';
            else HC[i].bits[HC[i].start--] = '1';
            c = p; p = HT[c].parent;
        }
        HC[i].start++;  // 指向第一個有效編碼位
    }
}

4. 編碼與解碼主邏輯

void encode(const char *msg, int n) {
    for (int i = 0; msg[i]; i++) {
        for (int j = 0; j < n; j++) {
            if (msg[i] == HT[j].data) {
                printf("%s", &HC[j].bits[HC[j].start]);
                break;
            }
        }
    }
    printf("\n");
}

void decode(const char *code, int n) {
    int p = 2*n - 2;  // 從根開始
    for (int i = 0; code[i]; i++) {
        p = (code[i] == '0') ? HT[p].lchild : HT[p].rchild;
        if (p < n) {  // 到達葉子
            printf("%c", HT[p].data);
            p = 2*n - 2;  // 重置到根
        }
    }
    printf("\n");
}

完整 main 流程

int main() {
    int n;
    printf("字符種類數: "); scanf("%d", &n);
    buildHuffmanTree(n);
    printf("\n=== 哈夫曼樹結構 ===\n");
    printTree(2*n-2, 0);
    generateCodes(n);
    printf("\n=== 哈夫曼編碼表 ===\n");
    for (int i = 0; i < n; i++) {
        printf("%c: %s\n", HT[i].data, &HC[i].bits[HC[i].start]);
    }
    char msg[100], code[200];
    printf("\n輸入明文編碼: "); scanf("%s", msg); encode(msg, n);
    printf("輸入編碼解碼: "); scanf("%s", code); decode(code, n);
    return 0;
}

常見坑與優化

• 數組越界：HT 大小至少 2*MAX_CHAR-1，bits 長度 ≥ 樹高（≤ n）。
• 字符輸入：scanf(" %c") 前加空格跳過空白，避免讀到換行符。
• 編碼存儲方向：從葉子向根回溯得到的是逆序，用 start 索引標記有效段起始，輸出時正序打印。
• 優化選最小：用最小堆將構建複雜度從 O(n²) 降為 O(n log n)。

這份代碼涵蓋了哈夫曼樹「建、遍、編、解、印」全流程，是數據結構課程設計、面試手寫、壓縮算法入門的標準參考實現。