//节点结构

 struct Node{

     Node(int k=):key(k){}

     Node* parent = nullptr;

     Node* left = nullptr;

     Node* right = nullptr;

     int key;

 };

 //我把二叉搜索相关的基本方法放到了一个类里

 class MyBST{

 private:

     Node* root=nullptr;

 public:

     MyBST(){};

     MyBST(vector<int> v);

     Node* getRoot(){ return root; }

     void insertNode(int k);

     void deleteNode(int k);

     Node* findByKey(int k);

     Node* findSuccessor(int k);//寻找后继节点

     Node* findPredecessor(int k);//寻找前驱节点

     void traversal(Node* root, void(*f)(int k) = [](int k)->void{cout <<k << " "; });//遍历输出所有节点

     void insertNode(Node* n);

     void deleteNode(Node* n);

     Node* findSuccessor(Node* n);

     Node* findPredecessor(Node* n);

 };

 MyBST::MyBST(vector<int> v):MyBST(){

     for (auto n : v){

         insertNode(n);

     }

 }

 Node* MyBST::findByKey(int k){

     Node* temp = root;//获取根节点

     while (temp != nullptr){

         if (k == temp->key)//当key匹配的时候返回匹配节点

             return temp;

         temp = k < temp->key ? temp->left : temp->right;//通过比较key的值来决定搜索向哪一棵子树进行

     }

     cout << "can't find" << endl;

     return nullptr;

 }

 Node* MyBST::findPredecessor(Node* n){

     if (n->left != nullptr){//若x的左子树不为空，则x前驱是x节点左子树里最靠右的那个节点

         n = n->left;

         while (n->right != nullptr)

             n = n->right;

         return n;

     }

     while (n->parent != nullptr&&n->parent->left == n)//如果x的左子树为空，那么我们就要向上找x的第一个有右孩子且左子树里没有x节点的祖先

         n = n->parent;

     return n->parent;

 }

 Node* MyBST::findPredecessor(int k){

     return findPredecessor(findByKey(k));

 }

 Node* MyBST::findSuccessor(Node* n){

     if (n->right != nullptr){//若x的右子树不为空，则x后继是x节点右子树里最靠左的那个节点

         n = n->right;

         while (n->left != nullptr)

             n = n->left;

         return n;

     }

     while (n->parent != nullptr&&n->parent->right == n)//如果x的左子树为空，那么我们就要向上找x的第一个有右孩子且左子树里没有x节点的祖先

         n = n->parent;

     return n->parent;

 }

 Node* MyBST::findSuccessor(int k){

     return findSuccessor(findByKey(k));

 }

 void MyBST::traversal(Node* root, void(*f)(int k)){

     if (root == nullptr)

         return;

     traversal(root->left);

     f(root->key);

     traversal(root->right);

 }

 void MyBST::insertNode(int k){

     Node* n = new Node(k);

     insertNode(n);

 }

 void MyBST::insertNode(Node* n){

     Node* temp = root;

     if (temp==nullptr){//树为空就设置根节点

         root = n;

         return;

     }

     while (true){//这个循环里有一个大的if-else结构，用来决定插入到左子树还是右子树

         if (temp->key > n->key){

             if (temp->left != nullptr)//里层各有一个if-else结构判断是否已经到达要插入的地方，到达则替换，没有则深入

                 temp = temp->left;

             else{

                 temp->left = n;//因为我们用null代替了NIL节点，所以替换时只需要修改两个指针

                 n->parent = temp;

                 return;

             }

         }

         else{

             if (temp->right != nullptr)

                 temp = temp->right;

             else{

                 temp->right = n;

                 n->parent = temp;

                 return;

             }

         }

     }

 }

 void MyBST::deleteNode(Node* n){

     Node* temp;//用来存取代n节点位置的节点，下面的if分三种情况确定取代n节点位置的节点temp的取值

     if (n->left == nullptr&&n->right == nullptr)//情况一：n没有孩子节点

         temp = nullptr;

     else if (n->left == nullptr || n->right == nullptr){//情况二：n有一个孩子节点

         temp = (n->left == nullptr) ? n->right : n->left;//我们用这个孩子节点当做取代n的节点

         temp->parent = n->parent;//因为temp要取代n，所以要用temp复制n的属性，因为temp就是n的孩子节点之一，且另一个孩子节点是nullptr，所以n的孩子节点的信息不用复制

     }

     else{//情况三：n有两个孩子节点

         temp = findSuccessor(n);//我们用n节点的后继y当做取代n的节点

         Node* successor_right;//y只可能有一个右孩子或者没有孩子，我们先要让y的右孩子取代y，再让y取代n

         if (temp->right == nullptr)//如果y没有孩子，则用nullptr取代y

             successor_right = nullptr;

         else{

             successor_right = temp->right;

             successor_right->parent = temp->parent;//y有右孩子的时候要处理右孩子的父节点

         }

         if (temp->parent->left == temp)//这个if用来让y的父节点指向取代y的节点

             temp->parent->left = successor_right;

         else

             temp->parent->right = successor_right;

         //接下来要让y取代n了，其实我们只需要把y的key值给n就行了,然后直接退出，不需要再修改其他的部分了

         n->key = temp->key;

         delete temp;

         return;

     }

     //情况一和情况二到此为止取代n节点的temp已经确定，而且当temp不是nullptr的时候，temp也已经复制了必要的n的属性，剩下的就是让n的父节点指向temp了

     //注意被删除的节点有可能是根节点，所以当我们发现被删除的是根节点时，不需要让n的父节点指向temp，因为n没有父节点了，但是这个时候必须修改root指针的指向

     if (n->parent != nullptr){

         if (n->parent->left == n)

             n->parent->left = temp;

         else

             n->parent->right = temp;

     }

     else

         root = temp;//修改root指针的指向

     delete n;

 }