#include<stdio.h>
#include<conio.h>
#include<malloc.h>
#define MAX 100
#define ENDFLAG -1   /* ENDFLAG为输入数据的结束标志*/
char yes_no='\n',k='\0';
typedef  int KeyType;
typedef  struct{
KeyType  key;   /*关键码*/
           /*其他数据项*/
 }RecNode;

typedef struct node{
     RecNode elem ;
     struct node *lchild,*rchild ;
}BitNode, *BinTree;


void  inorder (BinTree t ) /*中序遍历*/
  { 
    if  (t!=NULL) 
    {
        inorder(t->lchild); 
        printf("%4d", t->elem.key); 
        inorder(t->rchild); 
    }  
}



/*查找算法*/
 BitNode *Search_BinTree(BinTree  bt , KeyType kx)
{/*在二叉排序树bt上查找关键码为kx的元素，若找到，返回指向该元素的指针，否则，返回空指针*/
if (bt == NULL) return NULL;       /*查找失败*/
if(bt->elem.key == kx)  return bt;    /*查找成功*/
if(bt->elem.key > kx)  return Search_BinTree(bt->lchild, kx);   /*在左子树查找*/
else return Search_BinTree(bt->rchild, kx);                  /*在右子树查找*/
}


/*４．插入算法*/
BinTree  Insert_BinTree(BinTree  bt , KeyType kx)
{    /*在二叉排序树bt上插入关键码为kx的元素，返回指向根结点指针*/
if (bt == NULL)                    /*如果是空树，则插入后成为根结点*/
{  bt = (BitNode *)malloc(sizeof(BitNode)) ;
bt->elem.key = kx ;
bt->lchild=NULL;
bt->rchild=NULL;
return bt;
}       
if(bt->elem.key > kx)  bt->lchild=Insert_BinTree(bt->lchild, kx);   /*插入到左子树*/
else  bt->rchild=Insert_BinTree(bt->rchild, kx);                  /*插入到右子树*/
return bt;
}


/*5.创建二叉排序树算法*/

BinTree  Creat_BinTree( )
{    /*从空树开始构造二叉排序树，返回指向根结点指针*/
 BinTree bt=NULL;
 KeyType kx;
 printf("请输入各结点，以间隔隔开(-1结束):");
 scanf("%d",&kx) ;
 while(kx != ENDFLAG)
{  bt=Insert_BinTree(bt, kx);   
     scanf("%d",&kx);
}
return bt ;
}



int delete(BinTree root,KeyType kx)
{
    BinTree p,s,q;
    p=Search_BinTree(root,kx);
    if(p==NULL)
        return 1;
    if(!p->rchild)
    {
        q=p;
        p=p->lchild;
        free(q);
    }
    else if(!p->lchild)
    {
        q=p;
        p=p->rchild;
        free(q);
    }
    else
    {
        q=p;
        s=p->rchild;
        while(s->lchild)
        {
            q=s;
            s=s->lchild;
        }
        p->elem=s->elem;
        if(q!=p)
            q->lchild=s->rchild;
        else
            q->lchild=s->lchild;
        free(s);
    }
    return 0;
}



main()
{
    int k,val;
    BinTree bt;
    bt=Creat_BinTree( );
    printf("建立二叉树成功，并已中序遍历输出如下:");
    inorder(bt);
    printf("\n");
    do
    {
    printf(" 1-------------------查找\n");
    printf(" 2-------------------插入\n");
    printf(" 3-------------------删除\n");
    printf(" 0-------------------退出\n");
    printf("请选择(1-3):");
    scanf("%d",&k);
    switch(k)
    {
      case 1:
           printf("选择了查找\n");
           printf("请输入要查找的数值:");
           scanf("%d",&val);
           if(Search_BinTree(bt,val)!=NULL)
              printf("找到了");
           else 
           printf("没有找到哦!\n");
           break;
     case 2:
            printf("选择了插入!\n");
            printf("请输入要插入的值:");
            scanf("%d",&val);
            if(Insert_BinTree(bt,val)!=0)
            {
              printf("插入成功!\n");
              printf("新二叉树的中序遍历结果如下:\n");
              inorder(bt);
              printf("\n");
            }
            else
                printf("插入失败，值为%d的结点以存在!\n",val);
            break;
     case 3:
           printf("选择了删除!\n");
           printf("请输入要删除的值!\n");
           scanf("%d",&val);
           if(delete(bt,val)!=1)
           {
            printf("删除成功!\n");
            printf("对二叉树进行中序遍历结果如下:\n");
            inorder(bt);
            printf("\n");
           }
           else 
           printf("删除失败，值为%d的结点不能存在!\n",val);
           break;
     case 0: break;
     default:printf("         %c为非法选择!\n",k);
    }
    if(k=='0') break;
    printf("\n------------要继续选择吗(Y/N)? \n");
    do
    {
        yes_no=getch();
    }while(yes_no!='Y' && yes_no!='y'&& yes_no!='N' && yes_no!='n');
}while(yes_no=='Y'||yes_no=='y');
    
}