《数据结构 创建二叉排序树与查找》由会员分享，可在线阅读，更多相关《数据结构 创建二叉排序树与查找（9页珍藏版）》请在金锄头文库上搜索。
1、数据结构实验报告实验题目:创建二叉排序树与查找实验目的：1、掌握使用 Visual C+6.0 上机调试程序的基本方法；2、掌握二叉排序树的创建和二叉排序树查找的方法。3、提高自己分析问题和解决问题的能力，在实践中理解教材上的理论。实验内容：建立至少 10 个顶点的二叉排序树，然后对其进行中序遍历，接着进行查找，判断待查找数据是否存在。一、需求分析1、输入的形式和输入值的范围：根据提示，首先输入顶点中的数据，在进行查找操作时，输入待查找的数据，接着选择下一步要进行的操作(A. 新二叉排序树;B.继续查找;C.结束操作)。2、输出的形式：输出二叉排序的中序遍历结果，在输入待查找的数据后，输出查找
2、的结果。3、程序所能达到的功能：输入顶点数据后，创建二叉排序树，接着进行中序遍历，再输入待查找数据进行查找操作。4、测试数据：请输入顶点数据:53 25 76 20 48 14 60 84 33 78中序遍历结果为:14 20 25 33 48 53 60 76 78 84输入待查找数据:33待查找数据存在选择操作(A.新二叉排序树;B.继续查找;C.结束操作):B输入待查找数据:54待查找数据不存在选择操作(A.新二叉排序树;B.继续查找;C.结束操作):C谢谢使用!Press any key to continue二 概要设计1、二叉排序树又称二叉查找树，对一个二叉树若规定：任一结点如果有
3、左子树，其左子树各结点的数据必须小于该结点的数据；任一结点如果有右子树，其右子树各结点的数据必须大于该结点的数据。按这样规定构成的二叉树称为二叉排序树。对二叉排序树进行中序遍历所得到的结点序列是一个有序序列。2、创建二叉排序树的非递归算法执行的步骤如下：生成一个新结点；与根结点进行比较，如果小于根结点，沿左链域比较，如果大于根结点，沿右链域比较；直至到终端，插入该结点。以序列 53，25，76，20，48，14，60，84，33 ，78 为例，所创建的二叉排序树如图所示。3、二叉排序树查找二叉排序树查找的基本思路：查找过程从根结点开始，首先将它的关键字与给定值 k进行比较， ，如果相等，则查找
4、成功，输出有关的信息；如果不等，若根结点关键字大于给定值 k，向左子树继续查找，否则向右子树继续查找。向子树查找又是树状查找，先以子树的根结点数据与 k 进行比较，如果不相等又转向它的左子树或右子树继续查找。4、本程序的基本操作和模块：建立二叉排序树的函数：Create(BiTNode *B)二叉树的中序遍历函数：Inorder(BiTNode *B,SeqStack &K)查找函数：Search(BiTNode *B,int key)主函数：main( )函数的调用关系如下图所示:三 详细设计（1）元素类型、结点类型1、二叉树结点的类型描述typedef struct nodechar da
5、ta; /data 用于存储二叉树中的字母struct node *lchild; /lchild 为指向该结点左孩子的指针struct node *rchild; /rchild 为指向该结点下一层的指针BiTNode;2、顺序栈的类型描述typedef structBiTNode *pin40; /指针数组，用于存储广义表结点指针int top; /栈顶指针SeqStack;（2）每个模块的分析1、主程序模块main()定义根结点指针定义栈并初始化栈申请根结点空间，令根结点 B 的 lchild 域和 rchild 域为空 调用创建二叉排序树函数调用中序遍历二叉树函数调用查找函数进行查找2
6、、建立二叉排序树的函数void Create(BiTNode *B)定义指向当前结点的指针 p，新结点的指针 q，初始时 p 为空输入不是回车时执行以下操作输入结点数据若该数据是第一个数据第一个数据存到根节点，p 指针指向根结点若该数据不是第一个数据申请新结点 q，将该数据存入 q 的 data 域令新结点 q 的 lchild 域和 rchild 域为空p 指向根结点当 p 指针所指结点和 q 指针所指结点中的数据不同时执行以下操作如果 p 结点数据小于新结点 q 中的数据,执行以下操作如果 p 的右孩子为空，令 p 的右孩子为 q将 p 的右孩子赋 p如果 p 结点数据大于新结点 q 中的
7、数据,执行以下操作如果 p 的左孩子为空，令 p 的左孩子为 q将 p 的左孩子赋 p3、查找函数void Search(BiTNode *B,int key)定义指向当前结点的指针 p，初始时 p 指向根结点当 p 不为空且 p 所指结点的数据不为待查找数据时，执行以下操作如果当前结点中的数据小于待查找数据，则令 p 指向它的右孩子如果当前结点中的数据大于待查找数据，则令 p 指向它的左孩子循环结束后，若 p 为空则待查找数据不存在;否则待查找数据存在4、中序遍历二叉树树的函数void Display(GLNode *G,SeqStack &K)定义表示当前结点的指针 p，并令 p 指根结点
8、。当栈不为空或当前结点指针 p 不为空时，执行以下操作while(K.top!=-1|p!=NULL)a.如果当前结点指针 p 为空，执行以下操作：出栈，栈顶元素所指的结点作为当前结点 p输出当前结点 p 中的数据令当前结点 p 的 rchild 域所指的结点作为当前结点 pb.如果当前结点指针 p 不为空，执行以下操作：当前结点指针 p 入栈令当前结点 p 的 rchild 域所指的结点作为当前结点 p四 使用说明、测试分析及结果1、程序使用说明：（1）本程序运行环境为 Visual C+ 6.0；（2）根据界面提示进行操作：输入多个数据时以空格分隔，每次输入按回车表示输入结束2、测试结果与
9、分析：请输入顶点数据:53 25 76 20 48 14 60 84 33 78中序遍历结果为:14 20 25 33 48 53 60 76 78 84输入待查找数据:33待查找数据存在选择操作(A.新二叉排序树;B.继续查找;C.结束操作):B输入待查找数据:54待查找数据不存在选择操作(A.新二叉排序树;B.继续查找;C.结束操作):C谢谢使用!Press any key to continue由上测试结果分析得，该程序功能满足题目要求。3、调试过程中遇到的问题及解决方法本次实验的错误的主要发生在二叉排序树查找，对进行循环操作的条件判断不够完整，输出数据的条件判断不正确，使运行中出现错误
10、。原因是在 p 为空时，仍判断 p 中数据是否与待查找数据相等。另外，本次实验中的其它小错误都很快修改正确。4、运行界面五、实验总结本次实验提前作了预习，老师在课堂上有详细的讲解，所以此次实验比较顺利，我在11 月 23 日完成了本次实验。本次实验，我很感谢老师和同学对我的指点。通过本次实验，对二叉排序树有了更深的认识，学会了如何利用二叉排序树查找数据，对一些细节更加理解，收获了很多。教师评语：实验成绩：指导教师签名： 批阅日期： 代码：# include# include/typedef struct node /二叉树结点的类型描述char data; /data 用于存储二叉树中的字母s
11、truct node *lchild; /lchild 为指向该结点左孩子的指针struct node *rchild;/rchild 为指向该结点下一层的指针BiTNode;/typedef struct /顺序栈的类型描述BiTNode *pin40; /指针数组，用于存储广义表结点指针int top; /栈顶指针SeqStack;/void Create(BiTNode *B) /建立二叉排序树的函数int m;char r;BiTNode *p,*q; /定义指向当前结点的指针 p,新结点的指针 qp=NULL; /初始时 p 为空printf(请输入顶点数据:);while(r!=n
12、) /输入回车表示循环结束scanf(%d%c, /输入结点数据if(p=NULL) /第一个数据置到根节点，p 指针指向根结点B-data=m;p=B;else /对于其它数据执行以下操作q=(BiTNode *)malloc(sizeof(BiTNode); /申请新结点 qq-data=m; /令该数据存入当前结点的 data 域q-lchild=NULL;q-rchild=NULL; /令新结点 q 的 lchild 域和 rchild 域为空p=B;while(p-data!=q-data) /当 p 指针所指结点和 q 指针所指结点中的数据不同时执行以下操作if(p-datadat
13、a) /如果 p 结点数据小于新结点 q 中的数据, 执行以下操作if(p-rchild=NULL) /如果 p 的右孩子为空，令 p 的右孩子为 qp-rchild=q;p=p-rchild; /将 p 的右孩子赋 pelse /如果 p 结点数据大于新结点 q 中的数据, 执行以下操作if(p-lchild=NULL) /如果 p 的左孩子为空，令 p 的左孩子为 qp-lchild=q;p=p-lchild; /将 p 的左孩子赋 p/void Search(BiTNode *B,int key) /查找函数BiTNode *p; /定义指向当前结点的指针 pp=B; /初始时 p 指向
14、根结点while(p!=NULL&p-data!=key) /当 p 不为空且 p 所指结点的数据不为待查找数据时，执行以下操作if(p-datarchild;else /如果当前结点中的数据大于待查找数据，则令 p 指向它的左孩子p=p-lchild;if(p=NULL) printf(待查找数据不存在n,key);/ 循环结束后，若 p 为空则待查找数据不存在;否则待查找数据存在else printf(待查找数据存在 n,key);printf(n);/void Inorder(BiTNode *B,SeqStack &K) /二叉树的中序遍历函数printf(中序遍历结果为:); /提示
15、以下结果为中序遍历结果BiTNode *p; /p 指针指向当前结点p=B; /当前结点为根结点while(K.top!=-1|p!=NULL) /当栈不为空或当前结点指针 p 不为空时，执行以下操作if(p=NULL) /如果当前结点指针 p 为空，执行以下操作p=K.pinK.top; /出栈，栈顶元素所指的结点作为当前结点 pK.top-;printf(%d ,p-data); /输出当前结点 p 中的数据p=p-rchild; /令当前结点 p 的 rchild 域所指的结点作为当前结点 pelse /如果当前结点指针 p 不为空，执行以下操作K.top+; /当前结点指针 p 入栈K.pinK.top=p;p=p-lchild; /令当前结点 p 的 rchild 域所指的结点作为当前结点 ppr
