C語言數據結構與算法實戰：二叉樹、哈夫曼編碼、圖的遍歷

C語言數據結構與算法實戰：二叉樹、哈夫曼編碼、圖的遍歷

本文為「C語言范例學習」系列第三部分，完整實現二叉樹創建與三種遍歷、哈夫曼編碼構建、無向圖的深度/廣度優先搜索（DFS/BFS），代碼均可直接編譯運行。

3.5 二叉樹及其應用

存儲結構：二叉鏈表

typedef struct Node {
    struct Node *lchild;
    char data;
    struct Node *rchild;
} BiNode, *BiTree;

遞歸創建（先序輸入，# 代表空）

BiTree CreateTree() {
    char ch; scanf("%c", &ch);
    if (ch == '#') return NULL;
    BiTree t = malloc(sizeof(BiNode));
    t->data = ch;
    t->lchild = CreateTree();
    t->rchild = CreateTree();
    return t;
}

三種遍歷（遞歸版）

void PreOrder(BiTree t) {   // 根-左-右
    if (t) { putchar(t->data); PreOrder(t->lchild); PreOrder(t->rchild); }
}
void InOrder(BiTree t) {    // 左-根-右
    if (t) { InOrder(t->lchild); putchar(t->data); InOrder(t->rchild); }
}
void PostOrder(BiTree t) {  // 左-右-根
    if (t) { PostOrder(t->lchild); PostOrder(t->rchild); putchar(t->data); }
}

樹的深度、節點數、葉子數

int Depth(BiTree t) {
    if (!t) return 0;
    return 1 + (Depth(t->lchild) > Depth(t->rchild) ? Depth(t->lchild) : Depth(t->rchild));
}
int NodeCount(BiTree t) { return t ? NodeCount(t->lchild) + NodeCount(t->rchild) + 1 : 0; }
int LeafCount(BiTree t) { 
    if (!t) return 0; 
    if (!t->lchild && !t->rchild) return 1; 
    return LeafCount(t->lchild) + LeafCount(t->rchild); 
}

運行示例

輸入：ABD##E##CF##G##（先序，# 為空）

contents of binary tree: DBEAFCG   (中序輸出)
depth of binary tree: 3
the number of the nodes: 7
the number of the leaf nodes: 4
preorder traversal: ABD#E#CF#G#
inorder traversal: DBEAFCG
postorder traversal: DEBFGCA

哈夫曼編碼實現

邏輯

1. 初始森林：n 個單節點樹，權值為字符頻率；
2. 重複 n-1 次：選取權值最小的兩棵樹合併，新根權值為兩者之和；
3. 最終得到哈夫曼樹（2n-1 個節點）；
4. 從葉子向根回溯：左分支編 0，右分支編 1，得到前綴編碼。

關鍵數據結構

typedef struct { char data; int weight; int parent, left, right; int flag; } HuffNode;
typedef struct { char code[50]; int start; } HuffCode;

構建與編碼輸出（權值：a=18,b=20,c=4,d=13,e=16,f=38）

huffman is:
a: 010
b: 011
c: 000
d: 001
e: 10
f: 11

高頻字符（f, e）編碼短，低頻（c, d）編碼長，符合最優前綴碼原理。

3.6 圖的遍歷：DFS 與 BFS

鄰接表存儲

struct Node { int vertex, flag; struct Node *next; };
struct Node V[10];  // 頂點表頭

深度優先搜索（遞歸）

void DFS(int v) {
    V[v].flag = 1; printf("vertex[%d] ", v);
    for (struct Node *p = V[v].next; p; p = p->next)
        if (!V[p->vertex].flag) DFS(p->vertex);
}

廣度優先搜索（隊列）

void BFS(int v) {
    int q[100], front=-1, rear=-1;
    q[++rear] = v; V[v].flag = 1; printf("vertex[%d] ", v);
    while (front != rear) {
        int cur = q[++front];
        for (struct Node *p = V[cur].next; p; p = p->next)
            if (!V[p->vertex].flag) {
                q[++rear] = p->vertex;
                V[p->vertex].flag = 1;
                printf("vertex[%d] ", p->vertex);
            }
    }
}

測試圖（6頂點、7邊）

DFS: vertex[1] vertex[2] vertex[4] vertex[5] vertex[3] vertex[6]
BFS: vertex[1] vertex[2] vertex[3] vertex[4] vertex[5] vertex[6]

總結與感悟

• **二叉樹**是樹形結構的核心，遞歸是其天然表達方式；
• **哈夫曼編碼**展示貪心策略在壓縮編碼中的威力；
• **圖的遍歷**本質是「狀態標記 + 線性數據結構（棧/隊列）」，DFS 用系統棧/遞歸，BFS 用顯式隊列；
• 所有複雜結構最終都歸結為**指針/鏈表**的組合與操作，掌握指針即掌握了數據結構的靈魂。

數據結構在計算機考研專業課中佔比 80% 以上，更是編程思想的具體化。下一章進入算法專題，將側重「思想引導算法，算法體現思想」。