二叉排序树维护子系统实现实验报告.doc

《二叉排序树维护子系统实现实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、实验三二叉排序树维护子系统实现实验报告姓名：学号：日期：2012.12.8（以下内容用五号字书写，本页空白不够可续页）一、实验程序…………………………………#include#includeintmax;structnode{intdata;structnode*llink;structnode*rlink;};structnode*find(structnode*tree,intx){intf;structnode*p,*q;p=tree;f=0;while((!f

2、)&&(p!=NULL)){if(p->data==x)f=1;elseif(xdata)p=p->llink;elsep=p->rlink;}if(f)q=p;elseq=NULL;return(q);}structnode*find2(structnode*tree,intx){intf;structnode*p,*q,*r;p=tree;f=0;while((!f)&&(p!=NULL)){if(p->data==x)f=1;elseif(xdata){r=p;p=p->llink

3、;}else{r=p;p=p->rlink;}}if((f==1)&&p!=tree)q=r;elseq=NULL;return(q);}structnode*insertree(structnode*tree,intx){structnode*r,*q;if(tree==NULL){r=(structnode*)malloc(sizeof(structnode));r->data=x;r->rlink=NULL;r->llink=NULL;tree=r;}else{r=tree;while(r!=NU

4、LL){q=r;if(xdata)r=r->llink;elser=r->rlink;}r=(structnode*)malloc(sizeof(structnode));r->data=x;r->rlink=NULL;r->llink=NULL;if(xdata)q->llink=r;elseq->rlink=r;}returntree;}structnode*detree(structnode*t,structnode*f,structnode*p){structnode*q,*s;

5、intbool1;bool1=0;if((p->llink==NULL)

6、

7、(p->rlink==NULL)){if(p->llink==NULL){if(p==t)t=p->rlink;else{s=p->rlink;bool1=1;}}else{if(p==t)t=p->llink;else{s=p->llink;bool1=1;}}}else{q=p;s=q->rlink;while(s->llink!=NULL){q=s;s=s->llink;}s->llink=p->llink;if(q!=p

8、){q->llink=s->rlink;s->rlink=p->rlink;}if(p==t)t=s;elsebool1=1;}if(bool1==1){if(p==f->llink){f->llink=s;}else{f->rlink=s;}}free(p);return(t);}voidpreorder(structnode*t){structnode*s[max];inttop;top=-1;do{while(t!=NULL){printf("%4d",t->data);if(t->rlink!=

9、NULL){top++;s[top]=t->rlink;}t=t->llink;}if(top!=-1){t=s[top];top--;}}while((t!=NULL)

10、

11、(top!=-1));printf("");}intmain(){inti,x,o,u;structnode*v,*w,*z;structnode*tree=NULL;printf("Pleaseinputhowmanynumbersdoyouwanttodevelop:");scanf("%d",&max);for(i=1;i

12、<=max;i++){printf("Pleaseinputanumber:");scanf("%d",&x);tree=insertree(tree,x);}preorder(tree);for(i=1;;i++){printf("choosethemodeyouwant:1¡¢find2¡¢insert3¡¢delete");scanf("%d",&o);switch(o){case1:{printf("inputthenumber