/**1.实现了递归 非递归插入（创建）二叉排序（搜索）树；
分别对应Insert_BinSNode(TBinSNode* T,int k),NonRecursion_Insert_BinSNode(TBinSNode* T,int k);
  2.实现了递归 非递归查找 二叉排序（搜索）树 ；
分别对应Find_BinSNode(TBinSNode *T,int s),NonRecursion_Find_BinSNode(TBinSNode *T,int s);
  3. 实现了非递归删除 二叉排序（搜索）树；
分别对应Delete_BinSNode()； 
  4. 实现了递归先序、中序、后序遍历二叉排序（搜索）树；
分别对应Pre_Print_BinSNode(TBinSNode T),In_Print_BinSNode(TBinSNode T),Post_Print_BinSNode(TBinSNode T);    
*/
#include
#include
typedef struct BinSTreeNode{
  int num;
  struct BinSTreeNode *lchild,*rchild;
}BinSNode,*TBinSNode;
int Empty_Tree(TBinSNode T){
  if(!T){
    return 1; 
  }else{
    return 0;
  }
}

/*---------------------非递归方法 二叉排序树的删除-----------------*/
void Delete_BinSNode(TBinSNode *T,int del){
  TBinSNode cur,pre,lt,rblast; 
  cur=*T;
  pre=NULL;
  //如果二叉排序树为空 
  if(Empty_Tree(cur)){
    printf("Sorry,Tree is none"); 
    return;
  }
//如果二叉排序树不为空，先找到即将删除的元素del.这里再次实现一遍查找，当然也可以修改一下Find类的函数 
  while(cur && cur->num!=del){
    if(del>cur->num){
      pre=cur; 
      cur=cur->rchild;
    }else{
      pre=cur;
      cur=cur->lchild;
    }
  }
  if(!cur){
    printf("Sorry,you want to delete the node ,which is non-existent");
    return;
  }
  if(cur->num==del){
    printf("find the delete node,wait a minute.......\n");
  }
  //如果找到待删除的结点，立刻判断该结点有无左子树

  //情况一：待删除结点无左子树 
  if(!cur->lchild){
    if(pre==NULL){
      cur=*T;
      *T=(*T)->rchild;
      free(cur);
      return;
    }
    if(pre->lchild && pre->lchild->num==del){
      pre->lchild=cur->rchild;
      free(cur);
      return;
    }
    if(pre->rchild && pre->rchild->num==del){
      pre->rchild=cur->rchild;
      free(cur);
      return;
    }
  } 
  //情况二：待删除的结点有左子树。 
  if(cur->lchild){
    lt=cur->lchild;
    //情况2.1：该左子树无右子树 
    if(!lt->rchild){
      if(pre->lchild && pre->lchild->num==del){
        pre->lchild=lt;
        free(cur);
        return;
      }
      if(pre->rchild && pre->rchild->num==del){
        pre->rchild=lt;
        free(cur);
        return;
      }
    }  
    //情况2.2:该左子树有右子树 
    if(lt->rchild){
      while(lt->rchild){
        rblast=lt; //该左子树中最大的结点的前一个结点. 
        lt=lt->rchild; 
      }
      cur->num=lt->num;
      rblast->rchild=lt->lchild;
      free(lt);
      return;
    }  
  }
} 



/*--------------------递归方法 查找 二叉排序树-------------------*/
void Find_BinSNode(TBinSNode T,int s){
  if(s==T->num){
    printf("%d\n",T->num);
    return;
  }
  if(s>T->num){
    Find_BinSNode(T->rchild,s);
  }else{
    Find_BinSNode(T->lchild,s);
  }
} 
/*-------------------非递归方法 查找二叉排序树--------------------*/
void NonRecursion_Find_BinSNode(TBinSNode T,int s){
  if(Empty_Tree(T)){
    printf("Tree is none");
    return; 
  }
  while(T && s!=T->num ){
    if(s>T->num){
      T=T->rchild;
    }else{
      T=T->lchild;    
    }  
  }
  if(!T){
    printf("Sorry,Not Find!");
    exit(0);
  }
  if(s==T->num){
    printf("%d\n",T->num);
  }

} 
/*-----------------递归方法 创建/插入 二叉排序树------------------*/ 
void Insert_BinSNode(TBinSNode *T,int k){
// int n;
  TBinSNode node;
// scanf("%d",&n);
  if(Empty_Tree(*T)){
    *T=(TBinSNode)malloc(sizeof(BinSNode)); 
    (*T)->num=k;
    (*T)->lchild=(*T)->rchild=NULL;
    return;
  }else{
    if(k>(*T)->num){
      Insert_BinSNode(&(*T)->rchild,k); 
    }else{
      Insert_BinSNode(&(*T)->lchild,k); 
    }
  }  
}
/*----------------------先序遍历二叉排序树----------------------------------*/
void Pre_Print_BinSNode(TBinSNode T){
  if(T){
    printf("%d ",T->num);
    Pre_Print_BinSNode(T->lchild);
    Pre_Print_BinSNode(T->rchild); 
  }
}
/*-----------------------中序遍历二叉排序树-----------------------------------*/
void In_Print_BinSNode(TBinSNode T){
  if(T){
    In_Print_BinSNode(T->lchild);
    printf("%d ",T->num);
    In_Print_BinSNode(T->rchild); 
  }
}

/*-----------------------后序遍历二叉排序树-----------------------------------*/
void Post_Print_BinSNode(TBinSNode T){
  if(T){
    Post_Print_BinSNode(T->lchild);
    Post_Print_BinSNode(T->rchild);
    printf("%d ",T->num); 
  }
}
/*---------------------非递归 创建/插入 二叉排序树---------------------------*/
void NonRecursion_Insert_BinSNode(TBinSNode *T,int k){
  //如果为空的二叉排序树 
  TBinSNode cur,p,t;
  t=*T;
  if(!*T){
    *T=(TBinSNode)malloc(sizeof(BinSNode));
    (*T)->num=k;
    (*T)->lchild=(*T)->rchild=NULL;
    return; 
  }else{     //二叉排序树不为空。
    while(t){
      if(k>t->num){
        cur=t;
        t=t->rchild;
      }else{
        cur=t;
        t=t->lchild;
      } 
    }
     p=(TBinSNode)malloc(sizeof(BinSNode));
     p->num=k;
     p->lchild=p->rchild=NULL;
     if(k>cur->num){
      cur->rchild=p;
     } 
     if(knum){
      cur->lchild=p;
     }
  }
} 
int main(void){
  TBinSNode T=NULL;
  int k,s,del;//创建的 查找的 删除的 
  while(scanf("%d",&k) && k){
//   Insert_BinSNode(&T,k);
    NonRecursion_Insert_BinSNode(&T,k); 
  }
// scanf("%d",&s); 
// Find_BinSNode(T,s);
// NonRecursion_Find_BinSNode(T,s); 
  Pre_Print_BinSNode(T);
  scanf("%d",&del);
  Delete_BinSNode(&T,del);
  Pre_Print_BinSNode(T); 
  return 0;
}