数据结构_二叉排序树实验报告

一、实验目的1、巩固和加深对数据结构课程基本知识的理解，综合数据结构课程里学的理论知识，完成对排序二叉树程序的设计。2、理解和掌握二叉树的各种基本数据结构的定义、存储结构和相应的算法，并能够用c语言实现。3、理解排序二叉树的建立过程。二、实验内容采用llink-rlink方式存储二叉排序树，编写能够通过键盘输入建立二叉排序树，并在建立完立即在屏幕显示中序遍历结果的程序。三、实验环境1、硬件配置：Pentium（R）Dual-Core9CUPE6500@2.93GHz，1.96的内存2、软件环境：MicrosoftWindowsXPProfessionalServicePack3，MicrosoftVisualC++6.0四、需求分析1、输入的形式和输入值的范围：根据题目要求与提示输入一些数字，且数与数之间用空格隔开并用0作为结束符。2、输出的形式：建立好的排序二叉树的中序遍历结果。3、程序所能达到的功能：能够通过键盘输入建立二叉排序树，并在建立完立即在屏幕显示中序遍历结果的程序4、测试数据：输入452453122890并用空格将数隔开，以0作为结束符，如：输入452453122890输出的中序遍历结果为：122428455390五、概要设计为了实现上述操作，应以结构体为存储结构。实现如下：structnode{intkey;//关键字的值structnode*lchild,*rchild;//左右指针}BSTNode,*BSTree;1、基本操作：（1）structnode{intkey;//关键字的值structnode*lchild,*rchild;//左右指针}BSTNode,*BSTree;。（2）voidCreateBST(BSTree*bst)创建二叉排序树（3）voidinorder(BSTreebt)递归法中序遍历二叉排序树（4）voidInsertBST(BSTree*bst,intkey)二叉排序树的插入结点2、本程序包含二个模块：（1）主程序模块；（2）创建二叉排序树、二叉排序树的插入结点、递归法中序遍历二叉排序树（3）模块调用图：主程序模块创建二叉排序树二叉排序树的插入结点递归法中序遍历二叉排序树3、流程图流程图如下：开始定义BSTree变量bt;printf(pleaseinsertthenumbers(以0作为结束标志):\n);调用CreateBST(BSTree*bst)函数定义int型变量key;key!=0调用InsertBST(BSTree*bst,intkey)函数*bst=NULLscanf(%d,&key)NYBSTrees;*bst==NULLkey(*bst)-keys=(BSTree)malloc(sizeof(BSTNode));key(*bst)-keyNYYNInsertBST(&((*bst)-lchild),key)InsertBST(&((*bst)-rchild),key)YNscanf(%d,&key);printf(\n中序遍历结果是:);调用inorder(BSTreebt)函数bt!=NULLinorder(bt-lchild)YNprintf(%3d,bt-key)inorder(bt-lchild)printf(\n)getchar()结束六、详细设计1、存储类型，元素类型，结点类型：structnode{intkey;//关键字的值structnode*lchild,*rchild;//左右指针}BSTNode,*BSTree;元素类型为整形和指针形。2、每个模块的分析：（1）主程序模块：main(){BSTreebt;printf(pleaseinsertthenumbers(以0作为结束标志):\n);CreateBST(&bt);/*构造排序二叉树*/printf(\n中序遍历结果是:);inorder(bt);/*中序遍历排序二叉树*/printf(\n);getchar();}（2）创建二叉排序树函数模块voidCreateBST(BSTree*bst){intkey;*bst=NULL;scanf(%d,&key);while(key!=0){InsertBST(bst,key);scanf(%d,&key);}}二叉排序树的插入结点函数模块voidInsertBST(BSTree*bst,intkey){BSTrees;if(*bst==NULL){s=(BSTree)malloc(sizeof(BSTNode));s-key=key;s-lchild=NULL;s-rchild=NULL;*bst=s;}elseif(key(*bst)-key)InsertBST(&((*bst)-lchild),key);//将s插入左子串elseif(key(*bst)-key)InsertBST(&((*bst)-rchild),key);//将s插入右子串}递归法中序遍历二叉排序树voidinorder(BSTreebt){if(bt!=NULL){inorder(bt-lchild);printf(%3d,bt-key);inorder(bt-rchild);}}3）函数调用关系图main()CreateBST(BSTree*bst)InsertBST(BSTree*bst,intkey)inorder(BSTreebt)3、完整的程序：#includestdio.h#includemalloc.htypedefstructnode{intkey;//关键字的值structnode*lchild,*rchild;//左右指针}BSTNode,*BSTree;voidInsertBST(BSTree*bst,intkey)//二叉排序树的插入结点{BSTrees;if(*bst==NULL){s=(BSTree)malloc(sizeof(BSTNode));s-key=key;s-lchild=NULL;s-rchild=NULL;*bst=s;}elseif(key(*bst)-key)InsertBST(&((*bst)-lchild),key);//将s插入左子串elseif(key(*bst)-key)InsertBST(&((*bst)-rchild),key);//将s插入右子串}voidCreateBST(BSTree*bst)//创建二叉排序树{intkey;*bst=NULL;scanf(%d,&key);while(key!=0){InsertBST(bst,key);scanf(%d,&key);}}voidinorder(BSTreebt)//递归法中序遍历二叉排序树{if(bt!=NULL){inorder(bt-lchild);printf(%3d,bt-key);inorder(bt-rchild);}}main(){BSTreebt;printf(pleaseinsertthenumbers(以0作为结束标志):\n);CreateBST(&bt);/*构造排序二叉树*/printf(\n中序遍历结果是:);inorder(bt);/*中序遍历排序二叉树*/printf(\n);getchar();}七、程序使用说明及测试结果1、程序使用说明（1）本程序的运行环境为VC6.0。（2）进入演示程序后即显示提示信息：请输入数字，并以0作为结束标志，回车；即得中序遍历排序二叉树结果2、测试结果：例如：输入：452453122890输出：1224284553903、调试中的错误及解决办法。调试过程中，遇到了许多的问题，如开始生成一棵二叉排序树的时候，参考书本上的构造二叉排序树的算法，但是将树的地址传递给函数的参数的时候，运行程序的过程中有问题，后来讲形式参数改为BSTree*bst，本来BSTreebst就相当于定义了一个structnode型的指针，在加*为指向指针的指针。运行界面先输入452453122890后，回车：八、实验小结：这次实验的过程中还是遇到了些许问题，创建二叉排序树、二叉排序树的插入结点算法参考了西安电子科技大学出版社耿国华老师出的数据结构c语言描述，卡是编译的时候有错误提示，后来进过调试后程序能够正确运行，总之，通过本次试验，对树的知识还是有了更深层次的了解，比如如何去构建一棵二叉排序树，平时简建树的算法才用递归的算法，但是二叉排序树是有规律的树，对加深了递归算法了解。签名：日期：实验成绩：批阅日期：