/**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<stdio.h>
#include<stdlib.h>
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(k<cur->num){
      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;
}