12、二叉搜索树的删除：BST删除操作的三种情况

二叉搜索树的删除，说实话，是BST操作里最容易出bug的地方。我在项目里见过不少同事，插入和查找写得飞起，一到删除就翻车。为什么？因为删除要考虑的情况比插入复杂得多——你得保证删完之后，树依然是二叉搜索树。

嗯，咱们今天就把这个硬骨头啃下来。我会把三种情况拆开讲，配上代码，再聊聊我踩过的坑。

删除操作的核心思路

删除一个节点，说白了就是三步：

1. 找到它——定位要删除的节点
2. 处理它——根据它的孩子情况决定怎么删
3. 修复树——保证删除后BST性质不变

你想想看，最难的是第二步。一个节点可能有0个、1个或2个孩子，每种情况处理方式完全不同。

情况一：删除叶子节点

这是最简单的情况。叶子节点没有孩子，直接把它从父节点上摘掉就行。就像从树上摘一片叶子，不会影响其他部分。

我记得第一次写删除时，觉得叶子节点太简单了，结果忘了处理根节点是叶子的情况——如果树只有一个节点，删除后根指针要置为NULL。这个细节很容易漏。

情况二：删除只有一个孩子的节点

这种情况也还算直接。节点只有一个左孩子或一个右孩子，那就让孩子"顶替"它的位置。

说白了就是：把当前节点从链表中"跳过"，让父节点直接指向它的孩子。

情况三：删除有两个孩子的节点

这才是重头戏。如果一个节点有两个孩子，你不能直接删，因为两个孩子没法同时顶替它的位置。

怎么办？我告诉你一个经典做法：

1. 找到要删除节点的中序后继（右子树中最小的节点）或中序前驱（左子树中最大的节点）
2. 用这个后继节点的值覆盖要删除的节点
3. 然后删除那个后继节点——它一定属于情况一或情况二

为什么会这样？因为中序后继要么是叶子，要么只有一个右孩子。你想想看，右子树中最小的节点，它不可能有左孩子，对吧？

三种情况对比

情况	孩子数量	处理方式	复杂度
叶子节点	0	直接删除，父节点指针置NULL	O(1)
单孩子节点	1	孩子顶替当前位置	O(1)
双孩子节点	2	找中序后继，值覆盖，再删除后继	O(h)，h为树高

C语言完整实现

下面是我个人比较喜欢的一种写法。我习惯用一个辅助函数来找到右子树的最小节点，这样主函数逻辑更清晰。

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

// 找到以node为根的子树中的最小值节点
Node* findMin(Node* node) {
    while (node->left != NULL) {
        node = node->left;
    }
    return node;
}

// 删除二叉搜索树中的指定值
Node* deleteNode(Node* root, int key) {
    // 基本情况：树为空或没找到
    if (root == NULL) {
        return root;
    }

    // 递归查找要删除的节点
    if (key < root->data) {
        root->left = deleteNode(root->left, key);
    } else if (key > root->data) {
        root->right = deleteNode(root->right, key);
    } else {
        // 找到了要删除的节点
        // 情况1：叶子节点
        if (root->left == NULL && root->right == NULL) {
            free(root);
            return NULL;
        }
        // 情况2：只有一个孩子
        else if (root->left == NULL) {
            Node* temp = root->right;
            free(root);
            return temp;
        } else if (root->right == NULL) {
            Node* temp = root->left;
            free(root);
            return temp;
        }
        // 情况3：有两个孩子
        else {
            // 找到右子树的最小节点（中序后继）
            Node* successor = findMin(root->right);
            // 用后继的值覆盖当前节点
            root->data = successor->data;
            // 删除后继节点
            root->right = deleteNode(root->right, successor->data);
        }
    }
    return root;
}

删除操作的流程图

下面这张图把整个删除流程串起来了，你可以对照着代码看：

实际项目中的避坑指南

我在实际项目中用过BST做内存管理，删除操作有几个地方特别容易出问题：

• 递归深度：如果树退化成链表，递归删除可能导致栈溢出。我建议在关键系统中加一个深度限制，或者改用迭代版本。
• 内存泄漏：free节点后，一定要确保没有任何指针还指向它。我习惯在free之后把局部指针置为NULL，虽然C语言里这更多是心理安慰，但能帮你养成好习惯。
• 重复值处理：BST通常不允许重复值，但如果你非要支持，删除时要明确删除的是哪一个。我一般约定删除第一个遇到的。

删除操作是BST里最考验基本功的地方。你如果能把这个写对，说明你对指针操作和递归的理解已经到位了。嗯，多写几遍，自然就熟了。

---

公众号:蓝海资料掘金营，微信deep3321