《数据结构课程设计》二叉排序树基本操作实验程序

#include"head.h" int min=-32768; BSTNode * CreatBST(keytype a[],int n)//创建二叉排序树 { BSTNode *p=NULL; int i=0; while(i<n) { InsertBST(p,a[i]); i++; } return p; } void InsertBST(BSTNode *&p,keytype k)//向二叉树插入结点 { if(p==NULL) { p=(BSTNode *)malloc(sizeof(BSTNode)); p->key=k; p->lchild=p->rchild=NULL; } else if(p->key==k) ; else if(p->key<k) InsertBST(p->rchild,k); else InsertBST(p->lchild,k); } void DispBST(BSTNode * b)//输出二叉树 { if(b!=NULL) { printf("%d",b->key ); if(b->lchild!=NULL||b->rchild!=NULL) { printf("("); if(b->lchild!=NULL) DispBST(b->lchild); if(b->rchild!=NULL) { printf(","); DispBST(b->rchild); } printf(")"); } } } int DeleteBST(BSTNode *&p,keytype k) { if(!p) { printf("出现错误！\n"); return 0; } else { if(k==p->key) return Delete(p); else if(k<p->key) return DeleteBST(p->lchild,k); else return DeleteBST(p->rchild ,k); } } int Delete(BSTNode * & p) { BSTNode *q,*r; if(!p->rchild ) { q=p; p=p->lchild; free(q); } else if(!p->lchild ) { q=p; p=p->rchild; free(q); } else Delete1(p,r); return 1; } void Delete1(BSTNode *&p,BSTNode *&r) { BSTNode * q; q=p; r=p->lchild ; while(r->rchild)//找到的右子树的最右下结点 { q=r;//q指向r的双亲结点 r=r->rchild ; } p->key =r->key ; if(q!=p) q->rchild =r->lchild ; else q->lchild =r->lchild ; free(r); } void searchbst1(BSTNode * bt,keytype k,keytype path[],int i)//采用非递归方法查找结点并输出查找路径 { int j; if(bt==NULL) ; else if(k==bt->key ) { path[i+1]=bt->key ; for(j=1;j<=i+1;j++) printf("%3d",path[j]); printf("\n"); } else { path[i+1]=bt->key ; if(k<bt->key ) searchbst1(bt->lchild ,k,path,i+1); else searchbst1(bt->rchild ,k,path,i+1); } } int JudgeBST(BSTNode *bt)//非递归得到中序遍历序列判断是否为二叉排序树 { BSTNode * s [MAXSIZE]; BSTNode * p; int top=-1; p=bt; while(p||top<0) { if(p) { s[++top]=p; p=p->lchild; } else { top--; p=s[top]; if(p->key>min) { min=p->key; } else return 0; p=p->rchild; } } return 1; } void SearchBST2(BSTNode *bt,keytype k)//采用递归方法查找结点并输出查找路径 { if(bt->key ==k) printf("%3d",bt->key ); else if(bt) { printf("%3d",bt->key ); if(k<bt->key ) SearchBST2(bt->lchild,k ); else SearchBST2(bt->rchild,k ); } }