C++中 int createBiTree(BiTree &r) 參數含義詳解

問題背景

在學習二叉樹構建代碼時，經常遇到如下函數簽名：

int createBiTree(BiTree &r);

初學者常見疑問：結構體明明用 BiNode 定義，為何參數卻用 BiTree？這其實涉及 C/C++ 中 typedef 的指針別名機制。

結構體與類型定義剖析

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

這裡一次定義了兩個類型別名：

• BiTNode：代表結構體 struct BiNode 本身（值類型）。
• BiTree：代表 指向該結構體的指針（即 struct BiNode*）。

因此 BiTree 本質上是 BiNode*，所以函數參數 BiTree &r 實際上是 二級指針引用（BiNode* &r），用於在函數內部修改外部的根節點指針。

代碼邏輯解讀

int createBiTree(BiTree &r) {
    flag = 0;
    cin >> temp;
    if (temp.length() == 1 && temp[0] == '#') {
        r = NULL;  // 遇到 '#' 表示空節點
    } else {
        flag = 1;  // 標記有效節點
        // 此處應續接節點創建與遞歸構建左右子樹的代碼
    }
    return flag;
}

關鍵點：

1. 引用傳遞：&r 確保對根指針的修改（如 r = new BiTNode 或 r = NULL）能反映到調用方。
2. 輸入約定：以 # 表示空節點，符合二叉樹先序遍歷構建的經典輸入格式。
3. 返回值：flag 指示是否成功創建節點，便於上層遞歸判斷。

常見誤區與最佳實踐

誤區：混淆 BiTNode 與 BiTree

若錯寫為 int createBiTree(BiTNode &r)，則傳遞的是結構體對象而非指針，無法構建動態鏈表結構，且會導致遞歸時對象切片、內存佈局錯誤。

最佳實踐建議

• 使用更清晰的現代 C++ 寫法：using BiTree = BiNode*; 替代 typedef。
• 改用智能指針（unique_ptr<BiNode>）自動管理內存，避免手動 new/delete 洩漏風險。
• 輸入驗證：檢查 cin 狀態，防止非法輸入導致死循環。

總結

BiTree 是節點指針的別名，BiTree &r 使函數能直接修改調用者的根指針，這是 C 語言風格二叉樹構建的核心技巧。理解 typedef 指針別名與引用傳遞的配合，是掌握樹形結構動態構建的關鍵。