循序漸進實作演算法：二元搜尋樹節點插入詳解

編輯：關於C語言

前言

二元搜尋樹（BST）的節點插入是資料結構中的基礎操作。雖然邏輯單純，但涉及指標操作、遞歸與迭代選擇、以及測試驅動開發（TDD）的實踐。本文將一步步拆解插入邏輯，從參數檢查到根節點建立、子樹遞歸尋找位置，並附上完整的 C 語言程式碼與測試案例。

核心邏輯拆解

二元搜尋樹插入主要分為兩大步驟：

參數合法性檢查：由於需要修改根節點指標本身（例如樹為空時建立根節點），函數參數採用指標的指標（`TREE_NODE**`），並檢查是否為 `NULL`。
分情況討論插入邏輯：
- 若樹為空（`*ppTreeNode == NULL`），直接建立新節點作為根節點。
- 若樹非空，比較插入值與當前節點值：
  - 值較小 → 往左子樹遞歸尋找插入位置。
  - 值較大 → 往右子樹遞歸尋找插入位置。
  - 值相等 → 依定義不允許重複，直接返回。
  - 找到空位（子節點為 `NULL`） → 建立新節點掛載。

程式碼演進與測試驅動開發（TDD）示範

採用 TDD 方式，分三個階段逐步完善功能：

階段一：僅檢查參數合法性

STATUS insert_node_into_tree(TREE_NODE** ppTreeNode, int data) {
    if (NULL == ppTreeNode)
        return FALSE;
    return TRUE;
}

測試案例：傳入 `NULL` 指標，預期返回 `FALSE`。

static void test1() {
    assert(FALSE == insert_node_into_tree(NULL, 10));
}

階段二：處理樹為空的情況（建立根節點）

STATUS insert_node_into_tree(TREE_NODE** ppTreeNode, int data) {
    if (NULL == ppTreeNode)
        return FALSE;

    if (NULL == *ppTreeNode) {
        *ppTreeNode = (TREE_NODE*)create_tree_node(data);
        assert(NULL != *ppTreeNode);
        return TRUE;
    }
    return TRUE; // 此處暫時未處理非空樹情況
}

測試案例：插入第一個節點，驗證根節點資料正確性。

static void test2() {
    TREE_NODE* pTreeNode = NULL;
    assert(TRUE == insert_node_into_tree(&pTreeNode, 10));
    assert(10 == pTreeNode->data);
    free(pTreeNode);
}

階段三：完整實作遞歸插入邏輯（含父節點指標維護）

引入輔助函數 `_insert_node_into_tree`，傳入父節點指標以利未來擴充（如線索化、平衡因子更新）。

STATUS _insert_node_into_tree(TREE_NODE** ppTreeNode, int data, TREE_NODE* pParent) {
    if (NULL == *ppTreeNode) {
        *ppTreeNode = create_tree_node(data);
        assert(NULL != *ppTreeNode);
        (*ppTreeNode)->parent = pParent; // 維護父節點指標
        return TRUE;
    }

    if (data < (*ppTreeNode)->data)
        return _insert_node_into_tree(&(*ppTreeNode)->left_child, data, *ppTreeNode);
    else if (data > (*ppTreeNode)->data)
        return _insert_node_into_tree(&(*ppTreeNode)->right_child, data, *ppTreeNode);
    else
        return FALSE; // 資料已存在，不重複插入
}

STATUS insert_node_into_tree(TREE_NODE** ppTreeNode, int data) {
    if (NULL == ppTreeNode)
        return FALSE;

    if (NULL == *ppTreeNode) {
        *ppTreeNode = (TREE_NODE*)create_tree_node(data);
        assert(NULL != *ppTreeNode);
        return TRUE;
    }

    return _insert_node_into_tree(ppTreeNode, data, NULL);
}

測試案例：驗證左、右子節點正確掛載。

static void test3() {
    TREE_NODE* pTreeNode = NULL;
    assert(TRUE == insert_node_into_tree(&pTreeNode, 9));
    assert(TRUE == insert_node_into_tree(&pTreeNode, 8));
    assert(TRUE == insert_node_into_tree(&pTreeNode, 10));
    assert(9 == pTreeNode->data);
    assert(8 == pTreeNode->left_child->data);
    assert(10 == pTreeNode->right_child->data);
    // 記憶體釋放略
}