C语言实现二叉搜索树（BST）删除操作详解（从零开始掌握C语言BST删除操作）

BST 删除操作的三种情况

删除一个节点时，根据该节点的子节点数量，可分为以下三种情况：

1. 叶子节点（无子节点）：直接删除即可。
2. 只有一个子节点：将其父节点指向它的唯一子节点，然后删除该节点。
3. 有两个子节点：找到其中序后继（右子树中的最小节点）或中序前驱（左子树中的最大节点），用该值替换当前节点的值，再递归删除那个后继/前驱节点。

C语言代码实现

下面是一个完整的 C 语言实现，包含节点定义、插入、查找最小值以及删除操作。

#include <stdio.h>#include <stdlib.h>// 定义二叉搜索树节点结构typedef struct Node {    int data;    struct Node* left;    struct Node* right;} Node;// 创建新节点Node* createNode(int value) {    Node* newNode = (Node*)malloc(sizeof(Node));    newNode->data = value;    newNode->left = NULL;    newNode->right = NULL;    return newNode;}// 插入节点（用于构建BST）Node* insert(Node* root, int value) {    if (root == NULL) {        return createNode(value);    }    if (value < root->data) {        root->left = insert(root->left, value);    } else if (value > root->data) {        root->right = insert(root->right, value);    }    return root;}// 查找最小值节点（用于删除有两个子节点的情况）Node* findMin(Node* root) {    while (root && root->left != NULL) {        root = root->left;    }    return root;}// 删除节点函数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) {            Node* temp = root->right;            free(root);            return temp;        } else if (root->right == NULL) {            Node* temp = root->left;            free(root);            return temp;        }        // 情况2：有两个子节点        Node* temp = findMin(root->right); // 找中序后继        root->data = temp->data; // 替换值        root->right = deleteNode(root->right, temp->data); // 删除后继节点    }    return root;}// 中序遍历（用于验证结果）void inorder(Node* root) {    if (root != NULL) {        inorder(root->left);        printf("%d ", root->data);        inorder(root->right);    }}// 主函数测试int main() {    Node* root = NULL;    root = insert(root, 50);    insert(root, 30);    insert(root, 20);    insert(root, 40);    insert(root, 70);    insert(root, 60);    insert(root, 80);    printf("初始中序遍历: ");    inorder(root);    printf("\n");    root = deleteNode(root, 20); // 删除叶子节点    printf("删除20后: ");    inorder(root);    printf("\n");    root = deleteNode(root, 30); // 删除有两个子节点的节点    printf("删除30后: ");    inorder(root);    printf("\n");    return 0;}

关键点解析

- 在C语言BST删除操作中，处理两个子节点的情况最容易出错。记住：我们不是直接删除该节点，而是用它的中序后继（或前驱）的值覆盖它，再删除那个后继节点。

- findMin 函数用于在右子树中找到最小值，即中序后继。

- 删除后一定要释放内存（free），避免内存泄漏。

总结

通过本教程，你已经掌握了 二叉搜索树节点删除 的完整逻辑和 C 语言实现。这是 C语言数据结构教程 中的核心内容之一。多加练习，你就能熟练运用 BST 进行各种操作了！

如果你觉得这篇文章对你有帮助，欢迎收藏并分享给其他正在学习数据结构的朋友！