数据结构课程设计报告二叉排序树的实现教案

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

2、ee()操作建立二叉排序树。 2.在二叉排序树t中通过操作bstree InsertBST(bstree t,int key,nametype name,double grade)插入一个节点。3. 从二叉排序树t中通过操作void Delete(bstree &p)删除任意节点。4. 在二叉排序树t中通过操作bstnode *SearchBST(bstree t,keytype key)查找节点。5. 在二叉排序树t中通过操作p=SearchBST(t,key)查询，并修改节点信息6. 非递归遍历二叉排序树。7. 定义函数void compare()对数组和二叉排序树的查找效率进行比较比较。

3、2.2创建二叉排序树CreatTree模块从键盘中输入关键字及记录，并同时调用插入函数并不断进行插入。最后，返回根节点T。2.3删除模块：二叉排序树上删除一个阶段相当于删去有序系列中的一个记录，只要在删除某个节点之后依旧保持二叉排序树的性质即可。假设二叉排序树上删除节点为*p（指向节点的指针为p），其双亲节点为*f（节点指针为f）。若*p节点为叶子节点，则即左右均为空树，由于删去叶子节点不破坏整棵树的结构，则只需修改其双亲节点的指针即可；若*p节点只有左子树或只有右子树，此时只要令左子树或右子树直接成为其双亲节点*f的左子树即可；若*p节点的左子树和右子树均不为空，其一可以令*p的左子树为*f

4、的左子树，而*p的右子树为*s的右子树，其二可以令*p的直接前驱（或直接后继）替代*p，然后再从二叉排序树中删去它的直接前驱（或直接后继）。在二叉排序树中删除一个节点的算法为void DeleteData(bstree &t,keytype key)若二叉排序树t中存在关键字等于key的数据元素，则删除该数据元素节点，并返回TRUE，否则返回FALSE。2.4插入模块二叉排序树是一种动态树表，其特点是树的结构通常不是一次生成的，而是在查找的过程中，当树中不存在关键字等于给定值得节点时在进行插入。新插入的节点一定是一个新添加的叶子节点，并且是查找不成功时查找路径上访问的最后一个节点的左孩子或右孩

5、子的节点。一个无序系列可以通过构造一棵二叉排序树而变成一个有序系列，构造树的过程即为对无序系列进行排序的过程， 并且每次插入的节点都是二叉排序树上新的叶子节点，则在进行插入操作时，不必移动其他节点，仅需改变某个节点的指针由空变为非空即可。二叉排序树的插入算法为bstree InsertBST(bstree t,int key,nametype name,double grade) 若二叉排序树中不存在关键字等于key的数据元素时，插入元素并返回TRUE。2.5查找模块二叉排序树又称二叉查找树，当二叉排序树不为空时，首先将给定的值和根节点的关键字比较，若相等则查找成功，否则将依据给定的值和根节点

6、关键字之间的大小关系，分别在左子树或右子树上继续进行查找。为此定义一个二叉排序树的查找算法为bstnode *SearchBST(bstree t,keytype key) 在根指针t所指向的二叉排序树中查找关键字等于key的数据元素，如成功，返回指向该元素节点的指针，否则返回空指针。2.6效率比较compare模块void compare()对数组和二叉排序树的查找效率进行比较比较。2.7二叉排序树的遍历先序遍历也叫做 HYPERLINK /view/2872148.htm t _blank 先根遍历。首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根结点，然后遍

7、历左子树，最后遍历右子树，如果二叉树为空则返回。其实过程为：先遍历左子树root-left-left-left.-null，由于是先序遍历，因此一遇到节点，便需要立即访问；由于一直走到最左边后，需要逐步返回到父节点访问右节点，因此必须有一个措施能够对节点序列回溯。其一可以用栈记忆在访问途中将依次遇到的节点保存下来。根据栈的先进后出、后进先出的特点特点。则可以用栈保存。每次都将遇到的节点压入栈，当左子树遍历完毕后从栈中弹出最后一个访问的节点，然后访问其右子树。基本算法思想：1.先访问根节点，将根节点入栈2.重复执行两大步骤：如果该节点左孩子存在，则访问该左孩子节点，并将其指针入栈。重复以上操作，

