您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C >> 關於C

演算法實作筆記：二元搜尋樹（BST）節點刪除完整指南

編輯：關於C

前言

二元搜尋樹（Binary Search Tree, BST）的刪除操作是資料結構教學與面試中的「必考題」。它綜合考察指標操作、樹形結構不變量維護、邊界情況處理。本文將刪除操作拆解為四大基本情況，逐步給出 C 語言實作與測試策略。

BST 節點定義


typedef struct TreeNode {
    int data;
    struct TreeNode *left, *right, *parent;
} TreeNode;

含 parent 指標可簡化刪除時的父節點連接更新；若無 parent 指標，需用雙重指標或遞迴返回新子樹根。

四大刪除情況

情況 1：葉子節點（無左、無右）

直接斷開父節點對應的子指標，free 該節點。

情況 2：僅有左子樹（無右）

將左子樹根接上父節點，更新左子樹根的 parent，free 原節點。

情況 3：僅有右子樹（無左）

同情況 2，改接右子樹。

情況 4：左右子樹皆存在（核心難點）

策略：找前驅節點（左子樹中最大值節點，即「左子樹最右下角」）或後繼節點（右子樹最小值）。本文採用前驅。

在左子樹中找最大節點 maxNode（無右孩子）。
若 maxNode 就是左孩子（即左子樹無右分支）：
- 將 maxNode 接上父節點；
- maxNode->right = delNode->right，更新右子樹 parent；
否則（maxNode 深在左子樹右鏈深處）：
- 將 maxNode->data 複製給 delNode（資料交換）；
- 刪除 maxNode（此時 maxNode 必屬於情況 1 或 2，遞迴或直接處理）。

核心程式碼實作

輔助：尋找左子樹最大節點


TreeNode* find_max(TreeNode *root) {
    while (root && root->right) root = root->right;
    return root;
}

內部刪除函數（假設節點非根）


bool delete_node_internal(TreeNode *del) {
    TreeNode *maxLeft;
    if (!del->left && !del->right) {                    // 情況 1
        if (del == del->parent->left) del->parent->left = NULL;
        else del->parent->right = NULL;
    }
    else if (del->left && !del->right) {                // 情況 2
        del->left->parent = del->parent;
        if (del == del->parent->left) del->parent->left = del->left;
        else del->parent->right = del->left;
    }
    else if (!del->left && del->right) {                // 情況 3
        del->right->parent = del->parent;
        if (del == del->parent->left) del->parent->left = del->right;
        else del->parent->right = del->right;
    }
    else {                                              // 情況 4
        maxLeft = find_max(del->left);
        if (maxLeft == del->left) {                     // 4.1 最大節點即左孩子
            maxLeft->parent = del->parent;
            if (del == del->parent->left) del->parent->left = maxLeft;
            else del->parent->right = maxLeft;
            maxLeft->right = del->right;
            del->right->parent = maxLeft;
        } else {                                        // 4.2 最大節點深在右鏈
            del->data = maxLeft->data;                  // 複製資料
            // maxLeft 必無右孩子，只可能有左孩子 → 遞迴刪除 maxLeft
            return delete_node_internal(maxLeft);       // 尾遞迴，安全
        }
    }
    free(del);
    return true;
}

公開介面：處理根節點刪除


bool bst_delete(TreeNode **rootPtr, int key) {
    if (!rootPtr || !*rootPtr) return false;
    TreeNode *target = bst_find(*rootPtr, key);  // 假設已實作查找
    if (!target) return false;

    if (target == *rootPtr) {                    // 刪除根節點
        if (!target->left && !target->right) { *rootPtr = NULL; }
        else if (target->left && !target->right) {
            *rootPtr = target->left; target->left->parent = NULL;
        }
        else if (!target->left && target->right) {
            *rootPtr = target->right; target->right->parent = NULL;
        }
        else {
            TreeNode *maxLeft = find_max(target->left);
            if (maxLeft == target->left) {
                *rootPtr = maxLeft;
                maxLeft->parent = NULL;
                maxLeft->right = target->right;
                target->right->parent = maxLeft;
            } else {
                target->data = maxLeft->data;
                return delete_node_internal(maxLeft);
            }
        }
        free(target);
        return true;
    }
    return delete_node_internal(target);
}

測試策略：以斷言驅動開發

針對每種情況編寫獨立測試函數，建構最小樹、執行刪除、驗證結構與中序遍歷有序性：


void test_delete_leaf(void) {
    TreeNode *root = NULL;
    bst_insert(&root, 10);
    bst_insert(&root, 6);
    bst_insert(&root, 15);
    assert(bst_delete(&root, 6));
    assert(root->left == NULL);
    assert(bst_inorder_check(root));  // 驗證 BST 性質
    bst_free(root);
}

void test_delete_two_children_deep(void) {
    TreeNode *root = NULL;
    bst_insert(&root, 10);
    bst_insert(&root, 6);
    bst_insert(&root, 5);
    bst_insert(&root, 8);
    assert(bst_delete(&root, 6));  // 刪除 6，前驅為 5
    assert(root->left->data == 5);
    assert(root->left->right->data == 8);
    assert(bst_inorder_check(root));
    bst_free(root);
}

常見錯誤與避坑指南

錯誤類型	現象	修正
忘記更新 parent	父節點指向舊記憶體，遍歷崩潰	每次重掛子樹必雙向更新 `parent`
根節點特殊情況漏處理	刪除根後樹根指標未更新	公開介面優先判斷 `target == *rootPtr`
情況 4 複製資料後未刪除前驅	樹中出現重複鍵值，記憶體洩漏	複製後必須遞迴/迭代刪除 `maxLeft`
測試未覆蓋「左子樹最大節點有左孩子」	情況 4.2 邏輯未驗證	構造 `5 (left: 2, right: 8)` 刪除 5，前驅 4 有左孩子 2

總結

BST 刪除的核心在於「情況 4 轉化為情況 1/2」的前驅/後繼替換法。掌握「找前驅 → 判斷相對位置 → 複製資料或重掛子樹 → 遞迴清理」的標準流程，配合完整的單元測試矩陣（4 情況 × 根/非根 × 左/右），即可自信應對面試與工程實作。進階可研究紅黑樹、AVL 樹在刪除後的平衡調整，原理同源但細節更繁。