《数据结构课程设计(1850)》由会员分享，可在线阅读，更多相关《数据结构课程设计(1850)（38页珍藏版）》请在金锄头文库上搜索。
1、 数 据 结 构课程设计 题 目：二叉排序树院 系：信息工程学院班 级：信息10本1指导老师：安强强日 期：2012年1月10日表11 二叉排序树课程设计任务书课程设计情况课程设计名称二叉排序树指导教师姓名安强强职称讲师需学生数5人组长葛守瑜成员霍小丽、罗健、陈亚维、韦丽田各成员主要负责内容葛守瑜：编写程序代码并参与模块设计。韦丽田：程序模块设计并参与设计目标。 罗 健：课程设计总结并参与详细设计，并整理文档。陈亚维：详细设计并参与模块设计。霍小丽：课程设计目标并参与详细设计。 目 录1课程设计目标.1 1.1 问题描述.1 1.2 问题分析.1 1.3 需求分析.12.概要设计.2 2.1
2、方案确定.2 2.2 程序设计模块.2 2.3 设计连接图.3 2.4 程序功能描述.33.详细设计.5 3.1 方法设计.5 3.2 整体程序流程图.164.程序清单.175.程序测试与运行结果.226.课程设计总结.291、 课程设计目标1 问题描述编写一C语言程序，其功能是建立一个二叉排序树，对二叉排序树进行查找，遍历及最终运行结果进行打印等相关操作。2 问题分析首先,选择合适的存储结构构造二叉排序树，对该程序可以分为几个模块进行分析，每个模块在该程序中的作用进行了解。最后用设计连接图将各模块之间的联系连接起来，以方便我们更容易理解。然后,该程序需要一个详细的设计流程图来表示各个步骤所完
3、成的先后顺序，（如，对二叉排序树进行插入，查找及进行中序遍历并输出打印结果）。最后,按流程图进行编写二叉排序树的程序，输出结果，并将最终的打印结果显示出。3. 需求分析 本次实验设计主要是建立二叉排序树,要实现二叉排序树的中序遍历,二叉排序树的查找,二叉排序树的插入及二叉排序树的更新建立.设计需求上我们需要掌握以下几点:(1).设计需求部分1. 写出本次实验的详细设计方案。2. 画出该次程序的流程图。3. 分析该次程序的程序清单,进行程序测试并输出运行结果。4. 对该次程序中个函数的功能分析结果。5. 对该次实验完成后有总结。(2).设计大纲1. 了解, 分析这次实验的主要问题。2. 讨论解决
4、问题的方案。3. 分配组员的个人任务。4. 进行各部分的整合、修改、完善。5. 进行这次实验的总体报告实验总结。二、概要设计1、方案确定 二叉排序树这个课题要求实现许多功能，我们可遵循结构化程序设计思想来进行本函数一系列的设计,应运用自顶向下，逐步细化的方法执行。本程序可以分为五个小问题：二叉排序树的插入，二叉排序树的建立，二叉排序树的中序遍历，二叉排序树的查找。我们要逐个解决，从而完成整个程序。 2、程序设计模块 该程序可划分为四个模块: 主函数模块main（） 从键盘上输入一组数据，建立一个二叉排序树； 二叉排序树的建立模块BSTree CreateBST(BSTree *bst)建立二叉
5、排序树的链表结构并将其初始化为一个空树；从键盘上依次读入n个关键字并每遇到一关键字就建立一个新的结点； 依次用InsertBST（插入函数）使结点逐个插入到一生成的二叉排序树； 返回根结点T； 二叉排序树的中序遍历模块void OutputBintree(BSTree p)判断根结点是否为空，假如不是空值，则访问左子树，遍历左子树；以左子树为根结点，依次调用OutputBintree（）函数；访问并遍历右子树；二叉排序树的查找模块int SearchBST(BSTree bst,int sea_key)在根指针p所指二叉排序树中非递归查找关键字等于 key 的数据元素； 计算根结点的个数，计算
6、长度；若成功，count+,否则返回count=0； 3、 设计连接图二叉排序树的链表建立模块二叉排序树的结点插入二叉排序树建立模块二叉排序树中序遍历模块二叉排序树查找模块动态查找模块主函数模块二叉排序树 图- 1图3-14. 程序功能描述： insertbst(bstree *bst,int key)函数数据对象：可以是任意类型的数据，但必须属于同一个数据对象；函数功能：二叉排序树结点的插入及左右孩子的定义； 二叉排序树链表结构的建立；基本操作: if(*bst=NULL)：树的判断； if(keykey):关键字和左孩子的判断。BSTree CreateBST(BSTree *bst)函数
7、数据对象：一个集合，该集合中的所有元素具有相同的特性；数据关系：若D为空，则为空树。若D中仅含有一个数据元素，则R为空集,否则R=H，H为如下二元关系：（1） 在D中存在唯一的称为根的数据元素 p它在关系H中没有前驱；（2） 除p外，D中每个结点在关系H下有且仅有一个前驱。基本操作：CreateBST(BSTree *bst)；功能描述：以key为关键字，输入一组有序数，建立一个二叉排序树。void OutputBintree(BSTree p)函数数据对象：不同类型的数据，但必须同属于一个数据对象；函数功能：以根结点是否为空值为线索，分别访问并遍历左右子树，从而完成对整棵树的中序遍历；基本操
8、作：树BSTree：if(p=NULL):根结点的判断； Output Bintree():输出二叉树。nt SearchBST(BSTree bst,int sea_key)函数数据对象：可以是不同的数据类型，但必须同属于一个数据对象；函数功能：用指针p查找二叉排序树中的关键字key；基本操作：插入指向树根结点的指针*p；if(sea-keykey):根结点与关键字的判断。三、详细设计1、方法设计A. 建立二叉排序树（1）将二叉树初始化为一棵空树，每读入一个元素，就建立一个新的结点，并插入到当前已生成的二叉排序树中，即通过多次调用二叉排序树的插入新结点来实现。 Void CreateBST(
9、BSTree *bst) KeyType key; *bst=NULL; Scanf(%d,&key); While(key!=ENDKEY) InsertBST(bst,key); Scanf(%d,&key); B. 二叉排序树的插入 （1）.若二叉排序树是空树，则S成为二叉排序树的根； （2）.若二叉排序树非空，则S.key与二叉排序树根节点的关键字进行比较； a.如果key的值等于根节点的值，则停止插入； b.如果key的值小于根节点的值,则将插入左子树； c.如果key的值大于根节点的值,则将插入右子树。开始创建二叉排序树空二叉树是插入数为根结点否关键字大于根结点是插入右子树否插入左子树结束图3-2void 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(keykey)InsertBST(&(*bst)-lchild),key);else if(key(*bst)-key)InsertBST(&(*bst)-rchild),key
