《数据结构_二叉排序树实验报告》由会员分享，可在线阅读，更多相关《数据结构_二叉排序树实验报告（12页珍藏版）》请在金锄头文库上搜索。
1、一、实验目的1、稳固和加深对数据构造课程根本知识的理解，综合数据构造课程里学的理论知识，完成对 排序二叉树程序的设计。2、理解和掌握二叉树的各种根本数据构造的定义、存储构造和相应的算法，并能够用c语言 实现。3、理解排序二叉树的建立过程。二、实验内容采用llink-rlink方式存储二叉排序树，编写能够通过键盘输入建立二叉排序树，并在建立完立 即在屏幕显示中序遍历结果的程序。三、实验环境1、硬件配置：2、软件环境：Micros。ft Windows XP Professional Service Pack 3 Micros。ft Visual C+6.0四、需求分析1、输入的形式和输入值的范围
2、：根据题目要求与提示输入一些数字，且数与数之间用空格隔 开并用0作为完毕符。2、输出的形式：建立好的排序二叉树的中序遍历结果。3、程序所能到达的功能：能够通过键盘输入建立二叉排序树，并在建立完立即在屏幕显示中 序遍历结果的程序4、测试数据：输入45 24 53 12 28 90并用空格将数隔开，以0作为完毕符，如：输入 45 24 53 12 28 90输出的中序遍历结果为：12 24 28 45 53 90五、概要设计为了实现上述操作，应以构造体为存储构造。实现如下：struct nodeint key;/关键字的值struct node *lchild,*rchild;/左右扌旨针BSTN
3、ode,*BSTree;1、根本操作： struct nodeint key;/关键字的值struct node *lchild,*rchild;/左右扌旨针BSTNode,*BSTree;。2void CreateBST(BSTree *bst)创立二叉排序树3void inorder(BSTree bt)递归法中序遍历二叉排序树4void InsertBST(BSTree *bst,int key)二叉排序树的插入结点2、本程序包含二个模块：1主程序模块；2创立二叉排序树、二叉排序树的插入结点、递归法中序遍历二叉排序树3模块调用图：主程序模块创立二叉排序树二叉排序树的插入结点递归法中序遍历
4、二叉排序树3、流程图流程图如下：开始六、详细设计1、存储类型，元素类型，结点类型：struct nodeint key;/关键字的值struct node *lchild,*rchild;/左右扌旨针BSTNode,*BSTree;元素类型为整形和指针形。2、每个模块的分析：1主程序模块：main()BSTree bt;printf (please insert the numbers(以 0 作为完毕标志)：n);Crea teBST(&bt); /*构造排序二叉树*/printf (n中序遍历结果是:)；inorder(b t); /*中序遍历排序二叉树*/printf(n)；get ch
5、ar();2创立二叉排序树函数模块void CreateBST(BSTree *bst)int key;*bst=NULL;scanf(%d，& key);while(key!=0)Inser tBST(bs t,key);scanf(%d，& key);二叉排序树的插入结点函数模块void InsertBST(BSTree *bst,int key)BSTree s;if(*bst=NULL)s=(BSTree)malloc(sizeof(BSTNode);s-key=key;s-lchild二NULL;s-rchild二NULL;*bst=s;else if(key(*bst)-key)I
6、nsertBST(&(*bst)-lchild),key);/将 s 插入左子串else if(key(*bst)-key)InsertBST(& (*bst)-rchild),key);/将 s 插入右子串递归法中序遍历二叉排序树void inorder(BSTree bt)辻(bt!=NULL)inorder(bt-lchild);printf(%3d,bt-key);inorder(bt-rchild);3函数调用关系图main()CreateBST(BSTree *bst) InsertBST(BSTree *bst,int key)inorder(BSTree bt)3、完整的程序：
7、#includestdio.h#includemalloc.htypedef struct nodeint key;/关键字的值struct node *lchild,*rchild;/左右扌旨针BSTNode,*BSTree;void Inser tBST(BSTree *bs t,int key) /二叉排序树的插入结点BSTree s;if(*bst=NULL)s=(BSTree)malloc(sizeof(BSTNode); s-key=key;s-lchild二NULL;s-rchild二NULL;*bst=s;else if(key(*bst)-key)InsertBST(& (*
8、bst)-rchild),key);/将 s 插入右子串void Crea teBST(BSTree *bs t)/创立二叉排序树int key;*bst=NULL;scanf(%d，& key);while(key!=O)Inser tBST(bs t,key);scanf(%d，& key);void inorder(BSTree bt)/递归法中序遍历二叉排序树辻(bt!=NULL)inorder(bt-lchild);printf(%3d,bt-key);inorder(bt-rchild);main()BSTree bt;printf (please insert the numbe
9、rs(以 0 作为完毕标志)：n);Crea teBST(&bt); /*构造排序二叉树*/printf (n中序遍历结果是:)；inorder(b t); /*中序遍历排序二叉树*/printf(n)；get char();七、程序使用说明及测试结果1、程序使用说明1本程序的运行环境为VC6.0。2进入演示程序后即显示提示信息：请输入数字，并以0作为完毕标志，回车；即得中序遍历排序二叉树结果2、测试结果：例如：输入：45 24 53 12 28 90输出：12 24 28 45 53 903、调试中的错误及解决方法。调试过程中，遇到了许多的问题，如开场生成一棵二叉排序树的时候，参考书本上的构
10、造二叉 排序树的算法，但是将树的地址传递给函数的参数的时候，运行程序的过程中有问题，后来讲形式 参数改为BSTree *bst,本来BSTree bst就相当于定义了一个struct node型的指针，在加*为指 向指针的指针。运行界面先输入 45 24 53 12 28 90 后，后来进过调试后程序能够正确运行，总之，通过本次试验，对树的知识还是有了更深层次的了解， 比方如何去构建一棵二叉排序树，平时简建树的算法才用递归的算法，但是二叉排序树是有规律的 树，对加深了递归算法了解。签名：日期：实验成绩：批阅日期：【本文档内容可以自由复制内容或自由编辑修改内容期待你的好评和关注，我们将会做得更好】
