用C语言删除二叉排序树指定节点

在C语言中，删除二叉排序树(BST)中的指定节点通常涉及三个步骤：首先找到需要删除的节点，然后处理三种情况：如果该节点无子节点、有一个子节点或有两个子节点。

1. **找到节点**：
使用递归的方式遍历BST，比较当前节点的值与目标值。如果相等，找到了要删除的节点；如果不等于，则继续查找左子树或右子树。

struct TreeNode* search(struct TreeNode* root, int val) {
    if (root == NULL || root->val == val) {
        return root;
    }
    if (val < root->val) {
        return search(root->left, val);
    } else {
        return search(root->right, val);
    }
}

2. **处理删除**：
- 如果节点无子节点，直接删除它并返回NULL；
- 如果有单个子节点，将子节点替换到原节点的位置；
- 如果有两个子节点，需要找到它的后继节点（右子树的最大值），用后继节点的值替换当前节点，然后删除后继节点。

struct TreeNode* deleteNode(struct TreeNode* root, int val) {
    struct TreeNode* node = search(root, val);
    if (node == NULL) return root; // 节点不存在

    // 有子节点的情况
    if (node->left == NULL && node->right == NULL) {
        free(node);  // 节点无子节点，直接释放内存
    } else if (node->left == NULL) {
        struct TreeNode* temp = node->right;
        free(node);
        return temp;
    } else if (node->right == NULL) {
        struct TreeNode* temp = node->left;
        free(node);
        return temp;
    }

    // 后继节点替换
    struct TreeNode* temp = findMin(node->right);
    node->val = temp->val;
    free(temp);  // 删除后继节点
    return root;
}

// 辅助函数：找最小节点
struct TreeNode* findMin(struct TreeNode* node) {
    while (node->left != NULL) {
        node = node->left;
    }
    return node;
}