1、 数据结构课程设计 设计说明书 二叉排序树的简单应用 起止日期：2012 年 12 月 22 日 至 2013 年 01 月 02 日 学生姓名 班级 信 息 管 理 类 112 班 成绩 指 导 教 师 ( 签 字 ) 年年 月月 日日 数据结构课程设计 1 目 录 一、问题描述 2 二、测试数据 2 三、算法思想 2 四、模块划分 3 五、数据结构 3 六、源程序 3 七、测试情况 . 11 八、设计体会及今后的改进意见 . 13 参 考 文 献 13 数据结构课程设计 2 一、问题描述 1)1)具体具体问题描述问题描述 输入树的各个结点，建立排序二叉树，对建立的排序二叉树进行层次、先序、
2、中序和 后序遍历并统计该二叉树中叶子结点的数目等。 2)2)基本要求基本要求 (1)用菜单实现 (2)能够输入树的各个结点，并能够输出用不同方法遍历的遍历序列和叶子结点的数 目。 二、测试数据 （1）关键字序列为（45,24，53,12,37,93） （2）关键字序列为（44,10,50,3,33,100,22,61,90,78） 三、算法思想 因为二叉排序树的操作要根据结点的关键字域来进行，所以，首先要定义每个结点的 数据域类型。二叉排序树的遍历算法和二叉树类似，利用链表存储二叉树，用队列实现层 次遍历，利用栈进行非递归中序遍历二叉树，所以在创建二叉排序树之前，定义二叉链表 的存储表示，对队
3、列、栈进行定义 。 二叉排序树的创建是从空的二叉排序树开始，每输入一个结点，经过查找操作（二叉 排序树插入的基本过程是查找） ， ，将新的结点插入到当前二叉排序树的合适位置。首先将 二叉排序树 T 初始化为空树，读入一个关键字为 key 的结点，将此结点插入到二叉排序树 T 中，重复执行，直至读入的关键字 key 是输入结束标志。 根据开始定义好的队列的定义、操作，用队列实现层次遍历；按先序次序输入二叉树 中结点的值（一个字符），创建二叉链表表示的二叉树 T；分别输入先序遍历二叉树 T 的 递归算法、中序遍历二叉树 T 的递归算法、后序遍历二叉树 T 的递归算法；利用栈进行非 递归中序遍历二叉
4、树，非空根指针进栈，遍历左子树，为空根指针退栈,访问根结点,遍历 右子树；递归查找叶子数，左子树的叶子数加上右叶子数，可以计算出二叉树的叶子数 数据结构课程设计 3 四、模块划分 （1）二叉排序树的操作要根据结点的关键字域来进行，其中包括基本操作的函数有：用 队列实现层次遍历操作函数、先序遍历有序二叉树 T 的递归算法、中序遍历有序二叉树 T 的递归算法、后序遍历有序二叉树 T 的递归算法、用栈实现非递归中序遍历有序二叉树 T 的算法、求有序二叉树的叶子数，该抽象数据类型文件名为 BSTree.h。 （2）void InsertBST(BSTree /关键字项 ElemType; typede
5、f struct BSTNode ElemType data; /每个结点数据域包括关键字项和其他数据项 struct BSTNode *lchild,*rchild; /左右孩子指针 BSTNode,*BSTree; 六、源程序 源程序存放在文件 BSTree.h 中 文件 BSTree.h： 数据结构课程设计 4 #include using namespace std; typedef int Status; #define OVERFLOW -2 #define OK 1 #define TRUE 1 #define FALSE 0 #define ERROR 0 #define MA
6、XQSIZE 100 /最大队列长度 typedef struct ElemType int key; ElemType; typedef struct BSTNode ElemType data; /结点数据域 struct BSTNode *lchild,*rchild; /左右孩子指针 BSTNode,*BSTree; /队列定义 typedef struct BSTree *base; /初始化的动态分配存储空间的基础 int front; /队头指针 int rear; /队尾指针 SqQueue; /顺序队列的类型名 /栈的定义 typedef struct BSTree *base; BSTree *top; int stacksize; SqStack; /队列的基本操作 数据结构课程设计 5 Status InitQueue(SqQueue if(!Q.base) exit(OVERFLOW); Q.f
