1、 数据结构课程设计 1 课课 程程 设设 计计 报报 告告 数据结构 题目：二叉排序树题目：二叉排序树 姓姓 名：名： 学学 号：号： 专专 业：业： 班班 级：级： 指导老师：指导老师： 年年 月月 日日 数据结构课程设计 2 目目 录录 一、课程设计简介 3 二、原理分析及流程 3 2.1、原理分析3 2.2、流程图4 1、main()函数4 2、创建.4 3、插入.5 4、查找.6 5、中序遍历输出 7 三、算法描述 8 3.1、存储结构. 8 3.2、插入算法. 8 3.3、查找算法. 9 3.4、删除算法. 10 四、小结与体会 12 五、程序执行过程 13 5.1、创建二叉排序树并
2、中序输出.13 5.2、插入并中序输出13 5.3、查找14 六、程序清单 14 数据结构课程设计 3 一、课程设计简介一、课程设计简介 1.1、题目、题目：二叉排序树相关操作：二叉排序树相关操作 1、创建二叉排序树；2、插入给定值； 3、查找给定值； 4、删除给定值的结点。 1.2、报告要求：、报告要求： 1、封面; 2、题目与流程图或模块图; 3、程序清单和运行结果; 4、小结(收获和体会); 5、装订成册。 1.3、目的：、目的： 课程设计为学生提供了一个既动手又动脑，独立实践的机 会，将课本上的理论知识和实际有机的结合起来，锻炼学生的分 析解决实际问题的能力。提高学生适应实际，实践编程
3、的能力。 二、原理分析及流程二、原理分析及流程 2.1、原理分析：、原理分析： 根据题目要求，要实现这些功能，就必须创建一个菜 单。这个菜单设置在 main（）函数里面，然后使用 while().switch()语句进行循环调用相关函数，以达到实现 数据结构课程设计 4 相关功能的目的。 2.2、流程图：、流程图： 1、main（）函数：（）函数： 2、创建：、创建： 选择操作 main()开始 选择 1 创建 选择 2 插入 选择 3 查找 选择 4 删除 选择 5 退出 Create( typedef struct node keytype key; struct node *lchild
4、,*rchild; bstnode,*bstree; 3.2、插入算法、插入算法 在二叉排序树中插入一个新节点， 首先要查找该节点在二叉 排序树中是否已经存在。 若二叉排序树中不存在关键字等于 x的 节点，则插入。 将一个关键字值为 x 的节点 s 插入到二叉排序树中， 可以用 下面的方法： （1）若二叉排序树为空，则关键字为 x的节点 s 成为二叉排 序树的根 （2）若二叉排序树非空，则将 x与二叉排序树根进行比较， 如果 x 的值等于根节点关键值，则停止插入；如果 x的根节点值 小于根节点关键值，则将 x插入左子树；如果 x 的值大于根节点 关键字的值，则将 x 插入右子树。在左右两个子树的插入方法与 数据结构课程设计 9 整个二叉排序树相同。 算法如下： void insert(bstree *t,keytype x) bstree s; if(*t=null) s=(bstree)malloc(sizeof(bstnode); s-key=x; s-lch
