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

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 &p)删除任意节点。4. 在二叉排序树t中通过操作bstnode *SearchBST(bstree t,keytype key)查找节点。5. 在二叉排序树t中通过操作p=SearchBST(t,key)查询，并修改节点信息6. 非递归遍历二叉排序树。7. 定义函数void compare()对数组和二叉排序树的查找效率进行比较比较。2

3、.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二叉排序树的遍历先序遍历也叫做先根遍历。首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树，如果二叉树为空则返回。其实过程为：先遍历左子

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

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

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

10、nclude<time.h>#include <iomanip>using namespace 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 sta

11、cksize;Sqstack;int InitStack (Sqstack &s) /建立一个空栈s.base=(bstree*)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;/非递

12、归历遍并输出结点信息/*-先序非递归遍历-*/void x_print(node *t)Sqstack s;InitStack(s);bstnode *p;p=t;while(p|!(s.top=s.base)if(p) Push(s,p);cout<<p->key<<"t"<<setw(20);cout<<p->name<<"t"<<setw(20);cout<<p->grade<<"t"<<endl;p=p

13、->lchild;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);cout<<p->key<<"t"<<setw(20);cout<<p->name<<"t"<<setw(20);

14、cout<<p->grade<<"t"<<endl;p=p->rchild;/*-非递归后序遍历-*/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; cout<<q->key<<"

15、t"<<setw(20);cout<<q->name<<"t"<<setw(20);cout<<q->grade<<"t"<<endl; else p=p->rchild;q=NULL; /递归查找二叉树/ /*-归查找，若找到就返回指向该结点的指针，否则返回空-*/bstnode *SearchBST(bstree t,keytype key) if(t=NULL|key=t->key)return t;if(key<t->

16、key)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->grade=grade;t->lchild=t->rchild=NULL;elsep=t;whi

17、le(p) /树已存在，按照二叉排序树的特性查找q=p;if(p->key>key)p=q->lchild;else if(p->key<key)p=q->rchild;elsecout<<endl;cout<<"树中已有该节点:"<<key<<endl;cout<<endl;return t;p=new bstnode(); /找不到结点就新建一个结点插入到二叉排序树中p->key=key;p->name=name;p->grade=grade;p->l

18、child=p->rchild=NULL;if(q->key>key)q->lchild=p;elseq->rchild=p;return t;/-二叉树排序树的构建-/bstree CreatTree() /不断输入学生信息以插入到二叉树中bstree t=NULL;keytype key;nametype name;double grade;cout<<"请输入-学号-姓名-成绩-（输入0时结束）:"<<endl;cin>>key;if(key=0)return t;cin>>name;cin

19、>>grade;while(key) /key=0时退出t=InsertBST(t,key,name,grade);cout<<"请输入-学号-姓名-成绩-（输入0时结束）:"<<endl; cin>>key;if(key=0)break;cin>>name; cin>>grade;return t;/-删除树中的结点-/void Delete(bstree &p) /删除结点的函数bstree q,s;if(!p->rchild)q=p;p=q->lchild ;delete q;

20、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)cout<<"没有该信息，请重新输入！" cin>&

21、gt;key;DeleteData(t,key);elseif(t->key=key)Delete(t); /若找到结点直接删除cout<<"删除成功！"<<endl;else if(t->key>key)DeleteData(t->lchild,key); /结点数据比查找关键字大，继续在其左子树中查找elseDeleteData(t->rchild,key); /结点数据比查找关键字小，继续在其右子树中查找/数组和二叉排序树的查找效率比较/void compare()bstree t=NULL;clock_t sta

22、rt,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;/cout<<"（输入0时结束）"<<endl;cout<<"请输入-学号-姓名-成绩-（输入0时结束）:"<<endl;cin>>key;if(key="0") return ;cin>>name;cin>>grade;

