#include <stdio.h> /*输入六个整数45、24、53、12、37、9,插入数据元素13,删除数据元素24和53  */
#include <stdlib.h>
typedef struct BiTNode/*结点结构 */
{
  int data;
  struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;                              为什么这样定义，下面好像没用到。指针跟没指针有什么区别？
BiTree Insert(BiTree T,int e)/*插入操作*/
{
    BiTree p=T, f=NULL, s;
    s=(BiTree)malloc(sizeof(BiTNode));         为什么这样分配存储空间，BiTree,BiTNode各代表什么？
    s->data=e;  
    s->lchild=s->rchild=NULL;
    if (T==NULL) /*插入 s 为新的根结点*/
    {  
    T = s;  
    }
    else
    {/*查找插入位置*/
            while(p && p->data!=e) /*如果当前节点不为空且节点的值不是插入的值 */              
            {
              if (p->data>e)
                 {f=p; p=p->lchild;} /*如果当前节点值大于插入的值，则记录当前节点，并将节点的左节点作为当前节点 */
              else
                 {f=p; p=p->rchild;} /*否则，节点的右节点作为当前节点 */
            }
            if (p==NULL&&e <f->data) /*如果当前节点为空并且插入的值小于父节点中的值； */
            f->lchild = s;      /*插入 s 为 f 的左孩子 */
            else if(p==NULL&&e>f->data) f->rchild = s;    /* 插入 s 为 f 的右孩子*/
            else {printf("insert wrong!");exit(0);}
    }
    return  T;                           为什么要return T,T又不是头节点。T好像是根节点？
}
void Delete(BiTree T,int x)
{
  BiTree f=NULL,p=T,q,s;

      while(p&&p->data!=x)
      {
        if(p->data>x)/*如果节点的数值大于x,则记录当前节点，查找其左节点 */
            {f=p;p=p->lchild;}
        else  
            {f=p;p=p->rchild;}
      }
     if(p==NULL)
        {printf("search fail！");exit(0);}
      if(p->lchild==NULL)/*当前节点左孩子为空，重接右结点或左右均为空 */
      {
          if(f->lchild==p)  /*当前节点为左孩子（f->data>p->data）  */
              f->lchild=p->rchild;
          else
              f->rchild=p->rchild;
          free(p);
      }
      else if(p->rchild==NULL)/*右为空，重接左结点  */
      {
          if(f->lchild==p)
              f->lchild=p->lchild;
         else  
             f->rchild=p->lchild;
          free(p);
      }
      else/*左右都不为空 */
      {
          q=p;
          s=p->lchild;
          while(s->rchild!=NULL)
          {
            q=s;
            s=s->rchild;
          }
         p->data=s->data;
          if(q==p)   
              p->lchild=s->lchild;
          else  
              q->rchild=s->lchild; /*到这里删除工作已经结束，要删除的p->data,已经被s->data代替；但是p仍然指向二叉树中
          //的节点，因此如果释放，则会导致由p派生出来的子节点的地址信息全部散失在内存中，无从查找；
         // free(p);      */
      }
}
void Inorder(BiTree T)
{  /* 中序遍历二叉树   */
  if (T)
  {
      Inorder(T->lchild); /* 遍历左子树  */
      printf("%d ",T->data);        /*访问结点 */
      Inorder(T->rchild);/* 遍历右子树 */
  }
}                                                         
void Menu(BiTree T)
{
  int i,e;

  printf("1.input\n");
  printf("2.delete\n");
  printf("3.end\n");
  printf("choice：\n");

  scanf("%d",&i);
  switch(i)
  {
      case  1:
          printf("input element：");
          scanf("%d",&e);
          T=Insert(T,e);
          printf("inorder：\n");
          Inorder(T);
          printf("\n");
        break;
      case  2:
          printf("delete element：");
          scanf("%d",&e);
          Delete(T,e);
          printf("inorder：\n");
          Inorder(T);
          printf("\n");
        break;
        default:   
            exit(0);  
        break;
  }
  Menu(T);
}
void main()
{
  int e,i;
  BiTree T;

  T=NULL;
  printf("input 6 num:\n");
  for(i=1;i <7;i++)
  {
  scanf("%d",&e);
  T=Insert(T,e);
  }
  printf("inorder：\n");
  Inorder(T);
  printf("\n");

  Menu(T);
  getch();
}