数据结构二叉排序树实验报告解析.doc
文本预览下载声明
一、实验目的
1、巩固和加深对数据结构课程基本知识的理解，综合数据结构课程里学的理论知识，完成对排序二叉树程序的设计。
2、理解和掌握二叉树的各种基本数据结构的定义、存储结构和相应的算法，并能够用c语言实现。
3、理解排序二叉树的建立过程。 二、实验内容
采用llink-rlink方式存储二叉排序树，编写能够通过键盘输入建立二叉排序树，并在建立完立即在屏幕显示中序遍历结果的程序。 四、需求分析1、输入的形式和输入值的范围2、输出的形式3、程序所能达到的功能能够通过键盘输入建立二叉排序树，并在建立完立即在屏幕显示中序遍历结果的程序4、测试数据： 五、概要设计
为了实现上述操作，应以为存储结构。struct node
{
int key;//关键字的值
struct node *lchild,*rchild;//左右指针
}BSTNode,*BSTree;
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）主程序模块；
（2）（）模块调用图：
主程序模块
3、流程图 流程图如下：
六、详细设计
1元素类型，结点类型：struct node
{
int key;//关键字的值
struct node *lchild,*rchild;//左右指针
}BSTNode,*BSTree;
元素类型为整形和指针形。
2、每个模块的分析：
（1）主程序模块：main()
{
BSTree bt;
printf(please insert the numbers( 以0作为结束标志):\n);
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);
}
}
二叉排序树的插入结点函数模块
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)-lchild),key);//将s插入左子串
else if(key(*bst)-key)
InsertBST(((*bst)-rchild),key);//将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、完整的程序：#includestdio.h
#includemalloc.h
typedef struct node
{
int key;//关键字的值
struct node *lchild,*rchild;//左右指针
}BSTNode,*BSTree;
void InsertBST(BSTree *bst,int key) //二叉排序树的插入结点
{
BSTree s;
if(*bst==NULL)
{
s=(BSTr
显示全部