用c++写一个二叉排序树删除

以下是用C++实现二叉排序树的删除操作的示例代码：

#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
};

TreeNode* insert(TreeNode* root, int val) {
    if (!root) {
        root = new TreeNode(val);
        return root;
    }
    if (val < root->val) {
        root->left = insert(root->left, val);
    } else if (val > root->val) {
        root->right = insert(root->right, val);
    }
    return root;
}

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

TreeNode* remove(TreeNode* root, int val) {
    if (!root) {
        return nullptr;
    }
    if (val < root->val) {
        root->left = remove(root->left, val);
    } else if (val > root->val) {
        root->right = remove(root->right, val);
    } else {
        if (!root->left) {
            TreeNode* temp = root->right;
            delete root;
            return temp;
        } else if (!root->right) {
            TreeNode* temp = root->left;
            delete root;
            return temp;
        } else {
            TreeNode* minNode = findMin(root->right);
            root->val = minNode->val;
            root->right = remove(root->right, minNode->val);
        }
    }
    return root;
}

void inorderTraversal(TreeNode* root) {
    if (!root) {
        return;
    }
    inorderTraversal(root->left);
    cout << root->val << " ";
    inorderTraversal(root->right);
}

int main() {
    TreeNode* root = nullptr;
    root = insert(root, 5);
    root = insert(root, 3);
    root = insert(root, 7);
    root = insert(root, 1);
    root = insert(root, 9);
    root = insert(root, 4);
    root = insert(root, 6);

    cout << "Inorder traversal before deletion: ";
    inorderTraversal(root);
    cout << endl;

    root = remove(root, 3);

    cout << "Inorder traversal after deletion: ";
    inorderTraversal(root);
    cout << endl;

    return 0;
}

该程序首先定义了一个TreeNode结构体，包含节点值、左右子节点指针。接着定义了insert函数，用于向二叉排序树中插入节点。findMin函数用于查找树中最小节点。最核心的是remove函数，它实现了二叉排序树的删除操作。在该函数中，首先判断要删除的节点是否存在，如果存在，就判断它的左右子节点情况，如果有一个为空，那么就直接将它的另一个子节点接到它的父节点上，如果两个都不为空，那么就找到它右子树中的最小节点，将它的值赋给要删除的节点，然后再递归删除右子树中的最小节点。最后，定义了inorderTraversal函数，用于中序遍历二叉排序树，以便验证删除操作的正确性。在main函数中，先插入一些节点，然后进行删除操作，并输出中序遍历结果。