C实现二叉排序树
/************************************************************************/ /* C实现二叉排序树 */ /************************************************************************/ #include <stdio.h> #include <stdlib.h> typedef int ElemType; typedef struct BiTNode{ ElemType data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; int SearchBST(BiTree T,ElemType key,BiTree f,BiTree *p){ if(!T) { *p = f;return 0; }else{ if(key == T->data) { *p = T;return 1; }else{ if(key < T->data) { return SearchBST(T->lchild,key,T,p); }else{ return SearchBST(T->rchild,key,T,p);}}}}int InsertBST(BiTree *T,ElemType key){ BiTree p,s;if(!SearchBST(*T,key,NULL,&p)){ s = (BiTree)malloc(sizeof(BiTNode));s->data = key;s->lchild = s->rchild =NULL;if(!p){ *T = s;}else{ if(key < p->data) { p->lchild = s; }else{ p->rchild = s;}}return 1;}else{ return 0;} }void ProOrderTraverse(BiTree T){ if(T==NULL) { return; }else{ printf("%d ",T->data);ProOrderTraverse(T->lchild);ProOrderTraverse(T->rchild);}}int DeleteBST(BiTree *T,ElemType key){ if(!*T) {return 0; }else{ if(key == (*T)->data) {return Delete(T); }else{ if(key < (*T)->data) { return DeleteBST(&(*T)->lchild,key); }else{ return DeleteBST(&(*T)->rchild,key);}}}}int Delete(BiTree *p){ BiTree q,s;if((*p)->rchild == NULL){ q = *p;*p = (*p)->lchild;free(q);}else{ if((*p)->lchild == NULL) {q = *p;*p = (*p)->rchild;free(q); }else{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 1;}int main() { int i;int a[10]={62,88,58,47,35,73,51,99,37,93};BiTree T=NULL;for(i=0;i<10;i++){ InsertBST(&T,a[i]);}ProOrderTraverse(T);printf("\n");InsertBST(&T,95);ProOrderTraverse(T);printf("\n");DeleteBST(&T,51);ProOrderTraverse(T);printf("\n"); return 0; }