二叉樹構建陷阱：指針參數傳遞與引用的深度剖析

編輯：關於C語言

前言：一個看似簡單的遞歸建樹失敗

近期複習資料結構，編寫二叉樹建立與遍歷程式。雖然功能單純，卻踩中指針參數傳遞的經典陷阱。本文記錄問題發現、分析與解決全過程，以供參考。

核心問題：指針作為參數，為什麼主調函數的指針沒變？

現象重現

// 錯誤版本
void PreOrderCreateBinaryTree(BiTreeNode* pNode) {
    char ch;
    scanf("%c", &ch);
    if (ch == '#') {
        pNode = NULL;
    } else {
        pNode = (BiTreeNode*)malloc(sizeof(BiTreeNode));
        pNode->data = ch;
        PreOrderCreateBinaryTree(pNode->left);
        PreOrderCreateBinaryTree(pNode->right);
    }
}

int main() {
    BiTreeNode* pHeadNode = NULL;
    PreOrderCreateBinaryTree(pHeadNode);  // 傳入 NULL
    // 此時 pHeadNode 依然是 NULL！
    PreOrderTraverse(pHeadNode);  // 無任何輸出
}

深度分析：值傳遞的本質

關鍵誤區：「指針傳遞可以修改指向的內容」≠「可以修改指針變量本身的值」。

main 中的 pHeadNode 是一個指針變量，初值為 NULL。
PreOrderCreateBinaryTree 的形參 pNode 是另一個指針變量，初值同樣為 NULL（值傳遞複製）。
函數內部 pNode = malloc(...) 修改的是 形參指針變量本身的值（指向新分配的記憶體），並未改變實參 pHeadNode 的值。
函數返回後，pHeadNode 仍指向 NULL，導致樹根丟失，所有節點成為孤立記憶體塊（記憶體洩漏）。

對比示例

// 修改指向的內容：實參受影響
void FuncChangeObj(int* pInt) { *pInt = 20; }

// 修改指針本身：實參不變
void FuncNoChangeObj(int* pInt) { pInt = (int*)malloc(sizeof(int)); *pInt = 30; }

解決方案

方法一：函數返回指針，主調函數接收賦值（純 C 風格）

BiTreeNode* PreOrderCreateBinaryTree() {
    char ch;
    scanf("%c", &ch);
    if (ch == '#') return NULL;
    
    BiTreeNode* pNode = (BiTreeNode*)malloc(sizeof(BiTreeNode));
    pNode->data = ch;
    pNode->left = PreOrderCreateBinaryTree();
    pNode->right = PreOrderCreateBinaryTree();
    return pNode;
}

int main() {
    BiTreeNode* pHeadNode = PreOrderCreateBinaryTree();  // 接收返回值
    PreOrderTraverse(pHeadNode);
}

方法二：使用指針的引用傳遞（需 C++ 編譯器）

void PreOrderCreateBiTree2(BiTreeNode*& pNode) {  // 參數為指針引用
    char ch;
    scanf("%c", &ch);
    if (ch == '#') {
        pNode = NULL;
    } else {
        pNode = (BiTreeNode*)malloc(sizeof(BiTreeNode));
        pNode->data = ch;
        PreOrderCreateBiTree2(pNode->left);
        PreOrderCreateBiTree2(pNode->right);
    }
}
// 此法在 C 語言編譯器下無法編譯，因 C 無引用概念

方法三：傳遞指針的指針（二級指針，純 C 可行）

void PreOrderCreateBinaryTree3(BiTreeNode** ppNode) {
    char ch;
    scanf("%c", &ch);
    if (ch == '#') {
        *ppNode = NULL;
    } else {
        *ppNode = (BiTreeNode*)malloc(sizeof(BiTreeNode));
        (*ppNode)->data = ch;
        PreOrderCreateBinaryTree3(&(*ppNode)->left);
        PreOrderCreateBinaryTree3(&(*ppNode)->right);
    }
}

int main() {
    BiTreeNode* pHeadNode = NULL;
    PreOrderCreateBinaryTree3(&pHeadNode);  // 傳遞指針地址
}