1、 课课 程程 设设 计计 课程名称 数据结构课程设计 题目名称 二叉排序树的实现 学 院 应用数学学院 专业班级 学 号 学生姓名 指导教师 2013 年 12 月 26 日 1.1.设计任务设计任务 1）实现二叉排序树，包括生成、插入，删除； 2）对二叉排序树进行先根、中根、和后根非递归遍历； 3）每次对树的修改操作和遍历操作的显示结果都需要在屏幕上 用树的形状表示出来。 4）分别用二叉排序树和数组去存储一个班(50 人以上)的成员信 息(至少包括学号、姓名、成绩 3 项),对比查找效率，并说明 为什么二叉排序树效率高（或者低） 。 2 2. . 函数函数模块：模块： 2.1.2.1.主函数
2、主函数 mainmain 模块功能模块功能 1.通过 bstree CreatTree()操作建立二叉排序树。 2.在二叉排序树 t 中通过操作 bstree InsertBST(bstree t,int key,nametype name,double grade)插入一个节点。 3. 从二叉排序树 t 中通过操作 void Delete(bstree using namespace std; typedef string nametype;typedef string nametype; typedef unsigned long keytype;typedef unsigned long
3、 keytype; typedef struct node /typedef struct node /结点的结构体结点的结构体 keytype key; keytype key; nametype name; nametype name; intint grade;grade; struct node *lchild,*rchild;struct node *lchild,*rchild; bstnode;bstnode; tytypedef bstnode *bstree;pedef bstnode *bstree; /栈的定义栈的定义/ typedef struct /typedef s
4、truct /栈结构栈结构 bstree *base;bstree *base; bstree *top;bstree *top; int stacksize;int stacksize; Sqstack;Sqstack; int InitStack (Sqstack s.base=(bstree*)malloc(1000 * sizeof(int); s.top=s.base;s.top=s.base; return 1;return 1; ; int Push(Sqstack *s.top=e; s.top=s.top+1;s.top=s.top+1; return 1;return 1;
5、 ; int Pop(Sqstack if(s.top=s.base)return 0; else s.top=s.topelse s.top=s.top- -1;1; e=*s.top;e=*s.top; return 1;return 1; ; /非递归历遍并输出结点信息非递归历遍并输出结点信息/ /*/*-先序非递归遍历先序非递归遍历-*/*/ void x_print(nodevoid x_print(node *t)*t) Sqstack s;Sqstack s; InitStack(s);InitStack(s); bstnode *p;bstnode *p; p=t;p=t; while(p|!(s.top=s.base)while(p|!(s.top=s.base) if(p)if(p) Push(s,p);Push(s,p); coutlchild; else else Pop(s,p);Pop(s,p); p=pp=p- -rchild;rchild; /*/*-中序非递归遍历中序非递归遍历-*/*/ void
