数据结构二叉排序树试验报告word文档版

一、实验目的1、巩固和加深对数据结构课程基本知识的理解，综合数据结构课程里学的理论知识，完成对排序二叉树程序的设计。

2、理解和掌握二叉树的各种基本数据结构的定义、存储结构和相应的算法，并能够用C语言实现。3、理解排序二叉树的建立过程。

二、实验内容采用LNKRNK方式存储二叉排序树，编写能够通过键盘输入建立二叉排序树，并在建立完立即在屏幕显示中序遍历结果的程序。

三、实验环境

1、硬件配置：PENTIUM（R）DUALCORE9CUPE6500

2.93GHZ，

1.96的内存

2、软件环境：MICROSOFTWINDOWS_PPROFESSNALSERVICEPACK3，MICROSOFTVISUALC+6.0

四、需求分析

1、输入的形式和输入值的范围：根据题目要求与提示输入一些数字，且数与数之间用空格隔开并用0作为结束符。

2、输出的形式：建立好的排序二叉树的中序遍历结果。

3、程序所能达到的功能：能够通过键盘输入建立二叉排序树，并在建立完立即在屏幕显示中序遍历结果的程序

4、测试数据：输入452XXXX2890并用空格将数隔开，以0作为结束符，如：输入452XXXX2890输出的中序遍历结果为：122XXXX5390

五、概要设计为了实现上述操作，应以结构体为存储结构。实现如下：STRUCTNODEINTKEY键字的值STRUCTNODE_LCHILD,_RCHILD;左右指针BSTNODE,_BSTREE;

1、基本操作：

（1）STRUCTNODEINTKEY键字的值STRUCTNODE_LCHILD,_RCHILD;左右指针BSTNODE,_BSTREE;。

(2)VOIDCREATEBST(BSTREE_BST)创建二叉排序树

(3)VOIDINORDER(BSTREEBT)递归法中序遍历二叉排序树

(4)VOIDINSERTBST(BSTREE_BST,INTKEY)二叉排序树的插入结点

2、本程序包含二个模块：

（1）主程序模块；

(2)创建二叉排序树、二叉排序树的插入结点、递归法中序遍历二叉排序树

(3)模块调用图：主程序模块创建二叉排序树二叉排序树的插入结点递归法中序遍历二叉排序树

3、流程图流程图如下：开始结束教育资料

六、详细设计

1、存储类型，元素类型，结点类型：STRUCTNODEINTKEY键字的值STRUCTNODE_LCHILD,_RCHILD;左右指针BSTNODE,_BSTREE;元素类型为整形和指针形。

2、每个模块的分析：

（1）主程序模块：MAIN()BSTREEBT;PRINTF("PLEASEINSERTTHENUMBERS(以0作为结束标志):N);CREATEBST(BT);构造排序二叉树RINTF("N中序遍历结果是:");INORDER(BT);中序遍历排序二叉树RINTF("N");GETCHAR();

(2)创建二叉排序树函数模块VOIDCREATEBST(BSTREE_BST)INTKEY;_BSTNULL;SCANF("%D",WHILE(KEY!0)INSERTBST(BST,KEY);SCANF("%D",二叉排序树的插入结点函数模块VOIDINSERTBST(BSTREE_BST,INTKEY)BSTREES;IF(_BSTNULL)S(BSTREE)MALLOC(SIZEOF(BSTNODE);S>KEYKEY;S>LCHILDNULL;S>RCHILDNULL;_BSTS;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、完整的程序：#INCLUDE"STD.H"#INCLUDE"MALLOC.H"TYPEDEFSTRUCTNODEINTKEY键字的值STRUCTNODE_LCHILD,_RCHILD;左右指针BSTNODE,_BSTREE;VOIDINSERTBST(BSTREE_BST,INTKEY)叉排序树的插入结点BSTREES;IF(_BSTNULL)S(BSTREE)MALLOC(SIZEOF(BSTNODE);S>KEYKEY;S>LCHILDNULL;S>RCHILDNULL;_BSTS;ELSEIF(KEY<(_BST)>KEY)INSERTBST((_BST)>LCHILD),KEY);将S插入左子串ELSEIF(KEY>(_BST)>KEY)INSERTBST((_BST)>RCHILD),KEY);将S插入右子串VOIDCREATEBST(BSTREE_BST)建二叉排序树INTKEY;_BSTNULL;SCANF("%D",WHILE(KEY!O)INSERTBST(BST,KEY);SCANF("%D",VOIDINORDER(BSTREEBT归法中序遍历二叉排序树IF(BT!NULL)INORDER(BT>LCHILD);PRINTF("%3D",BT>KEY);INORDER(BT>RCHILD);MAIN()BSTREEBT;PRINTF("PLEASEINSERTTHENUMBERS(以0作为结束标志):N");CREATEBST(BT);构造排序二叉树RINTF("N中序遍历结果是：”)；INORDER(BT);中序遍历排序二叉树RINTF("N");GETCHAR();

七、程序使用说明及测试结果

1、程序使用说明

（1）本程序的运行环境为VC

6.0。

(2)进入演示程序后即显示提示信息：请输入数字，并以0作为结束标志，回车；即得中序遍历排序二叉树结果

2、测试结果：例如：输入：452XXXX2890输出：122XXXX5390

3、调试中的错误及解决办法。调试过程中，遇到了许多的问题，如开始生成一棵二叉排序树的时候，

八、实验小结：这次实验的过程中还是遇到了些许问题，创建二叉排序树、二叉排序树的插入结点算法