二叉排序树课程设计

数据结构课程设计二叉排序树的实现 C++实现

实验报告

课程名称： 数据结构课程实验 题目名称： 二叉排序树的实现 学生学院： 专业班级： 学 号： 学生姓名：__ ____________ __ 指导老师：

2015年6月24日

数据结构课程设计二叉排序树的实现 C++实现

摘要

本程序采用C++模板技术实现二叉排序树。程序包含三个头文件API.h、SortBinTree、Student.h和源文件main.cpp。头文件SortBinTree.h包含了二叉排序树类的模板定义及二叉排序树生成、插入、删除等成员函数的实现（模板类的定义及类成员函数的定义不能分开分别在头文件和源文件）。头文件API.h则包含了一些操纵二叉树的函数，比如比较二叉排序树和数组查找效率的函数。头文件Student.h 则定义了学生结构体。源文件main.cpp则是主函数main函数的所在文件。

关键字：C++

模板 二叉排序树实现

数据结构课程设计二叉排序树的实现 C++实现

目录

1 问题描述： ................................................................................................................................... 1 2 分析设计说明： ........................................................................................................................... 1

2.1 类、结构体： .................................................................................................................... 1 2.2 函数列表： ........................................................................................................................ 2 2.3 各模块分析： .................................................................................................................... 3

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

数据结构课程设计二叉排序树的实现 C++实现

1 问题描述：

二叉排序树的实现

1） 2） 3） 4）

编程实现二叉排序树， 包括生成、插入，删除；

对二叉排序树进行先根、中根、 和后根非递归遍历；

每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。 分别用二叉排序树和数组去存储一个班(50 人以上)的成员信息(至少包括学号、姓名、成绩 3 项),对比查找效率，并说明在什么情况下二叉排序树效率高,为什么?

2 分析设计说明：

2.1 类、结构体：

头文件SortBinTree.h //结点类定义

template<class T> class SBTreeNode {

public:

T data; //数据域 SBTreeNode<T> *left; //左子女 SBTreeNode<T> *right; //右子女 };

//二叉排序树类定义

template<class T> …… 此处隐藏：9406字，全部文档内容请下载后查看。喜欢就下载吧 ……