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

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

2、nal Service 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五、概要设计为了实现上述操作，应以结构体为存储结构。实现如下：str

3、uct node int key;/关键字的值 struct node *lchild,*rchild;/左右指针BSTNode,*BSTree;1、基本操作：（1）struct node int key;/关键字的值 struct node *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 node int key;/关键字的值 struct node *lchild,*rchild;/左右指针BSTNode,*BSTree;元素类型为整形和指针形。2、每个模块的分析：（1）主程序模块：main() BSTree bt; printf("please insert the numbers( 以0作为结束标志):n&

5、quot;); CreateBST(&bt); /*构造排序二叉树*/ printf("n中序遍历结果是:"); inorder(bt); /*中序遍历排序二叉树*/ printf("n"); getchar();（2）创建二叉排序树函数模块void CreateBST(BSTree *bst) int key;*bst=NULL;scanf("%d",&key);while(key!=0)InsertBST(bst,key);scanf("%d",&key);二叉排序树的插入结点函数模块v

6、oid 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) InsertBST(&(*bst)->lchild),key);/将s插入左子串 else if(key>(*bst)->key) InsertBST(&(*bst)->rchild),ke

7、y);/将s插入右子串递归法中序遍历二叉排序树void inorder(BSTree bt) if(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、完整的程序：#include"stdio.h"#include"malloc.h"typedef

8、 struct node int key;/关键字的值 struct node *lchild,*rchild;/左右指针BSTNode,*BSTree;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) InsertBST(&(*bst)->

9、;lchild),key);/将s插入左子串 else if(key>(*bst)->key) InsertBST(&(*bst)->rchild),key);/将s插入右子串void CreateBST(BSTree *bst) /创建二叉排序树int key;*bst=NULL;scanf("%d",&key);while(key!=0)InsertBST(bst,key);scanf("%d",&key);void inorder(BSTree bt) /递归法中序遍历二叉排序树 if(bt!=NULL)

10、inorder(bt->lchild); printf("%3d",bt->key) ; inorder(bt->rchild); main() BSTree bt; printf("please insert the numbers( 以0作为结束标志):n"); CreateBST(&bt); /*构造排序二叉树*/ printf("n中序遍历结果是:"); inorder(bt); /*中序遍历排序二叉树*/ printf("n"); getchar();七、程序使用说明及测试结果1

11、、程序使用说明（1）本程序的运行环境为VC6.0。（2）进入演示程序后即显示提示信息：请输入数字，并以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后， 回车：八、实验小结重点内容： 这次实验的过程中还是遇到了些许问题，创建二叉排