8、直到节点的左孩子不存在。将栈顶的元素，即其指针出栈，回到父节点，如果该指针节点的右孩子存在，则将该指针指向的右孩子节点重复执行以上步骤，直到桟为空为止。操作函数为void x_print(Tree T)中序遍历：中序遍历和先序遍历访问的顺序不同。中序遍历访问顺序为中序遍历左子数，在访问根节点，最后中序遍历右子树。先序遍历是先访问,再入栈；而中序遍历则是先入栈，弹栈后再访问。将二叉树的根节点入栈，如果该节点有左孩子，将左孩子直接入栈，重复该操作，直到该节点无左孩子；在将栈顶元素出栈，并访问该节点指向的节点，如果该指针指向的右孩子存在，则将当前指针指向右孩子节点。重复执行步骤直到栈为空为止。操作函

9、数为void z_print(Tree T )。后序遍历：先后序遍历左子树，在后序遍历右子树，最后访问根节点。先将根节点入栈，如果该节点左孩子节点存在，将该节点左孩子节点入栈。重复执行此操作，直到节点左孩子节点为空。取栈顶元素，并赋值给P，如果P的右孩子为空或P的右孩子等于q（即如果p的右孩子已访问，则访问根节点，即p指向的节点，并用q来记录刚刚访问的节点的指针），若p有右孩子，且右孩子没有别访问过，则p=p-rchild。操作函数为void h_print(Tree T)3.源代码#include#include#include#include#include using namespace

