#include <iostream>
using namespace std;

////////////////////// 树节点的表示形式：
typedef struct BTree
{
    int data;
    struct BTree *lchild, *rchild;
}btree,*tree;
enum{ unsucess, sucess };

typedef int status;
//////向二叉树插入一个节点的操作。
void insert(tree &a,int k);

/////创建一个二叉排序树；
void create(tree &a);

/////////////////
//////在二叉排序树里删除一个节点
void deleteT(tree a,int x);

/////删除节点的操作
void deleteR(tree a);

///////显示二叉排序树（以中序排序方式输出）
void display(tree a);

////在二叉排序树中寻找一个满足条件的节点
status search(tree a, int x);
/////

///////在完成插入操作 时，首先要在二叉排序树中找到是否存在该节点，下面的的操作就是完成此功能。
status search_1(tree t, int x,tree f,tree &p);//t is tree, p is last visted  node,f is t parents and is null at begin,;

////////该插入新节点的操作是在上面search_1()后的操作。
status insert_1(tree t,int x);//

/////////////////////////////////
////////         创建二叉排序树下面的代码没问题，但如果删除二叉排序树的叶子节点后，display()改二叉排序树，确得不到预期结果。
///////         如果要删除非叶子节点时，display()可以实现，所以请大家帮忙找下问题的原因。

/////////////////////////////////////
int main()
{
    tree a=NULL;
    create(a);
    //////////
    display(a);
//     cout <<"enter you want to search number: ";
//     int y;
//     cin >>y;
//     cout <<search(a,y)<<endl;
    /////
    cout <<"enter the num you want to delete: ";
    int x;
    cin >>x;
    deleteT(a, x);
    cout <<"output the last nums : "<<endl;
    display(a);
    cout <<" enter you want insert num: ";
    int z;
    cin >>z;
    insert_1(a,z);
    cout <<"output the new num: " <<endl;
    display(a);
    cout <<endl;
    return 0;
}

//////////////////////////////////
status search(tree a, int x)
{
//    findtag tag;
    if(a==NULL)
    { //tag=unsucess;
        return unsucess;
    }
    if(a->data ==x)
    {
        //tag = success;
        return sucess;
    }
    else if(a->data <x)
    {
        search(a->rchild ,x);
    }
    else
        search(a->lchild ,x);
}
//////////////////////////////////
void create(tree &a)
{
    cout <<"enter the numbers you want to input: ";
    int n;
    
    cin >>n;
    cout <<"enter the data: ";
    a=NULL;
    int key;

    for(int  i =0; i<n; i++)
    {
        cin >>key;
        insert(a,key);
        //cin >>key;
    }

}
/////////////////////////////////
void insert(tree &a,int k)
{
    tree b =new btree;
    b->data = k;
    b->lchild =b->rchild =NULL;
    if( a==NULL)
        a=b;
    else if(a->data ==k)
        return ;
    else if(k <a->data)
        insert(a->lchild ,k);
    else insert(a->rchild ,k);

    
}

///////////////////////////
void display(tree a)
{
    if(a==NULL)
        return ;
    if(a->lchild)
    {
        display(a->lchild);
    }
    cout <<a->data <<"\t";
    if(a->rchild)
        display(a->rchild);
}
////////////////////////////
void deleteT(tree a,int x)
{
    if(a==NULL)
        return ;
    if(a->data ==x)
    {
        if( !a->lchild && !a->rchild )
        {
            tree q= a;
            delete q;
        }
        else deleteR(a);
    }
    else if(a->data< x)
        deleteT(a->rchild ,x);
    else
        deleteT(a->lchild, x);

}
//////////////////////////
void deleteR(tree a)
{
    tree q=NULL;
    if(a==NULL)
        return ;
//     if( !a->lchild && !a->rchild )
//     {
//         q= a;
//         delete q;
//     }
   else    if( !a->rchild )
    {
        q=a;
        a=a->lchild;
        delete q;
    }
    else if( !a->lchild )
    {
        q =a;
        a=a->rchild;
        delete q;
        q=NULL;
    }
    else
    {
        q=a;
        tree s= a->lchild;
        while(s->rchild)
        {
            q=s;
            s=s->rchild;
        }
        a->data= s->data;
        if(q !=a)
        {
            q->rchild =s->lchild;
        }
        else
            q->lchild =s->lchild;
    }
}
status search_1(tree t, int x,tree f,tree &p)
{
    if(!t)  // empty tree;
    {
        p=f; return false;
    }
    else if( t->data ==x)
    {
        p=t;
        return true;
    }
    else if(t->data <x)
    {
        search_1(t->rchild,x ,t, p);
    }
    else
        search_1(t->lchild ,x ,t, p);

}
///
status insert_1(tree t,int x)
{
 tree q=NULL;
  if( !search_1(t,x,NULL,q) )
  {
        tree s =new btree;
        s->data =x;
        s->lchild =s->rchild =NULL;

        if(!q)
            t =s;
        else if( q->data <x)
            q->rchild =s;
        else
            q->lchild =s;

        return true ;
            
  }
  else false;

}