用C语言实现二叉排序树的删除

以下是用C语言实现二叉排序树的删除的代码：

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

struct TreeNode {
    int data;
    struct TreeNode *left;
    struct TreeNode *right;
};

struct TreeNode* createNode(int data) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

struct TreeNode* insert(struct TreeNode* root, int data) {
    if (root == NULL) {
        return createNode(data);
    }
    if (data < root->data) {
        root->left = insert(root->left, data);
    } else if (data > root->data) {
        root->right = insert(root->right, data);
    }
    return root;
}

struct TreeNode* findMin(struct TreeNode* root) {
    while (root->left != NULL) {
        root = root->left;
    }
    return root;
}

struct TreeNode* deleteNode(struct TreeNode* root, int data) {
    if (root == NULL) {
        return NULL;
    }
    if (data < root->data) {
        root->left = deleteNode(root->left, data);
    } else if (data > root->data) {
        root->right = deleteNode(root->right, data);
    } else {
        if (root->left == NULL) {
            struct TreeNode* temp = root->right;
            free(root);
            return temp;
        } else if (root->right == NULL) {
            struct TreeNode* temp = root->left;
            free(root);
            return temp;
        }
        struct TreeNode* temp = findMin(root->right);
        root->data = temp->data;
        root->right = deleteNode(root->right, temp->data);
    }
    return root;
}

void inorderTraversal(struct TreeNode* root) {
    if (root == NULL) {
        return;
    }
    inorderTraversal(root->left);
    printf("%d ", root->data);
    inorderTraversal(root->right);
}

int main() {
    struct TreeNode* 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 traversal before deleting node 20:\n");
    inorderTraversal(root);
    printf("\n");
    root = deleteNode(root, 20);
    printf("Inorder traversal after deleting node 20:\n");
    inorderTraversal(root);
    printf("\n");
    return 0;
}

上述代码实现了二叉排序树的删除操作，包括以下函数：

- `createNode(int data)`：创建一个新节点。
- `insert(struct TreeNode* root, int data)`：插入一个节点到二叉排序树中。
- `findMin(struct TreeNode* root)`：寻找二叉排序树中最小的节点。
- `deleteNode(struct TreeNode* root, int data)`：删除节点操作。
- `inorderTraversal(struct TreeNode* root)`：中序遍历二叉排序树。

在`main()`函数中，我们创建一个二叉排序树，并在其中插入一些节点。然后，我们删除其中一个节点并输出中序遍历结果，以验证删除操作是否正确。