1、 本科生课程设计论文 数据结构与算法 题 目：二叉排序树的操作 1 课程设计任务书 课程名称 数据结构与算法课程设计 设计题目 二叉排序树的操作 指导教师 时间 2015.1.52015.1.9 一、教学要求 1. 掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力 2. 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能 3. 提高综合运用所学的理论知识和方法独立分析和解决问题的能力 4. 训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方 法和作风 二、设计资料及参数 每个学生在教师提供的课程设计题目中任意选择一题，独立完成，
2、题目选定后不可更换。 二叉排序树的操作 以二叉链表表示二叉排序树，在此基础上实现二叉排序树的操作。 要求设计类（或类模板）来描述二叉排序树，包含必要的构造函数和析构函数，以及其他 能够完成如下功能的成员函数： 创建二叉排序树 输出二叉排序树 在二叉排序树中查找给定值 在二叉排序树中插入新结点 在二叉排序树中删除给定值 并设计主函数测试该类（或类模板） 。 三、设计要求及成果 1. 分析课程设计题目的要求 2. 写出详细设计说明 3. 编写程序代码，调试程序使其能正确运行 4. 设计完成的软件要便于操作和使用 5. 设计完成后提交课程设计报告 四、进度安排 资料查阅与讨论（1 天） 系统分析（2
3、 天） 系统的开发与测试（5 天） 编写课程设计说明书和验收（2 天） 五、评分标准 1. 根据平时上机考勤、表现和进度，教师将每天点名和检查 2. 根据课程设计完成情况，必须有可运行的软件。 3. 根据课程设计报告的质量，如有雷同，则所有雷同的所有人均判为不及格。 4. 根据答辩的情况，应能够以清晰的思路和准确、简练的语言叙述自己的设计和回答教师的提问 六、建议参考资料 1 数据结构 （C 语言版） 严蔚敏、吴伟民 主编 清华大学出版社 2004.11 2 数据结构课程设计案例精编（用 C/C+描述） ，李建学 等 编著，清华大学出版社 2007.2 3.数据结构:用面向对象方法与 C+语言
4、描述 ，殷人昆 主编， 清华大学出版社 2007.6 2 目录目录 目录. 2 第一章 需求分析 . 3 第二章 总体设计 . 4 第三章 抽象数据类型定义 . 5 3.1 二叉树 BT 抽象数据类型的设计 5 3.2 BT 抽象数据类型的设计. 6 第四章 详细设计 . 7 4.1 工程视图 . 7 4.2 类图视图 . 7 4.3 函数的调用关系 . 8 4.4 主程序流程图 9 4.5 主要算法的流程图 . 9 第五章 测试 .13 第六章 总结 .20 附录：程序代码 21 3 第一章第一章 需求分析需求分析 二叉排序树的操作 以二叉链表表示二叉排序树，在此基础上实现二叉排序树的操作。
5、 要求设计类（或类模板）来描述二叉排序树，包含必要的构造函数和 析构函数，以及其他能够完成如下功能的成员函数： 创建二叉排序树 输出二叉排序树 在二叉排序树中查找给定值 在二叉排序树中插入新结点 在二叉排序树中删除给定值 并设计主函数测试该类（或类模板） 。 4 第二章第二章 总体设计总体设计 系统的功能结构：设置二叉排序树根结点、添加二排序叉树结点、删除二排 序叉树结点、查找给定的二叉树结点、输出二排序叉树、退出。 功能说明： 设置二叉排序树根结点：为新创建的二叉排序树创建根节点。 添加二排序叉树结点：需要输入创建节点的数目，然后创建一定数目的二叉 排序树结点。 删除二排序叉树结点：给定一个
6、数据(字母)，然后查找，找到后删除，否则， 告知未找到， 查找给定的二叉树结点：给定一个数据(字母)，然后查找，并给出提示。 输出二排序叉树：按照先序遍历并输出二叉排序树的结点数据。 退出：退出程序。 系统功能结构 二叉排序树 设置 二叉 排序 树根 结点 添加 二排 序叉 树结 点 删除 二排 序叉 树结 点 查找 给定 的二 叉树 结点 输出 二排 序叉 树 退出 5 第三章第三章 抽象数据类型定义抽象数据类型定义 定义格式如下： 3.1 二叉树二叉树 BT 抽象数据类型的设计抽象数据类型的设计 ADT BT 数据对象数据对象 root：先定义一个二叉树结点的结构体： typedef struct bst char data; struct bst *left; struct bst *right; struct bst *father; BSTree,*BST; root 是指向二叉树结点的指针； 数据关系：数据关系：R=|V,CD, 表示由运算符 P 结合起来的表达
