数据结构实验-二叉检索树

桂林电子科技大学数学与计算科学学院实验报告实验室：06406实验日期：年月日院（系）信息与计算科学系学号1300710226姓名庞文正成绩课程名称数据结构实验实验项目名称二叉检索树指导教师赵汝文一，实验目的（1）掌握二叉检索树的定义和特征；（2）掌握二叉检索树的建立方法；（3）实现基于二叉检索树的查找技术；（4）掌握二叉检索树的查找性能；二，实验原理二叉树的构成，可从空的二叉树开始，每输入一个结点数据，就建立一个新结点插入到当前已经生成的二叉检索树中，所以它的主要操作是二叉检索树插入运算。在二叉检索树中插入新结点，只要保证插入后仍符合二叉检索树的定义即可。二叉检索树的检索运算实际上同二叉检索树的创建运算是一致的。区别在于，创建过程要为二叉检索树中没有位置的关键字建立结点。而查找过程中，只是在二叉检索树中查找是否有等于查找关键字值的结点存在。不管有还是没有，它都不会创建一个新的结点。三，实验设备Xp系统电脑一台，VC++6.0软件！四，实验内容与步骤（过程及结果截图）1、实验内容对给定的一组无序序列，建立一棵二叉检索树，并对建立的二叉检索树实现查找操作。调试程序并对相应的输出作出分析；修改输入数据，预期输出并验证输出的结果。加深对算法的理解。2、步骤#includestdio.h#includemalloc.h#defineMAXSIZE100#defineNULL0typedefintkeytype;typedefintelemtype;typedefstructnode{keytypekey;//关键字域elemtypeother;//其他数据域structnode*lchild,*rchild;}bilist;//二叉检索树的节点结构/*voidinsert(r,s)//将*s节点插入到一颗二叉检索树*r中递归算法bilist**r,*s;{bilist*q,*p;if((*r)==NULL)(*r)=s;elseif(s-key(*r)-key)insert(&((*r)-lchild),s);elseinsert(&((*r)-rchild),s);}*/bilist*insert(t,s)/*将*s结点插入到一棵二叉检索树*r中*/bilist*t,*s;{bilist*f,*p;p=t;while(p!=NULL){f=p;if(s-key==p-key)returnt;if(s-keyp-key)p=p-lchild;elsep=p-rchild;}if(t==NULL)returns;if(s-keyf-key)f-lchild=s;elsef-rchild=s;returnt;}bilist*creat(keytyper[],intn)//二叉检索树的构造函数算法{inti;bilist*s,*t;t=NULL;for(i=0;in;i++){s=(bilist*)malloc(sizeof(bilist));s-key=r[i];s-other=NULL;s-lchild=NULL;s-rchild=NULL;//insert(&t,s);t=insert(t,s);}returnt;}/*intsearch(bilist*t,keytypek)//二叉检索树算法递归算法{if((t==NULL)||(t-key==k))returnt;elseif(t-keyk)return(search(t-rchild,k));elsereturn(search(t-lchild,k));}*/intsearch(bilist*t,keytypek)/*二叉检索树检索算法*/{while(t!=NULL){if(t-key==k)returnt;if(t-keyk)t=t-lchild;elset=t-rchild;}returnNULL;}main(){keytypeA[MAXSIZE];inti,data,n=10;bilist*root;for(i=0;in;i++){scanf(%d,&A[i]);}printf(\n);root=creat(A,n);printf(pleaseinputthesearchkey:);scanf(%d,&data);if(search(root,data)!=NULL)printf(searchsucced!\n);elseprintf(searchfailed!\n);}2、预习思考题调试好上述程序后，试着完成以下拓展内容：（1）把二叉排序树的构造函数的递归算法改写为非递归算法。并在主函数中调用它，调试好程序并分析其运行结果。将insert(&t,s);改为insert(t,s)（2）把二叉排序树的插入函数的递归算法改写为非递归算法，并在主函数中调用它，调试好程序并分析其运行结果。bilist*insert(t,s)/*将*s结点插入到一棵二叉检索树*r中*/bilist*t,*s;{bilist*f,*p;p=t;while(p!=NULL){f=p;if(s-key==p-key)returnt;if(s-keyp-key)p=p-lchild;elsep=p-rchild;}if(t==NULL)returns;if(s-keyf-key)f-lchild=s;elsef-rchild=s;returnt;}（3）把二叉排序树的检索函数的递归算法改写为非递归算法，并在主函数中调用它，调试好程序并分析其运行结果。intsearch(bilist*t,keytypek)/*二叉检索树检索算法*/{while(t!=NULL){if(t-key==k)returnt;if(t-keyk)t=t-lchild;elset=t-rchild;}returnNULL;}3、分析讨论题：试分析二叉检索树递归算法和非递归算法的时间复杂度。二者时间复杂度是一样的！五，实验结果分析或总结此次实验有些困难，基本不动在么改！想了很久！