C 語言先序創建二叉樹失敗的原因與修正方案

問題現象

先序創建二叉樹程序運行後陷入無限輸入等待，無法正常結束創建過程。

核心問題分析

1. 遞歸參數傳遞錯誤：CreateBiTree(T->lchild) 傳遞的是指針值而非指針引用，子遞歸無法修改父節點的 lchild/rchild 指針。
2. 缺少指針初始化：新節點的 lchild 和 rchild 未初始化為 NULL，導致遞歸判斷失敗。
3. 返回值未正確處理：遞歸調用未檢查返回狀態，錯誤無法向上傳播。

修正後完整代碼

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

#define TElemtype char
#define Status int
#define OK 1
#define ERROR 0

typedef struct BiTNode {
    TElemtype data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

Status CreateBiTree(BiTree &T) {  // 關鍵：引用傳遞 BiTree (即 BiTNode**)
    TElemtype temp;
    scanf(" %c", &temp);  // 關鍵：%c 前加空格跳過換行符
    
    if (temp == '0') {
        T = NULL;
        return OK;
    }
    
    T = (BiTree)malloc(sizeof(BiTNode));
    if (!T) {
        printf("NO MEMORY!\n");
        return ERROR;
    }
    
    T->data = temp;
    T->lchild = NULL;  // 關鍵：初始化左右孩子指針
    T->rchild = NULL;
    
    // 關鍵：檢查遞歸返回值
    if (CreateBiTree(T->lchild) != OK) return ERROR;
    if (CreateBiTree(T->rchild) != OK) return ERROR;
    
    return OK;
}

Status PreOrderTraverse(BiTree T) {
    if (T) {
        printf("%c ", T->data);
        PreOrderTraverse(T->lchild);
        PreOrderTraverse(T->rchild);
    }
    return OK;
}

int main() {
    printf("請按先序輸入字符（0 表示空節點）：\n");
    BiTree T;
    CreateBiTree(T);
    printf("\n先序遍歷結果：\n");
    PreOrderTraverse(T);
    printf("\n");
    getch();
    return 0;
}

關鍵修正點詳解

輸入示例與對應樹結構

輸入：A B 0 0 C 0 0

    A
   / \
  B   C
 / \ / \
0  0 0 0

先序遍歷輸出：A B C

C 語言版本適配提示

若必須使用純 C（無引用），將函數簽名改為：

Status CreateBiTree(BiTree *T) {  // 二級指針
    // ...
    *T = (BiTree)malloc(...);
    // 遞歸調用：
    CreateBiTree(&(*T)->lchild);
    CreateBiTree(&(*T)->rchild);
}

總結

• 二叉樹創建的核心是指針引用/二級指針配合遞歸下傳。
• 輸入處理需注意空白字符過濾。
• 新節點必須初始化子指針為 NULL。
• 遞歸函數應檢查並傳播返回狀態。