有没有一道题搞定考研中的二叉排序树呢？

如果有，那就是下面这一道题，要做到自己理解的基础上，自己写出来整个过程，二叉排序树就没大问题了

/*
二叉排序树的每一个操作的时间复杂度是O(h),h为树的高度
在本题中如果不能保证3,4操作一定存在那么加两个哨兵就可以了,一个+∞,一个-∞
*/
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int INF = 1e8;

struct TreeNode
{
    int val;
    TreeNode *left, *right;
    TreeNode(int _val): val(_val), left(NULL), right(NULL) {}
}*root;


/*
递归整个二叉排序树，一直到叶子结点，就可以创建新的结点插入 
*/
void insert(TreeNode* &root,int x)
{
    if(!root)   root = new TreeNode(x);
    else if(x < root->val)  insert(root->left, x);
    else insert(root->right, x);
}

/*
情况分为如下:
1.叶子结点直接删
2.只有右儿子,把右儿子提上来
3.只有左儿子,把左儿子提上来
4.左右都有结点,把中序遍历的前驱的值覆盖上来就行,最后把前驱删除
(也就是找左子树的最大结点,即遍历左儿子的右子树最大结点)
*/
void remove(TreeNode* &root, int x)
{
    if(!root)   return;
    if(x < root->val)   remove(root->left, x);
    else if(x > root->val)  remove(root->right, x);
    else
    {
        if(!root->left && !root->right) root = NULL;
        else if(!root->left)    root = root->right;
        else if(!root->right)   root = root->left;
        else
        {
            auto p = root->left;
            while(p->right) p = p->right;
            root->val = p->val;
            remove(root->left, p->val);
        }
    }
}

int get_pre(TreeNode* root,int x)
{
    //如果根节点是空的,返回负无穷，目的是如果出现空，为了不让返回的值影响答案，要置空
    if(!root)   return -INF;
    if(root->val >= x)  return get_pre(root->left, x);
    return max(root->val, get_pre(root->right, x));
}

int get_suc(TreeNode* root,int x)
{
    //如果根节点是空的,返回负无穷，目的是如果出现空，为了不让返回的值影响答案，要置空
    if(!root)   return INF;
    if(root->val <= x)  return get_suc(root->right, x);
    return min(root->val, get_suc(root->left, x));
}

int main()
{
    int n;
    cin >> n;
    while (n -- )
    {
        int t,x;
        cin >> t >> x;
        if(t == 1)  insert(root, x);
        else if(t == 2) remove(root, x);
        else if(t == 3) cout << get_pre(root, x) << endl;
        else cout << get_suc(root, x) << endl;
    }

    return 0;
}