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

1、一、实验目的1、巩固和加深对数据结构课程基本知识的理解，综合数据结构课程里学的理论知识，完成对 排序二叉树程序的设计。2、 理解和掌握二叉树的各种基本数据结构的定义、存储结构和相应的算法，并能够用c语言 实现。3 、理解排序二叉树的建立过程。二、实验内容采用llink-rlink方式存储二叉排序树，编写能够通过键盘输入建立二叉排序树，并在建立完立即在屏幕显示中序遍历结果的程序。三、实验环境1、 硬件配置：Pentium （ R） Dual-Core9 CUP E6500 2.93GHz，1.96 的内存2、软件环境： Microsoft Windows XP Professional Serv

2、ice Pack 3， Microsoft Visual C+6.0四、需求分析1、输入的形式和输入值的范围：根据题目要求与提示输入一些数字，且数与数之间用空格隔 开并用0作为结束符。2、输出的形式：建立好的排序二叉树的中序遍历结果。3、程序所能达到的功能：能够通过键盘输入建立二叉排序树，并在建立完立即在屏幕显示中 序遍历结果的程序4、 测试数据：输入 45 24 53 12 28 90并用空格将数隔开，以0作为结束符，如：输入 45 24 53 12 28 90输出的中序遍历结果为：12 24 28 45 53 90五、概要设计为了实现上述操作，应以结构体为存储结构。实现如下：struct

3、nodeint key;/关键字的值struct n ode *lchild,*rchild;左右指针BSTNode,*BSTree;1、基本操作：(1) struct nodeint key;/ 关键字的值struct n ode *lchild,*rchild;左右指针BSTNode,*BSTree;。(2) void CreateBST(BSTree *bst)创建二叉排序树(3) void inorder(BSTree bt)递归法中序遍历二叉排序树(4) void InsertBST(BSTree *bst,int key)二叉排序树的插入结点2、本程序包含二个模块：(1) 主程序模

4、块；(2) 创建二叉排序树、二叉排序树的插入结点、递归法中序遍历二叉排序树(3) 模块调用图：主程序模块创建二叉排序树二叉排序树的插入结点递归法中序遍历二叉排序树3、流程图流程图如下:结束六、详细设计1、存储类型，元素类型，结点类型：struct nodeint key;/关键字的值struct n ode *lchild,*rchild;左右指针BSTNode,*BSTree;元素类型为整形和指针形。2、每个模块的分析：(1) 主程序模块：main ()BSTree bt;printf(please insert the numbers(以 0 作为结束标志):n);CreateBST(&b

5、t); /*构造排序二叉树 */printf(n中序遍历结果是:);in order(bt); /*中序遍历排序二叉树 */prin tf(n);getchar();(2) 创建二叉排序树函数模块void CreateBST(BSTree *bst)int key;*bst=NULL;scan f(%d, &key);while(key!=0)In sertBST(bst,key);scan f(%d,&key);二叉排序树的插入结点函数模块void InsertBST(BSTree *bst,int key)BSTree s;if(*bst=NULL)s=(BSTree)malloc(siz

6、eof(BSTNode);s-key=key;s-lchild=NULL;s-rchild=NULL;*bst=s;将s插入左子串将s插入右子串else if(keykey)In sertBST(&(*bst)-lchild),key);else if(key(*bst)-key)In sertBST(&(*bst)-rchild),key);递归法中序遍历二叉排序树void in order(BSTree bt)if(bt!=NULL)ino rder(bt-lchild);prin tf(%3d,bt-key);ino rder(bt-rchild);3）函数调用关系图 main ()Cr

7、eateBST(BSTree *bst)In sertBST(BSTree *bst,i nt key)in order(BSTree bt)3、完整的程序：#i ncludestdio.h#i ncludemalloc.htypedef struct nodeint key;/关键字的值struct n ode *lchild,*rchild;左右指针BSTNode,*BSTree;void In sertBST(BSTree *bst,i nt key) /二叉排序树的插入结点BSTree s;if(*bst=NULL)s=(BSTree)malloc(sizeof(BSTNode);s-

8、key=key;s-lchild=NULL;s-rchild=NULL;*bst=s;else if(keykey)InsertBST(&(*bst)-lchild),key);将 s 插入左子串else if(key(*bst)-key)In sertBST(&(*bst)-rchild),key);void CreateBST(BSTree *bst) /将s插入右子串创建二叉排序树int key;*bst=NULL;scan f(%d, &key); while(key!=O)In sertBST(bst,key); scan f(%d,&key);void ino rder(BSTre

9、e bt)/if(bt!=NULL)ino rder(bt-lchild);prin tf(%3d,bt-key);ino rder(bt-rchild);递归法中序遍历二叉排序树main ()BSTree bt;prin tf(please insert the nu mbers(CreateBST(&bt); /*以0作为结束标志):n);构造排序二叉树*/printf(n中序遍历结果是：”)；in order(bt); /*中序遍历排序二叉树 */prin tf(n);getchar();七、程序使用说明及测试结果1、程序使用说明(1) 本程序的运行环境为 VC6.0。(2) 进入演示程

10、序后即显示提示信息：请输入数字，并以0作为结束标志，回车；即得中序遍历排序二叉树结果2、测试结果：例如：输入：45 24 53 12 28 90输出：12 24 28 45 53 903、调试中的错误及解决办法。调试过程中，遇到了许多的问题，如开始生成一棵二叉排序树的时候，参考书本上的构造二叉 排序树的算法，但是将树的地址传递给函数的参数的时候，运行程序的过程中有问题，后来讲形式 参数改为 BSTree *bst，本来BSTree bst就相当于定义了一个 struct node型的指针，在加*为指向指针的指针。运行界面先输入 45 24 53 12 28 90 后，回车:八、实验小结：这次实验的过程中还是遇到了些许问题，创建二叉排序树、二叉排序树的插入结点算法参考了西安