数据结构课程设计--二叉排序树的实现.docx

1、课 程 设 计课程名称 数据结构课程设计 题目名称 二叉排序树的实现 学 院 应用数学学院 专业班级 学 号 学生姓名 指导教师 2013 年 12 月 26 日1.设计任务1）实现二叉排序树，包括生成、插入，删除；2）对二叉排序树进行先根、中根、和后根非递归遍历；3）每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。4）分别用二叉排序树和数组去存储一个班(50 人以上)的成员信 息(至少包括学号、姓名、成绩 3 项),对比查找效率，并说明 为什么二叉排序树效率高（或者低） 。2. 函数模块：2.1.主函数 main 模块功能1.通过 bstree CreatTree()

2、操作建立二叉排序树。 2.在二叉排序树 t 中通过操作 bstree InsertBST(bstree t,int key,nametype name,double grade)插入一个节点。3. 从二叉排序树 t 中通过操作 void Delete(bstree typedef string nametype;typedef unsigned long keytype;typedef struct node /结点的结构体keytype key; nametype name; int grade;struct node *lchild,*rchild;bstnode;typedef bstn

3、ode *bstree;/栈的定义/typedef struct /栈结构bstree *base;bstree *top;int stacksize;Sqstack;int InitStack (Sqstack s.top=s.base;return 1;int Push(Sqstack s.top=s.top+1;return 1;int Pop(Sqstack else s.top=s.top-1;e=*s.top;return 1;/非递归历遍并输出结点信息/*-先序非递归遍历-*/void x_print(node *t)Sqstack s;InitStack(s);bstnode

4、*p;p=t;while(p|!(s.top=s.base)if(p) Push(s,p);coutkeynamegradelchild;else Pop(s,p);p=p-rchild;/*-中序非递归遍历-*/void z_print(node *t)Sqstack s;InitStack(s);bstnode *p;p=t;while(p|!(s.top=s.base)if(p) Push(s,p);p=p-lchild;else Pop(s,p);coutkeynamegraderchild;/*-非递归后序遍历-*/void h_print(node *t)Sqstack s;Ini

5、tStack(s);node *p,*q;p=t;q=NULL;while(p | !(s.top=s.base)if(p)Push(s,p);p=p-lchild;elsep=*(s.top-1);if(p-rchild=q)Pop(s,q);p=NULL;coutkeynamegraderchild;q=NULL;/递归查找二叉树/*-归查找，若找到就返回指向该结点的指针，否则返回空-*/bstnode *SearchBST(bstree t,keytype key) if(t=NULL|key=t-key)return t;if(keykey)return SearchBST(t-lch

6、ild ,key);else return SearchBST(t-rchild ,key);/-给定学生信息插入到二叉树中-/bstree InsertBST(bstree t,int key,nametype name,double grade)bstree p,q;if(t=NULL) /树初始为空，新建二叉树t=new bstnode();t-key=key;t-name=name;t-grade=grade;t-lchild=t-rchild=NULL;elsep=t;while(p) /树已存在，按照二叉排序树的特性查找q=p;if(p-keykey)p=q-lchild;else

7、 if(p-keyrchild;elsecoutkey=key;p-name=name;p-grade=grade;p-lchild=p-rchild=NULL;if(q-keykey)q-lchild=p;elseq-rchild=p;return t;/-二叉树排序树的构建-/bstree CreatTree() /不断输入学生信息以插入到二叉树中bstree t=NULL;keytype key;nametype name;double grade;coutkey;if(key=0)return t;cinname;cingrade;while(key) /key=0 时退出t=Inse

8、rtBST(t,key,name,grade);coutkey;if(key=0)break;cinname;cingrade;return t;/-删除树中的结点-/void Delete(bstree if(!p-rchild)q=p;p=q-lchild ;delete q;else if(!p-lchild)q=p;p=p-rchild;delete q;else q=p;s=p-lchild;while(s-rchild)q=s;s=s-rchild;p-name=s-name;if(q!=p)q-rchild=s-lchild;elseq-lchild=s-lchild;delet

9、e s;void DeleteData(bstree DeleteData(t,key);elseif(t-key=key)Delete(t); /若找到结点直接删除coutkeykey)DeleteData(t-lchild,key); /结点数据比查找关键字大，继续在其左子树中查找elseDeleteData(t-rchild,key); /结点数据比查找关键字小，继续在其右子树中查找/数组和二叉排序树的查找效率比较/void compare()bstree t=NULL;clock_t start,end,start1,end1;int num=0;int a=0;int b=0;int c=0;int d=1;bstree p;string key,name;double grade;nametype str 1003;/coutkey;if(key=“0“)return ;cinname;cingrade;while(key!=“0“)strnum0=key;strnum1=name;strnum2=grade;int key1=atoi(key.c_str(); /用库函数将字符串转化为关键字的 int 型t=InsertBST(t,key1,name,grade); /插入结点coutkey;