/**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;}