#include<stdio.h>
#include<conio.h>
#include<alloc.h>
#include<string.h>
#include<dos.h>
typedef struct node *nodeptr;
typedef int    infor;
struct     node
{       infor data;
    nodeptr left;
    nodeptr right;
};

void    insert(nodeptr p,nodeptr *T);
void    insert_node(infor e,nodeptr *T);

void    freenode(nodeptr p)
{    free(p);
}

void    init(nodeptr *T)
{       *T=NULL;
}

nodeptr    remove(nodeptr p)
{    nodeptr rp,f;
    if(p==NULL)
    {    printf("Don't have p");
        return(p);
    }
    if(p->right==NULL)    rp=p->left;
    else
    {    if(p->left==NULL)
        rp=p->right;
        else
        {    f=p;
            rp=p->right;
            while(rp->left!=NULL)
            {    f=rp;
                  rp=rp->left;
            }
            if(f!=p)
            {    f->left=rp->right;
                 rp->right=p->right;
                 rp->left=p->left;
            }
            else    rp->left=p->left;
        }
    }
    free(p);
    return(rp);
}

nodeptr    search(nodeptr proot,int x)
{    nodeptr p;
    p=proot;
    if(p!=NULL)
    {    if(x<proot->data)
            p=search(proot->left,x);
        else    if(x>proot->data)
                p=search(proot->right,x);
    }
    return(p);
}

void    prerder(nodeptr proot)
{    if(proot!=NULL)
    {    printf("%3d",proot->data);
        preorder(proot->left);
        preorder(proot->right);
    }
}

void    inorder(nodeptr proot)
{    if(proot!=NULL)
    {
        inorder(proot->left);
        printf("%3d",proot->data);
        inorder(proot->right);
    }
}

void    posorder(nodeptr proot)
{    if(proot!=NULL)
    {
        posorder(proot->left);
        posorder(proot->right);
        printf("%3d",proot->data);
    }
}

void    cleartree(nodeptr proot)
{    if(proot!=NULL)
    {    cleartree(proot->left);
        cleartree(proot->right);
        freenode(proot);
    }
}
void     createtree(nodeptr *T)
{    int e;
    do
    {    printf("Enter your number (-1 to exit):");
          scanf("%d",&e);
          if(e!=-1)    insert_node(e,T);
    }while(e!=-1);
}

void    insert(nodeptr p,nodeptr *T)
{    if(p->data<(*T)->data)
        if((*T)->left)      insert(p,&(*T)->left);
            else    (*T)->left=p;
    else
        if(p->data>(*T)->data)
            if((*T)->right)      insert(p,&(*T)->right);
            else    (*T)->right=p;
}

void    insert_node(infor e,nodeptr *T)
{    nodeptr p;
    p=(nodeptr)malloc(sizeof(struct node));
    p->data=e;
    p->left=NULL;
    p->right=NULL;
    if(*T==NULL)    (*T)=p;
    else        insert(p,T);
}

main()
{    nodeptr T,p;
    int number,select;
    init(&T);
    do
    {   clrscr();
        printf("1-createtree\n");
        printf("2-preorder\n");
        printf("3-inorder\n");
        printf("4-posorder\n");
        printf("5-insert node\n");
        printf("6-search\n");
        printf("7-remove proot node\n");
        printf("8-remove left node\n");
        printf("9-remove right node\n");
        printf("10-remove all node\n");
        printf("11-exit\n");
        printf("ban chon cong viec nao:");scanf("%d",&select);
        switch(select)
        {    case 1: createtree(&T);
                break;
            case 2:
                if(T==NULL)  printf("empty tree");
                else preorder(T);
                getch();
                break;
            case 3:
                if(T==NULL)  printf("empty tree");
                else inorder(T);
                getch();
                break;
            case 4:
                if(T==NULL)  printf("empty tree");
                else posorder(T);
                getch();
                break;
            case 5: createtree(&T);
                break;
            case 6:
                printf("what number do you want to search:");scanf("%d",&number);
                if(search(T,so))
                    printf("had your number");
                else     printf("hadn't your number");
                getch();
                break;
            case 7:
                T=remove(T);
                break;
            case 8:
                printf("content of father node:");scanf("%d",&number);
                p=search(T,number);
                if(p!=NULL)    p->left=remove(p->left);
                else    printf("hadn't father node");
                break;
            case 9:
                printf("content of father node:");scanf("%d",&number);
                p=search(T,number);
                if(p!=NULL)    p->right=remove(p->right);
                else    printf("hadn't father node");
                break;
            case 10:cleartree(T);
                break;
        }
    }while(ch!=11);
    cleartree(T);
    T=NULL;
}