数据结构-二叉查找树

/* copyright by hwdong*/

#include <stdio.h>

#include <stdlib.h>

#include <malloc.h>

typedef int EType;

typedef struct  binode{
    EType data;
    struct  binode *lchild,*rchild;
}BiTNode;

BiTNode *newNode(EType e ){
	BiTNode *p  = (BiTNode *)malloc(sizeof(BiTNode));
	p->data = e;
	p->lchild = p->rchild = 0;
	return p;
}

BiTNode* SearchBST(BiTNode* T, EType e){
   if (!T) return 0; //递归出口

    if (T->data == e) return T;      //处理根

    if (e < T->data)                 //左子树

       return SearchBST(T->lchild, e);  

    else                             //右子树

       return SearchBST(T->rchild, e);
}

BiTNode* InsertBST( BiTNode* T, EType e){
  if(T==0) return newNode(e); 
 
  if (e<T->data)          //左子树

     T->lchild = InsertBST(T->lchild, e);

  else if (e>T->data)     //右子树

     T->rchild = InsertBST(T->rchild, e);

  return T;
}

void Delete( BiTNode* p) ;

BiTNode* DeleteBST( BiTNode* T, EType e){
  if(T==0) return T;
  if (e<T->data)          //左子树

     T->lchild = DeleteBST(T->lchild, e);

  else if (e>T->data)     //右子树

     T->rchild = DeleteBST(T->rchild, e);

  else{ //T就是要删除的结点

    if(T->rchild==0){ //左孩子顶替他

        BiTNode *q = T->lchild;
        free(T);
        return q;
    }
    else  if(T->lchild==0) {
    	BiTNode *q = T->rchild;
        free(T);
        return q;
    }
    else{
    	Delete(T); return T;
    }
  }
}


void Delete( BiTNode* p) { 
   BiTNode* q = p,*s = p->lchild;
   while (s->rchild) {
   	  q = s; s = s->rchild; 
   }
   p->data = s->data;
   if (q != p)
   	 q->rchild=s->lchild;
   else
     q->lchild=s->lchild;
   free(s);
   return;
}


void IOT(BiTNode* T)
{
    if (T!= 0){
        IOT(T->lchild);
        printf("%d ", T->data);
        IOT(T->rchild);
    }
}


int main()
{
    BiTNode* root = NULL;
    root = InsertBST(root, 50);
    root = InsertBST(root, 30);
    root = InsertBST(root, 20);
    root = InsertBST(root, 40);
    root = InsertBST(root, 70);
    root = InsertBST(root, 60);
    root = InsertBST(root, 80);
 
    printf("Inorder traversal of the given tree \n");
    IOT(root);
 
    printf("\nDelete 20\n");
    root = DeleteBST(root, 20);
    printf("Inorder traversal of the modified tree \n");
    IOT(root);
 
    printf("\nDelete 30\n");
    root = DeleteBST(root, 30);
    printf("Inorder traversal of the modified tree \n");
    IOT(root);
 
    printf("\nDelete 50\n");
    root = DeleteBST(root, 50);
    printf("Inorder traversal of the modified tree \n");
    IOT(root);
 
    return 0;
}