二叉搜尋樹刪除節點完整指南（上）：從參數檢查到根節點刪除

前言

二叉搜尋樹（BST）的刪除操作比插入複雜得多，因為必須處理多種情況並維持樹的有序性質。本文採用「邊寫代碼、邊寫測試」的增量式開發方式，逐步實現一個健壯的刪除函數。我們將從參數合法性檢查開始，逐步涵蓋根節點在各種子樹配置下的刪除邏輯。

核心步驟概覽

1. 參數驗證：檢查樹指標與目標數據是否存在。
2. 根節點刪除：分四種情況處理（無子節點、僅有左/右子節點、左右子節點皆存在）。
3. 普通節點刪除：委派給輔助函數處理（下篇詳細說明）。

1. 參數合法性檢查

首先確保輸入的樹指標有效，並確認目標數據確實存在於樹中。

1.1 基礎指標檢查

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

1.2 數據存在性檢查

引入 find_data_in_tree_node 輔助函數定位目標節點。

STATUS delete_node_from_tree(TREE_NODE** ppTreeNode, int data) {
    TREE_NODE* pTreeNode;

    if (NULL == ppTreeNode || NULL == *ppTreeNode)
        return FALSE;

    pTreeNode = find_data_in_tree_node(*ppTreeNode, data);
    if (NULL == pTreeNode)
        return FALSE;

    return TRUE;
}

測試用例

static void test1() {
    TREE_NODE* pTreeNode = NULL;
    assert(FALSE == delete_node_from_tree(NULL, 10));
    assert(FALSE == delete_node_from_tree(&pTreeNode, 10));
}

static void test2() {
    TREE_NODE* pTreeNode = create_tree_node(10);
    assert(FALSE == delete_node_from_tree(&pTreeNode, 11)); // 數據不存在
    free(pTreeNode);
}

2. 根節點刪除：四種情況全解析

當目標節點即為根節點（*ppTreeNode == pTreeNode）時，需根據其子節點情況調整樹結構。

2.1 無子節點（葉節點）

直接釋放節點並將根指標設為 NULL。

if (*ppTreeNode == pTreeNode) {
    if (NULL == pTreeNode->left_child && NULL == pTreeNode->right_child) {
        *ppTreeNode = NULL;
    }
    free(pTreeNode);
    return TRUE;
}

測試：建立單節點樹(10)，刪除後根應為 NULL。

2.2 僅有左子樹

左子樹根節點提升為新根，並斷開其父指標。

else if (NULL != pTreeNode->left_child && NULL == pTreeNode->right_child) {
    *ppTreeNode = pTreeNode->left_child;
    pTreeNode->left_child->parent = NULL;
}

測試：插入 10, 5, 3 → 刪除 10 → 新根為 5，左子為 3。

2.3 僅有右子樹

對稱處理：右子樹根提升為新根。

else if (NULL == pTreeNode->left_child && NULL != pTreeNode->right_child) {
    *ppTreeNode = pTreeNode->right_child;
    pTreeNode->right_child->parent = NULL;
}

測試：插入 10, 15, 20 → 刪除 10 → 新根為 15，右子為 20。

2.4 左右子樹皆存在（第一部分：左子樹最大節點即為左孩子）

若左子樹的最大節點就是左孩子本身，則左孩子直接取代根，並接管原右子樹。

else {
    TREE_NODE* pLeftMax = find_max_node(pTreeNode->left_child);
    if (pLeftMax == pTreeNode->left_child) {
        *ppTreeNode = pTreeNode->left_child;
        (*ppTreeNode)->right_child = pTreeNode->right_child;
        (*ppTreeNode)->right_child->parent = *ppTreeNode;
        (*ppTreeNode)->parent = NULL;
    }
    // 第二部分（左子樹最大節點非左孩子）將在下篇處理
}
free(pTreeNode);
return TRUE;

測試：插入 10, 6, 5, 15 → 刪除 10 → 新根 6，右子 15，左子 5。

小結

本篇完成了參數驗證與根節點刪除的大部分情況。關鍵在於：善用測試驅動開發，每增加一個分支就編寫對應測試，確保邏輯正確。下一篇將處理「左子樹最大節點非左孩子」的複雜情況，並引入輔助函數處理普通節點刪除。