二叉搜索树 c语言 删除节点

二叉搜索树的删除操作需要考虑三种情况：

1. 被删除节点是叶子节点，直接删除即可。
2. 被删除节点有一个子节点，将子节点替换为被删除节点。
3. 被删除节点有两个子节点，需要找到右子树中最小的节点或者左子树中最大的节点，将其替换为被删除节点。

以下是一个简单的 C 语言实现：

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

// 二叉搜索树结构体
typedef struct TreeNode {
    int value;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

// 创建一个新节点
TreeNode* createNode(int value) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->value = value;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// 插入一个节点
void insertNode(TreeNode** root, int value) {
    if (*root == NULL) {
        *root = createNode(value);
        return;
    }
    if (value < (*root)->value) {
        insertNode(&((*root)->left), value);
    } else {
        insertNode(&((*root)->right), value);
    }
}

// 寻找右子树中最小的节点
TreeNode* findMinNode(TreeNode* node) {
    while (node->left != NULL) {
        node = node->left;
    }
    return node;
}

// 删除一个节点
void deleteNode(TreeNode** root, int value) {
    if (*root == NULL) {
        return;
    }
    if (value < (*root)->value) {
        deleteNode(&((*root)->left), value);
    } else if (value > (*root)->value) {
        deleteNode(&((*root)->right), value);
    } else {
        if ((*root)->left == NULL) {
            TreeNode* temp = *root;
            *root = (*root)->right;
            free(temp);
        } else if ((*root)->right == NULL) {
            TreeNode* temp = *root;
            *root = (*root)->left;
            free(temp);
        } else {
            TreeNode* temp = findMinNode((*root)->right);
            (*root)->value = temp->value;
            deleteNode(&((*root)->right), temp->value);
        }
    }
}

// 中序遍历
void inorderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    inorderTraversal(root->left);
    printf("%d ", root->value);
    inorderTraversal(root->right);
}

int main() {
    TreeNode* root = NULL;
    insertNode(&root, 5);
    insertNode(&root, 3);
    insertNode(&root, 7);
    insertNode(&root, 2);
    insertNode(&root, 4);
    insertNode(&root, 6);
    insertNode(&root, 8);

    printf("Before deletion: ");
    inorderTraversal(root);
    printf("\n");

    deleteNode(&root, 5);

    printf("After deletion: ");
    inorderTraversal(root);
    printf("\n");

    return 0;
}

这段代码实现了二叉搜索树的删除操作，其中 `createNode` 函数用于创建新节点，`insertNode` 函数用于插入节点，`findMinNode` 函数用于寻找右子树中最小的节点，`deleteNode` 函数用于删除节点，`inorderTraversal` 函数用于中序遍历二叉搜索树。