二叉排序树课程设计
2.3.1 二叉排序树的生成:...........................................................................................3 2.3.2 二叉排序树的插入:.............................................................................................4 2.3.3 二叉排序树的删除:.............................................................................................5 2.3.4 二叉排序树的注销:.............................................................................................6 2.3.5 二叉排序树前序遍历非递归算法:.....................................................................7 2.3.6 二叉排序树中序遍历非递归算法:.....................................................................7 2.3.7 二叉排序树后序遍历非递归算法:.....................................................................8 2.3.8 树形输出二叉排序树:.........................................................................................9 2.3.9 查找效率比较:................................................................................................... 11 2.3.10 其它:.................................................................................................................12 3 功能与界面...............................................................................................................................13 3.1 二叉排序树的生成:......................................................................................................13 3.2 二叉排序树的插入..........................................................................................................14 3.3 二叉排序树的删除..........................................................................................................15 3.4 二叉排序树的注销...........................................................................................................16 3.5 打印二叉排序树..............................................................................................................17 3.6 二叉排序树的遍历输出..................................................................................................18 3.7 效率对比及分析..............................................................................................................19 4 总结 ............................................................................................................................................20 4.1 优点:..............................................................................................................................20 4.2 缺点:..............................................................................................................................21 4.3 改进..................................................................................................................................21 5 附录 ............................................................................................................................................23 5.1 头文件 SortBinTree.h ......................................................................................................23 5.2 头文件 API.h ...................................................................................................................37 5.3 头文件 Student.h .............................................................................................................40 5.4 源文件 main.cpp..............................................................................................................42
2.1 类、结构体:....................................................................................................................1 2.2 函数列表:........................................................................................................................2 2.3 各模块分析:....................................................................................................................3
实验报告
课程名称: 数据结构课程实验 题目名称: 二叉排序树的实现 学生学院: 专业班级: 学 号: 学生姓名:__ ____________ __ 指导老师:
2015 年 6 月 24 日
摘要
本程序采用 C++模板技术实现二叉排序树。程序包含三个头文件 API.h、SortBinTree、 Student.h 和源文件 main.cpp。头文件 SortBinTree.h 包含了二叉排序树类的模板定义及二叉 排序树生成、插入、删除等成员函数的实现(模板类的定义及类成员函数的定义不能分开分 别在头文件和源文件)。头文件 API.h 则包含了一些操纵二叉树的函数,比如比较二叉排序 树和数组查找效率的函数。头文件 Student.h 则定义了学生结构体。源文件 main.cpp 则是主 函数 main 函数的所在文件。
//数据域 //左子女 //右子女
//二叉排序树类定义
template<class T>
class SortBTree
{
public:
SortBTree():root(NULL){} ~SortBTree(){ DeleteAll();}
//构造函数 //析构函数
……
1
private: SBTreeNode<T> * root; ……
1 问题描述:
二叉排序树的实现
1) 编程实现二叉排序树, 包括生成、插入,删除; 2) 对二叉排序树进行先根、中根、 和后根非递归遍历; 3) 每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。 4) 分别用二叉排序树和数组去存储一个班(50 人以上)的成员信息(至少包括学号、姓