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

实验三二叉排序树维护子系统实现实验报告姓名：学号：日期：2012.12.8（以下内容用五号字书写，本页空白不够可续页） 一、实验程序…………………#include<stdio.h>#include<stdlib.h>intmax;structnode{ intdata; structnode*llink; structnode*rlink;};structnode*find(structnode*tree,intx){intf;structnode*p,*q;p=tree;f=0;while((!f)&&(p!=NULL)){if(p->data==x)f=1;elseif(x<p->data)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(x<p->data){r=p;p=p->llink;}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!=NULL) { q=r; if(x<r->data) r=r->llink; else r=r->rlink; } r=(structnode*)malloc(sizeof(structnode)); r->data=x; r->rlink=NULL; r->llink=NULL; if(x<q->data) q->llink=r; else q->rlink=r; } returntree;}structnode*detree(structnode*t,structnode*f,structnode*p){structnode*q,*s;intbool1;bool1=0;if((p->llink==NULL)||(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){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!=NULL) { top++; s[top]=t->rlink; } t=t->llink; } if(top!=-1) { t=s[top]; top--; } } while((t!=NULL)||(top!=-1)); printf("\n");}intmain(){ inti,x,o,u; structnode*v,*w,*z; structnode*tree=NULL; printf("Pleaseinputhowmanynumbersdoyouwanttodevelop:"); scanf("%d",&max); for(i=1;i<=max;i++) { printf("Pleaseinputanumber:"); scanf("%d",&x); tree=insertree(tree,x); } preorder(tree); for(i=1;;i++) { printf("choosethemodeyouwant:1¡¢find2¡¢insert3¡¢delete\n"); scanf("%d",&o); switch(o) { case1: { printf("inputthenumberyouwant\n"); scanf("%d",&u); v=find(tree,u); if(v==NULL) { printf("notfound\n");}else{printf("thenumberhasbeenfound\n");}continue;}case2:{printf("inputthenumberyouwanttoinsert\n");scanf("%d",&u);insertree(tree,u);preorder(tree);continue;}case3:{printf("inputthenumberyouwanttodelete");scanf("%d",&u);w=find(tree,u);z=find2(tree,u);tree=detree(tree,z,w);preorder(tree);continue;}default:break;} } return0;}二、实验过程实验中，首先建立一个二叉排序表，然后对此表进行查找、插入和删除等操作。建立完二叉排序表后，提示选择功能，包括查找、插入和删除。查找：插入：删除：三、实验分析实验的目的主要有三个：查找：首先将被查找的值与根结点的值进行比较，如果被查找的值大于根结点的值，则查找根结点的右子树，否则查找根结点的左子树，直到找到给定值的结点。插入：(1)在二叉排序树中插入结点例子如图3.3，在二叉排序树中插入值为243和614两个结点。插人的结点一定为二叉排序树的叶结点。删除：在二叉排序树中删除结点是指删除指定的结点，而不是把以这个结点为根的子树都删掉，删除结点后还要保持二叉树的性