#include<iostream>using namespace std;//定义二叉搜索树的结点struct Node{    int data;    Node *lc,*rc,*parent;};//中序遍历二叉搜索树void show(Node *now){    if(now==NULL) return;    show(now->lc);    cout<<now->data<<endl;    show(now->rc);}//将值为val的结点插入到二叉搜索树中//?为什么要传指向根结点指针的指针，而不是直接传根结点的指针。因为根结点的指针可能为空，这里需要开辟内存。Node* insert(Node **rt,int val){    Node *now=*rt;//用now指针在树上移动    Node *par=NULL;//记录now指针的父亲    while(now!=NULL)    {        par=now;        if(val<now->data)//如果val小于当前结点的值说明应该插到左子树中            now=now->lc;        else            now=now->rc; //否则插入到右子树中    }    Node *newnode=new Node;//开辟新结点    newnode->data=http://www.mamicode.com/val;    newnode->lc=newnode->rc=NULL;    if(par==NULL)//当这是一棵空树的时候    {        newnode->parent=NULL;        *rt=newnode;//直接通过指针修改根结点    }    else    {        if(val<par->data)            par->lc=newnode;        else            par->rc=newnode;        newnode->parent=par;    }    return newnode;}//在以now为根结点的树上，寻找值为val的结点Node* search(Node *now,int val){    while(now!=NULL&&now->data!=val)    {        if(val<now->data)            now=now->lc;        else            now=now->rc;    }    return now;}//在以now为根结点的树上，寻找最大、最小值Node* maximun(Node *now){    while(now->rc!=NULL)    {        now=now->rc;    }    return now;}Node* minimun(Node *now){    while(now->lc!=NULL)        now=now->lc;    return now;}//寻找now结点的前继、后继//寻找前继：如果now的左子树非空，则返回左子树的最大值结点。否则如果now是父亲的左孩子则不断向上直到now不再是父亲的左孩子，返回父结点。Node* predecessor(Node *now){    if(now->lc!=NULL)        return maximun(now->lc);    Node *par=now->parent;    while(par!=NULL&&now==par->lc)    {        now=par;        par=par->parent;    }    return par;}Node* successor(Node *now){    if(now->rc!=NULL)        return minimun(now->rc);    Node *par=now->parent;    while(par!=NULL&&now==par->rc)    {        now=par;        par=par->parent;    }    return par;}//对于一棵以T为根结点的树，用以v为根结点的子树取代以u为根结点的子树，完成u的父亲与v之间的绑定void transplant(Node **T,Node *u,Node *v){    if(u->parent==NULL)        (*T)=v;    else if(u==u->parent->lc)        u->parent->lc=v;    else if(u==u->parent->rc)        u->parent->rc=v;    if(v!=NULL)        v->parent=u->parent;}//删除给定结点void erase(Node **T,Node *now){    Node *temp=now;    if(now->lc==NULL)    {        transplant(T,now,now->rc);    }    else if(now->rc==NULL)    {        transplant(T,now,now->lc);    }    else    {        Node* nextnode=successor(now);        if(nextnode!=now->rc)        {            transplant(T,nextnode,nextnode->rc);            nextnode->rc=now->rc;            now->rc->parent=nextnode;        }        transplant(T,now,nextnode);        nextnode->lc=now->lc;        now->lc->parent=nextnode;    }    delete temp;}int main(){    Node *root=NULL;    while(1)    {        cout<<"1.插入结点"<<endl;        cout<<"2.删除结点"<<endl;        cout<<"3.中序遍历"<<endl;        cout<<"4.查询"<<endl;        cout<<"5.查询根"<<endl;        int p;        cin>>p;        if(p==1)        {            cout<<"输入待插元素值："<<endl;            int t;            cin>>t;            insert(&root,t);            cout<<"插入成功！"<<endl;        }        else if(p==2)        {            cout<<"输入待删元素值："<<endl;            int t;            cin>>t;            Node *q=search(root,t);            if(q==NULL)cout<<"该值不存在！"<<endl;            else            {                erase(&root,q);                cout<<"删除成功！"<<endl;            }        }        else if(p==3)        {            cout<<"======"<<endl;            show(root);            cout<<"======"<<endl;        }        else if(p==4)        {            cout<<"输入待查询元素值："<<endl;            int t;            cin>>t;            Node *q=search(root,t);            if(q==NULL) cout<<"该值不存在！"<<endl;            else            {                Node *a=predecessor(q),*b=successor(q);                if(a!=NULL)                    cout<<"前继："<<a->data<<endl;                if(b!=NULL)                    cout<<"后继："<<b->data<<endl;            }        }        else if(p==5)        {            if(root==NULL) cout<<"根为空！"<<endl;            else cout<<"根："<<root->data<<endl;        }    }    return 0;}