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

1、精选优质文档-倾情为你奉上桂林电子科技大学 数学与计算科学学院实验报告 实验室：06406 实验日期： 年 月 日院（系）信息与计算科学系学号姓名庞文正成绩课程名称数据结构实验实验项目名 称二叉检索树指导教师赵汝文一 ，实验目的（1） 掌握二叉检索树的定义和特征；（2） 掌握二叉检索树的建立方法；（3） 实现基于二叉检索树的查找技术；（4） 掌握二叉检索树的查找性能；二，实验原理二叉树的构成，可从空的二叉树开始，每输入一个结点数据，就建立一个新结点插入到当前已经生成的二叉检索树中，所以它的主要操作是二叉检索树插入运算。在二叉检索树中插入新结点，只要保证插入后仍符合二叉检索树的定义即可。二叉检索

2、树的检索运算实际上同二叉检索树的创建运算是一致的。 区别在于，创建过程要为二叉检索树中没有位置的关键字建立结点。而查找过程中，只是在二叉检索树中查找是否有等于查找关键字值的结点存在。不管有还是没有，它都不会创建一个新的结点。三，实验设备Xp系统电脑一台，VC+6.0软件！四，实验内容与步骤（过程及结果截图）1、 实验内容对给定的一组无序序列，建立一棵二叉检索树，并对建立的二叉检索树实现查找操作。调试程序并对相应的输出作出分析；修改输入数据，预期输出并验证输出的结果。加深对算法的理解。2、步骤#include<stdio.h>#include<malloc.h>#defi

3、ne MAXSIZE 100#define NULL 0typedef int keytype;typedef int elemtype;typedef struct nodekeytype key; /关键字域 elemtype other; /其他数据域 struct node *lchild,*rchild; bilist; /二叉检索树的节点结构 /*void insert(r,s) /将 *s 节点插入到一颗二叉检索树 *r 中 递归算法 bilist *r,*s;bilist *q,*p;if(*r)=NULL) (*r)=s;else if(s->key<(*r)-&

4、gt;key) insert(&(*r)->lchild),s); else insert(&(*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) return t; if(s->key<p->key) p=p->lchild; else p=p->rchild; if(t=NULL) return s; i

5、f(s->key<f->key) f->lchild=s; else f->rchild=s; return t; bilist *creat(keytype r,int n) /二叉检索树的构造函数算法 int i;bilist *s,*t;t=NULL;for(i=0;i<n;i+)s=(bilist *)malloc(sizeof(bilist);s->key=ri;s->other=NULL;s->lchild=NULL;s->rchild=NULL;/insert(&t,s);t=insert(t,s);return

6、 t; /*int search(bilist *t,keytype k) /二叉检索树算法 递归算法 if(t=NULL) | (t->key=k) return t;else if(t->key<k) return(search(t->rchild,k); else return(search(t->lchild,k); */int search(bilist *t,keytype k) /*二叉检索树检索算法*/ while(t!=NULL) if(t->key=k) return t; if(t->key>k) t=t->lchil

7、d; else t=t->rchild; return NULL; main()keytype AMAXSIZE;int i,data,n=10;bilist *root;for(i=0;i<n;i+)scanf("%d",&Ai);printf("n");root=creat(A,n);printf("please input the search key:");scanf("%d",&data);if(search(root,data)!=NULL) printf("sea

8、rch succed!n"); else printf("search failed!n");2、 预习思考题调试好上述程序后，试着完成以下拓展内容：（1） 把二叉排序树的构造函数的递归算法改写为非递归算法。并在主函数中调用它，调试好程序并分析其运行结果。将insert(&t,s);改为insert(t,s)（2） 把二叉排序树的插入函数的递归算法改写为非递归算法，并在主函数中调用它，调试好程序并分析其运行结果。bilist * insert(t,s) /* 将*s结点插入到一棵二叉检索树*r中*/ bilist *t,*s; bilist *f,*p;

9、p=t; while(p!=NULL) f=p; if(s->key=p->key) return t; if(s->key<p->key) p=p->lchild; else p=p->rchild; if(t=NULL) return s; if(s->key<f->key) f->lchild=s; else f->rchild=s; return t; （3） 把二叉排序树的检索函数的递归算法改写为非递归算法，并在主函数中调用它，调试好程序并分析其运行结果。int search(bilist *t,keytype k) /*二叉检索树检索算法*/ while(t!=NULL) if(t->key=k) return t; if(t->ke