二叉搜尋樹刪除節點完整指南（下）：前驅節點替換與普通節點刪除

接續上篇：根節點左右子樹皆存之複雜情況

上篇處理了左子樹最大節點即為左孩子的簡單情況。本篇解決「左子樹最大節點位於左子樹深處」的一般情況，並引入遞歸輔助函數統一處理普通節點刪除。

2.4 根節點刪除：左子樹最大節點非左孩子

此時需找到左子樹中的最大節點（前驅節點），將其數據複製到根節點，然後刪除該前驅節點（它至多只有左子樹）。

算法邏輯

1. 在左子樹中尋找最大節點 pLeftMax。
2. 將 pLeftMax->data 複製到當前根節點。
3. 從左子樹中移除 pLeftMax（因為它是最大值，必無右子樹，直接讓其父節點的右指標指向其左子樹即可）。
4. 釋放 pLeftMax。

代碼實現

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;
    } else {
        // 一般情況：前驅節點在左子樹深處
        pTreeNode->data = pLeftMax->data;        // 複製數據
        pLeftMax->parent->right_child = pLeftMax->left_child; // 繞過 pLeftMax
        if (pLeftMax->left_child)
            pLeftMax->left_child->parent = pLeftMax->parent;
        pTreeNode = pLeftMax; // 待釋放節點改為 pLeftMax
    }
}
free(pTreeNode);
return TRUE;

測試用例

static void test7() {
    TREE_NODE* pTreeNode = NULL;
    assert(TRUE == insert_node_into_tree(&pTreeNode, 10));
    assert(TRUE == insert_node_into_tree(&pTreeNode, 6));
    assert(TRUE == insert_node_into_tree(&pTreeNode, 8)); // 6 的右孩子，為左子樹最大值
    assert(TRUE == insert_node_into_tree(&pTreeNode, 15));
    assert(TRUE == delete_node_from_tree(&pTreeNode, 10));
    assert(8 == pTreeNode->data);           // 新根數據為 8
    assert(NULL == pTreeNode->parent);
    assert(NULL == pTreeNode->left_child->right_child); // 原 8 節點已被移除
    // 釋放記憶體...
}

3. 普通節點刪除：統一委派給輔助函數

當目標節點非根節點時，邏輯與根節點刪除高度相似，但需處理父節點的指標更新。為避免代碼重複，提取 _delete_node_from_tree 專門處理非根節點。

主函數最終形態

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

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

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

    if (*ppTreeNode == pTreeNode) {
        // 根節點刪除邏輯（同上，省略）
        // ...
        free(pTreeNode);
        return TRUE;
    }

    // 非根節點：委派給輔助函數
    return _delete_node_from_tree(pTreeNode);
}

輔助函數 _delete_node_from_tree 設計要點

• 參數為待刪除節點指標（非指標的指標），因父節點已知。
• 需根據該節點是父節點的左孩子還是右孩子，更新父節點對應指標。
• 刪除邏輯與根節點完全對稱：無子、單子、雙子（找前驅替換）。
• 處理完後釋放節點記憶體。

完整代碼將在後續文章展示，核心思想是「找前驅覆蓋數據，再刪除前驅節點」，將雙子刪除轉化為單子/無子刪除。

總結

1. 根節點刪除：四種子樹配置全覆蓋，關鍵在於正確維護父指標與根指標。
2. 前驅節點替換法：雙子節點刪除的標準解法，保證 BST 性質不變。
3. 代碼復用：透過輔助函數統一處理普通節點，減少重複邏輯。
4. 測試驅動：每個分支對應專用測試用例，確保邊界條件正確。

掌握這些模式，即可實現高可靠度的 BST 刪除操作。