数据结构课本上算法的实现

# include <stdio.h> # define OK 1 # define ERROR 0 # define OVERFLOW -2 # define FALSE 0 # define TRUE 1 typedef int ElemType; typedef int keyType; typedef int Status; typedef int TElemType; typedef struct BiTNode { TElemType data; struct BiTNode *lchild,*rchild; } BiTNode,*BiTree; BiTree T; int M; void main() { int key,e,m,n,q,a,i; BiTree CreateBiTree(BiTree T); void SearchBST(BiTree T,keyType key); BiTree SearchBST2(BiTree T, keyType key, BiTree f, BiTree p) ; Status InsertBST( ElemType e) ; Status DeleteBST(BiTree T, BiTree f, keyType key) ; Status PreOrderTraverse( BiTree T ); Status Delete(BiTree a,BiTree f); printf("shi fou zi dong sheng cheng er cha shu?\nshi(shu ru:0)\nbu shi (shu ru qi ta shu):"); scanf("%d",&q); if (q!=0 ) {printf("gou zao er cha shu\n"); T=CreateBiTree(T); } if(q==0) { printf("please input yuansu ge shu:"); scanf("%d",&a); for(i=1;i<=a;i++) { printf("please input yuansu e:"); scanf("%d",&m); InsertBST( m) ;} } printf("please input cha zhao yuansu:"); scanf("%d",&key); printf("er cha shu cha zha .\n"); SearchBST (T, key) ; printf("please input the chazhao(charu) yuansu e:"); scanf("%d",&m); InsertBST( m) ; printf("the chazhao(charu) hou de jie guo shi :"); PreOrderTraverse( T ) ; printf("\n"); printf("please input the deleat yuansu e:"); scanf("%d",&n); DeleteBST(T,NULL,n); printf("shan chu hou de jie guo shi:"); PreOrderTraverse( T ); printf("\n"); getch(); } BiTree CreateBiTree(BiTree T) { int ch; printf("please input the number:"); scanf("%d",&ch); if (ch==0) T = NULL; else { if (!(T = (BiTNode *)malloc(sizeof(BiTNode)))) exit(OVERFLOW); T->data = ch; T->lchild=CreateBiTree(T->lchild); T->rchild=CreateBiTree(T->rchild); } return T; } void SearchBST (BiTree T, keyType key) { if (!T || key==T->data) if(!T) printf("cha zhao bu cheng gong\n"); else printf("the result is:%d\n",T->data); else if (key<T->data) SearchBST(T->lchild, key); else SearchBST(T->rchild, key); } BiTree SearchBST2(BiTree T, keyType key, BiTree f, BiTree p) { if (!T) { p = f; return p; } else if (key==T->data) { p = T; printf("cha zhao de yuansu shi:%d\n",p->data); } else if (key<T->data) return SearchBST2(T->lchild, key, T, p); else return SearchBST2(T->rchild, key, T, p);} Status InsertBST( ElemType e) { BiTree s,p; p=SearchBST2(T, e, NULL, p); s = (BiTree)malloc(sizeof(BiTNode)); s->data = e; s->lchild = s->rchild = NULL; if (!p) T = s; else if (e<p->data) p->lchild=s; else p->rchild = s; return TRUE; } Status DeleteBST(BiTree T, BiTree f, keyType key) { if (!T) return FALSE; else { if (key==T->data) return Delete(T,f); else if (key<T->data) return DeleteBST(T->lchild,T, key); else return DeleteBST(T->rchild,T, key); } } Status Delete(BiTree a,BiTree f) { BiTree q, s; if(!a->lchild&&!a->rchild) { if(a->data<f->data) f->lchild=NULL; if(a->data>f->data) f->rchild=NULL; free(a);} else if (!a->rchild) { f->lchild=a->lchild; free(a);} else if (!a->lchild) {f->rchild=a->rchild; free(a);} else { q = a; s = a->lchild; while (s->rchild) { q = s; s = s->rchild; } a->data = s->data; if (q != a) q->rchild = s->lchild; else q->lchild = s->lchild; free(s); } return TRUE; } Status PreOrderTraverse( BiTree T ) { void Visit(TElemType e); if (T) { PreOrderTraverse(T->lchild); Visit(T->data); PreOrderTraverse(T->rchild); } else return OK; } void Visit(TElemType e) { printf("%4d",e);}