C 語言二叉樹非遞歸實作：建立、遍歷、路徑、深度、葉子、鏡像完整修正版

原始碼主要缺陷

1. CreateBiTree 參數傳遞錯誤： 使用 BinTree &bt (C++ 參考) 而非 C 語法 BinTree *bt，且遞歸呼叫未傳址，導致根節點無法回傳。
2. 中序遍歷堆疊邏輯錯誤： stack[top]=bt 初始化後未判空直接入堆疊，stack[top]=stack[top-1]->lchild 易導致野指標。
3. 尋找節點路徑演算法過度複雜且錯誤： 使用 tag 標記但邏輯混亂，回傳值型別不匹配。
4. 全域變數 found, p 耦合度高，非執行緒安全。
5. 主選單 bt 未初始化，Case 1 建樹後未賦值回主函式。
6. 使用 gets/scanf 混用導致緩衝區殘留字元干擾。

重構要點

• 統一使用 指標的指標 (BinTree *) 傳遞根節點，函式回傳 Status 表示成功/失敗。
• 採用 標準非遞歸中序遍歷模板：while (p || top != -1) { while(p) push(p), p=p->lchild; p=pop(); visit(p); p=p->rchild; }
• 路徑查找改用 遞歸回溯 或 堆疊儲存路徑，邏輯清晰可維護。
• 移除全域變數，改以函式參數/回傳值傳遞狀態。
• 輸入介面改用 getchar() 讀單字元，以 # 代表空節點，避免空格歧義。

核心函式修正版節選

/* 建立二叉樹：先序輸入，# 表空節點 */
Status CreateBiTree(BinTree *T) {
    char ch;
    scanf(" %c", &ch);  // 空格跳過換行/空白
    if (ch == '#') {
        *T = NULL;
    } else {
        *T = (BinTNode *)malloc(sizeof(BinTNode));
        if (!*T) return ERROR;
        (*T)->data = ch;
        CreateBiTree(&(*T)->lchild);
        CreateBiTree(&(*T)->rchild);
    }
    return OK;
}

/* 非遞歸中序遍歷 */
Status InorderTraverse(BinTree T) {
    BinTNode *stack[MAXSIZE];
    int top = -1;
    BinTNode *p = T;
    while (p || top != -1) {
        while (p) {
            stack[++top] = p;
            p = p->lchild;
        }
        p = stack[top--];
        printf("%c ", p->data);
        p = p->rchild;
    }
    return OK;
}

/* 尋找節點並回傳路徑 (遞歸回溯) */
bool FindPath(BinTree T, char target, BinTNode **path, int *len) {
    if (!T) return false;
    path[(*len)++] = T;
    if (T->data == target) return true;
    if (FindPath(T->lchild, target, path, len) || FindPath(T->rchild, target, path, len))
        return true;
    (*len)--;
    return false;
}

/* 深度、葉子數、鏡像交換遞歸寫法簡潔正確，保留即可 */
int TreeDepth(BinTree T) { ... }
int LeafCount(BinTree T) { ... }
BinTree MirrorTree(BinTree T) { ... }

主程式架構調整

int main() {
    BinTree root = NULL;
    int choice;
    while (1) {
        print_menu();
        scanf("%d", &choice); getchar();
        switch (choice) {
            case 1: CreateBiTree(&root); puts("建樹完成"); break;
            case 2: InorderTraverse(root); putchar('\n'); break;
            case 3: { /* 讀目標字元 -> FindPath -> 印路徑 */ } break;
            case 4: printf("深度=%d\n", TreeDepth(root)); break;
            case 5: printf("葉子數=%d\n", LeafCount(root)); break;
            case 6: root = MirrorTree(root); puts("鏡像完成"); break;
            case 0: FreeTree(root); return 0;
        }
    }
}

避坑提醒

• 遞歸建樹深度受限於堆疊大小，超過 10⁴ 節點易棧溢位；生產環境建議非遞歸或顯式堆疊。
• malloc 失敗必須檢查回傳值，避免解參考空指標。
• 選單迴圈務必清空輸入緩衝區 (while(getchar()!='\n');)，防止殘留字元導致無限迴圈。

總結

二叉樹基本操作是資料結構核心功課。掌握 指標傳址建樹、非遞歸遍歷模板、遞歸回溯找路徑 三大模式，即可應對絕大多數考試與面試題目。程式碼簡潔、邊界處理完善、記憶體管理正確，才是合格的 C 語言實作。