10、 std;typedef string nametype;typedef unsigned long keytype;typedef struct node /结点的结构体keytype key; nametype name; int grade;struct node *lchild,*rchild;bstnode;typedef bstnode *bstree;/栈的定义/typedef struct /栈结构bstree *base;bstree *top;int stacksize;Sqstack;int InitStack (Sqstack &s) /建立一个空栈s.base=(bs

11、tree*)malloc(1000 * sizeof(int);s.top=s.base;return 1;int Push(Sqstack &s ,node *e)/在栈顶插入元素（进栈）*s.top=e;s.top=s.top+1;return 1;int Pop(Sqstack &s, bstree &e)/出栈if(s.top=s.base)return 0;else s.top=s.top-1;e=*s.top;return 1;/非递归历遍并输出结点信息/*-先序非递归遍历-*/void x_print(node *t)Sqstack s;InitStack(s);bstnode

12、*p;p=t;while(p|!(s.top=s.base)if(p) Push(s,p);coutkeytsetw(20);coutnametsetw(20);coutgradetlchild;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);coutkeytsetw(20);coutnametsetw(20);coutgr

13、adetrchild;/*-非递归后序遍历-*/void h_print(node *t)Sqstack s; InitStack(s);node *p,*q;p=t;q=NULL; while(p | !(s.top=s.base)if(p)Push(s,p); p=p-lchild; else p=*(s.top-1); if(p-rchild=q) Pop(s,q);p=NULL; coutkeytsetw(20);coutnametsetw(20);coutgradetrchild;q=NULL; /递归查找二叉树/ /*-归查找，若找到就返回指向该结点的指针，否则返回空-*/bstn

14、ode *SearchBST(bstree t,keytype key) if(t=NULL|key=t-key)return t;if(keykey)return SearchBST(t-lchild ,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-gr

15、ade=grade;t-lchild=t-rchild=NULL;elsep=t;while(p) /树已存在，按照二叉排序树的特性查找q=p;if(p-keykey)p=q-lchild;else if(p-keyrchild;elsecoutendl;cout树中已有该节点:keyendl;coutkey=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() /不断输入学生信息以插入

16、到二叉树中bstree t=NULL;keytype key;nametype name;double grade;cout请输入-学号-姓名-成绩-（输入0时结束）:key;if(key=0)return t;cinname;cingrade;while(key) /key=0时退出t=InsertBST(t,key,name,grade);cout请输入-学号-姓名-成绩-（输入0时结束）:key;if(key=0)break;cinname; cingrade;return t;/-删除树中的结点-/void Delete(bstree &p) /删除结点的函数bstree q,s;if

17、(!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;delete s;void DeleteData(bstree &t,keytype key)if(!t)coutkey;DeleteData(t,key);elseif(t-key=key)Delete(t); /若找

18、到结点直接删除cout删除成功！keykey)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;/c

19、out（输入0时结束）endl;cout请输入-学号-姓名-成绩-（输入0时结束）:key;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); /插入结点cout请输入-学号-姓名-成绩-（输入0时结束）:key;if(key=0)break;cinname;cingrade;num+;coutendl; coutd;

20、while(d!=NULL) switch(d) case 0: cout返回选择界面endl;break; case 1:cout数组查询！endl;cout请输入查询的成绩：key;start=clock();while(a=10000000) /循环模拟数组查找while(b=100)cout数组查询：无查询信息，花费时间: end-start 毫秒endl;elsecout数组查询：查到信息，花费时间: end-start 毫秒endl;int key1=atoi(key.c_str(); /同上转化start1=clock();while(c=10000000) /用循环来模拟树中查

21、找p=SearchBST(t,key1);c+;end1=clock();if(p=NULL)cout树查询：无查询信息，花费时间: end1-start1 毫秒endl;else cout树查询：查到信息，花费时间: end1-start1 毫秒endl;a=0;b=0;c=0;break; coutd;/二叉树的深度int TreeDepth(bstree t)int left,right,max;if(t!=NULL)left=TreeDepth(t-lchild);right=TreeDepth(t-rchild);max=leftright?left:right;return max

22、+1;elsereturn 0;/树状输出二叉树void PrintTree(bstree t,int layer)int k;if(t=NULL)return ;PrintTree(t-rchild,layer+1);for(k=0;klayer;k+)cout ;coutkeylchild,layer+1);/-主函数测试-/int main()int d; keytype key;bstree t=NULL; t=CreatTree();d=TreeDepth(t);cout二叉排序树的树形表示如下endl; PrintTree(t,d);char choose;nametype nam

23、e;bstree p;double grade; cout endl;cout-请输入你要选择的操作-endl;cout |-|endl;cout |-|endl;cout | a 插入信息 |endl;cout | b 删除信息 |endl;cout | c 查询信息 |endl;cout | d 修改信息 |endl;cout | 0 退出 |endl;cout | e 对二叉排序树进行非递归遍历 |endl;cout | f 进行数组和二叉树查找效率实验|endl;cout |-|endl;cout |-|endl;coutendl;coutchoose;coutendl;while(c

24、hoose)switch(choose)case a:/cout输入学生信息信息（学号为0时结束）.endl;cout请输入-学号-姓名-成绩-（输入0时结束）:key;if(key=0) /*PrintTree(t,d);break;*/cinname;cingrade;while(key) t=InsertBST(t,key,name,grade);cout请输入-学号-姓名-成绩-:key;if(key=0)break;cinname; cingrade;break;case b:cout请输入要删除信息学生的成绩：key;DeleteData(t,key); d=TreeDepth(t

25、); cout删除结点后二叉树的树形显示如下endl; PrintTree(t,d);break;case c:cout请输入要查询的成绩：key;p=SearchBST(t,key);if(p=NULL)cout无查询的关键字：keyendl;elsecout成绩tsetw(20)姓名tsetw(20)学号endl; coutkeytsetw(20);coutnametsetw(20); coutgradeendl;break;case d:cout请输入要修改的学号：key;p=SearchBST(t,key);if(p=NULL)cout无你所要修改的关键字：keyendl;elsecoutname;coutgrade;p-name=name;p-grade=grade;break;case e:if(!t)cout没有任何信息，请先输入信息！;elsecout学号tsetw(20)姓名tsetw(20)成绩endl;cout-非递归先序遍历-endl;coutendl;x_print(t);cout-非递归中序遍历-endl;coutendl;z_print(t);cout-非递归后序