23、while(key!="0")strnum0=key;strnum1=name;strnum2=grade;int key1=atoi(key.c_str(); /用库函数将字符串转化为关键字的int型t=InsertBST(t,key1,name,grade); /插入结点cout<<"请输入-学号-姓名-成绩-（输入0时结束）:"<<endl;cin>>key;if(key="0")break;cin>>name;cin>>grade;num+;cout<<e

24、ndl; cout<<"进行数组和二叉排序树的查询效率比较（比较：1 不比较：0）" cin>>d;while(d!=NULL) switch(d) case 0: cout<<"返回选择界面"<<endl;break; case 1:cout<<"数组查询！"<<endl;cout<<"请输入查询的成绩："<<endl;cin>>key;start=clock();while(a<=10000000)

25、 /循环模拟数组查找while(b<=99)if(strb0=key)b=100;elseb+;b=0;a+;end=clock();if(num>=100)cout<<"数组查询：无查询信息，花费时间: "<<end-start<<" 毫秒"<<endl;elsecout<<"数组查询：查到信息，花费时间: "<<end-start<<" 毫秒"<<endl;int key1=atoi(key.c_str(

26、); /同上转化start1=clock();while(c<=10000000) /用循环来模拟树中查找p=SearchBST(t,key1);c+;end1=clock();if(p=NULL)cout<<"树查询：无查询信息，花费时间: "<<end1-start1<<" 毫秒"<<endl;else cout<<"树查询：查到信息，花费时间: "<<end1-start1<<" 毫秒"<<endl;a=0;

27、b=0;c=0;break; cout<<"是否继续进行操作（是：1 否：0）："cin>>d;/二叉树的深度int TreeDepth(bstree t)int left,right,max;if(t!=NULL)left=TreeDepth(t->lchild);right=TreeDepth(t->rchild);max=left>right?left:right;return max+1;elsereturn 0;/树状输出二叉树void PrintTree(bstree t,int layer)int k;if(t=NUL

28、L)return ;PrintTree(t->rchild,layer+1);for(k=0;k<layer;k+)cout<<" "cout<<t->key<<"n"PrintTree(t->lchild,layer+1);/-主函数测试-/int main()int d; keytype key;bstree t=NULL; t=CreatTree();d=TreeDepth(t);cout<<"二叉排序树的树形表示如下"<<endl; Print

29、Tree(t,d);char choose;nametype name;bstree p;double grade; cout<<" "<<endl;cout<<"-请输入你要选择的操作-"<<endl;cout<<" |-|"<<endl;cout<<" |-|"<<endl;cout<<" | a 插入信息 |"<<endl;cout<<" | b 删

30、除信息 |"<<endl;cout<<" | c 查询信息 |"<<endl;cout<<" | d 修改信息 |"<<endl;cout<<" | 0 退出 |"<<endl;cout<<" | e 对二叉排序树进行非递归遍历 |"<<endl;cout<<" | f 进行数组和二叉树查找效率实验|"<<endl;cout<<" |

31、-|"<<endl;cout<<" |-|"<<endl;cout<<endl;cout<<"需要选择的操作为："cin>>choose;cout<<endl;while(choose)switch(choose)case 'a':/cout<<"输入学生信息信息（学号为0时结束）."<<endl;cout<<"请输入-学号-姓名-成绩-（输入0时结束）:"<<

32、;endl;cin>>key;if(key=0) /*PrintTree(t,d);break;*/cin>>name;cin>>grade;while(key) t=InsertBST(t,key,name,grade);cout<<"请输入-学号-姓名-成绩-:"<<endl;cin>>key;if(key=0)break;cin>>name; cin>>grade;break;case 'b':cout<<"请输入要删除信息学生的成绩：

33、"<<endl;cin>>key;DeleteData(t,key); d=TreeDepth(t); cout<<"删除结点后二叉树的树形显示如下"<<endl; PrintTree(t,d);break;case 'c':cout<<"请输入要查询的成绩："<<endl;cin>>key;p=SearchBST(t,key);if(p=NULL)cout<<"无查询的关键字："<<key<&l

34、t;endl;elsecout<<"成绩"<<"t"<<setw(20)<<"姓名"<<"t"<<setw(20)<<"学号"<<endl; cout<<p->key<<"t"<<setw(20);cout<<p->name<<"t"<<setw(20); cout<<

35、;p->grade<<endl;break;case 'd':cout<<"请输入要修改的学号："<<endl;cin>>key;p=SearchBST(t,key);if(p=NULL)cout<<"无你所要修改的关键字："<<key<<endl;elsecout<<"请输入修改的姓名："cin>>name;cout<<"请输入修改的成绩："cin>>grade

36、;p->name=name;p->grade=grade;break;case 'e':if(!t)cout<<"没有任何信息，请先输入信息！"elsecout<<"学号"<<"t"<<setw(20)<<"姓名"<<"t"<<setw(20)<<"成绩"<<endl;cout<<"-非递归先序遍历-"<<endl;cout<<endl;x_print(t);cout<<"-非递归中序遍历-"<<endl;cout<<endl;z_print(t);cout<<"-非递归后序遍历-"<<endl;cout<<endl;h_print(t);break; case 'f':cout<<"*此实验为独立实验，实验数据独立于外部数据*"<<endl; cout<<"*请重新输入相关信息*