数据结构课程设计叉排序树的简单应用报告.doc

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