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

1、仅供个人参考For personal use only in study and research; notfor commercial use课程设计课程名称数据结构课程设计题目名称二叉排序树的实现学院应用数学学院专业班级学号学生姓名指导教师2013年12 月26 日不得用于商业用途仅供个人参考1. 设计任务1）实现二叉排序树，包括生成、插入，删除；2）对二叉排序树进行先根、中根、和后根非递归遍历；3）每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。4）分别用二叉排序树和数组去存储一个班(50 人以上 ) 的成员信息 ( 至少包括学号、姓名、成绩 3 项 ), 对比查

2、找效率，并说明为什么二叉排序树效率高（或者低） 。2. 函数模块：2.1. 主函数 main 模块功能1.通过 bstree CreatTree()操作建立二叉排序树。2.在二叉排序树 t 中通过操作 bstree InsertBST(bstree t,intkey,nametype name,double grade)插入一个节点。3.从二叉排序树 t 中通过操作 voidDelete(bstree &p)删除任意节点。4. 在二叉排序树 t 中通过操作 bstnode *SearchBST(bstree t,keytype key)查找节点。5. 在二叉排序树 t 中通过操作 p=

3、SearchBST(t,key) 查询，并修改节点信息6. 非递归遍历二叉排序树。7. 定义函数 void compare() 对数组和二叉排序树的查找效率进行比较比较。2.2 创建二叉排序树 CreatTree 模块从键盘中输入关键字及记录， 并同时调用插入函数并不断进行插入。 最后，返回根节点 T。2.3 删除模块：二叉排序树上删除一个阶段相当于删去有序系列中的一个记录，只要在删除某个节点之后依旧保持二叉排序树的性质即可。假设二叉排序树上删除节点为 *p（指向节点的指针为 p），其双亲节点为 *f （节点指针为 f ）。若*p 节点为叶子节点，则即左右均为空树，由于删去叶子节点不破坏整棵树

4、的结构，则只需修改其双亲节点的指针即可；若 *p 节点只有左子树或只有右子树，此时只要令左子树或右子树直接成为其双亲节点 *f 的左子树即可；若 *p 节点的左子树和右子树均不为空， 其一可以令 *p 的左子树为 *f 的左子树，而*p 的右子树为 *s 的右子树，其二可以令 *p 的直接前驱（或直接后继）替代 *p ，然后再从二叉排序树中删去它的直接前驱（或直接后继） 。在二叉排序树中删除一个节点的算法为void DeleteData(bstree &t,keytype key)若二叉排序树 t 中存在关键字等于 key 的数据元素，则删除该数据元素节点，并返回 TRUE，否则返回

5、FALSE。2.4 插入模块二叉排序树是一种动态树表，其特点是树的结构通常不是一次生成的，而是在查找的过程中，当树中不存在关键字等于给定值得节点时在进行插入。新插入的节点一定是一个新添加的叶子节点，并且是查找不成功时查找路径上访问的最后一个节点的左孩子或右孩子的节点。一个无序系列可以通过构造一棵二叉排序树而变成一个有序系列，构造树的过程即为对无序系列进行不得用于商业用途仅供个人参考排序的过程， 并且每次插入的节点都是二叉排序树上新的叶子节点，则在进行插入操作时，不必移动其他节点，仅需改变某个节点的指针由空变为非空即可。二叉排序树的插入算法为bstree InsertBST(bstree t,i

6、nt key,nametype name,double grade)若二叉排序树中不存在关键字等于 key 的数据元素时，插入元素并返回 TRUE。 2.5 查找模块二叉排序树又称二叉查找树，当二叉排序树不为空时，首先将给定的值和根节点的关键字比较，若相等则查找成功，否则将依据给定的值和根节点关键字之间的大小关系，分别在左子树或右子树上继续进行查找。为此定义一个二叉排序树的查找算法为bstnode *SearchBST(bstree t,keytype key)在根指针 t 所指向的二叉排序树中查找关键字等于key 的数据元素，如成功，返回指向该元素节点的指针，否则返回空指针。2.6 效率比较

7、 compare 模块void compare()对数组和二叉排序树的查找效率进行比较比较。2.7 二叉排序树的遍历先序遍历也叫做。首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树，如果二叉树为空则返回。其实过程为：先遍历左子树root->left->left->left.->null，由于是先序遍历，因此一遇到节点，便需要立即访问；由于一直走到最左边后，需要逐步返回到父节点访问右节点，因此必须有一个措施能够对节点序列回溯。其一可以用栈记忆在访问途中将依次遇到的节点保存下来。根据栈的先进后出、后进先出的特

8、点特点。则可以用栈保存。每次都将遇到的节点压入栈，当左子树遍历完毕后从栈中弹出最后一个访问的节点，然后访问其右子树。基本算法思想：1. 先访问根节点，将根节点入栈2. 重复执行两大步骤：如果该节点左孩子存在，则访问该左孩子节点，并将其指针入栈。重复以上操作，直到节点的左孩子不存在。将栈顶的元素，即其指针出栈，回到父节点，如果该指针节点的右孩子存在，则将该指针指向的右孩子节点重复执行以上步骤，直到桟为空为止。操作函数为 void x_print(Tree T)中序遍历：中序遍历和先序遍历访问的顺序不同。中序遍历访问顺序为中序遍历左子数，在访问根节点，最后中序遍历右子树。先序遍历是先访问,再入栈；

9、而中序遍历则是先入栈，弹栈后再访问。将二叉树的根节点入栈，如果该节点有左孩子，将左孩子直接入栈，重复该操作，直到该节点无左孩子；在将栈顶元素出栈，并访问该节点指向的节点，如果该指针指向的右孩子存在，则将当前指针指向右孩子节点。重复执行步骤直到栈为空为止。操作函数为 void z_print(Tree T )。后序遍历：先后序遍历左子树，在后序遍历右子树，最后访问根节点。先将根节点入栈，如果该节点左孩子节点存在，将该节点左孩子节点入栈。重复执行此操作，直到节点左孩子节点为空。取栈顶元素，并赋值给P，如果 P的右孩子为空或 P的右孩子等于 （q 即如果 p 的右孩子已访问，则访问根节点，即 p 指

10、向的节点，并用 q 来记录刚刚访问的节点的指针） ，若 p 有右孩子，且不得用于商业用途仅供个人参考右孩子没有别访问过，则p=p->rchild。操作函数为 voidh_print(Tree T)3. 源代码#include<stdio.h>#include<iostream>#include<string>#include<time.h>#include <iomanip>using namespace std;typedef string nametype;typedef unsigned longkeytype;typed

11、ef 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=(bstree*)malloc(1000 * sizeof(int);s.top=s.base;return 1;int Push

12、(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 *p;p=t;while(p|!(s.top=s.base)if(p

13、)Push(s,p);cout<<p->key<<"t"<<setw(20);cout<<p->name<<"t"<<setw(20);cout<<p->grade<<"t"<<endl;p=p->lchild;elsePop(s,p);p=p->rchild;/*-中序非递归遍历-*/void z_print(node *t)Sqstack s;InitStack(s);bstnode *p;p=

14、t;while(p|!(s.top=s.base)if(p)Push(s,p);p=p->lchild;elsePop(s,p);cout<<p->key<<"t"<<setw(20);不得用于商业用途仅供个人参考cout<<p->name<<"t"<<setw(20);cout<<p->grade<<"t"<<endl;p=p->rchild;/*-非递归后序遍历-*/void h_print(n

15、ode *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;elsep=*(s.top-1);if(p->rchild=q)Pop(s,q);p=NULL;cout<<q->key<<"t"<<setw(20);cout<<q->name<<"t"<<setw(20);cout<<q->grade

16、<<"t"<<endl;elsep=p->rchild;q=NULL;/ 递归查找二叉树/*- 归查找，若找到就返回指向该结点的指针，否则返回空 -*/ bstnode *SearchBST(bstree t,keytype key) if(t=NULL|key=t->key)return t;if(key<t->key)return SearchBST(t->lchild ,key);elsereturn SearchBST(t->rchild ,key);不得用于商业用途仅供个人参考/-给定学生信息插入到二叉树

17、中-/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->key>key)p=q->lchild;else if(p->key<key)p=q->rc

18、hild;elsecout<<endl;cout<<" 树中已有该节点:"<<key<<endl;cout<<endl;return t;p=new bstnode(); / 找不到结点就新建一个结点插入到二叉排序树中 p->key=key;p->name=name;p->grade=grade;p->lchild=p->rchild=NULL;if(q->key>key)q->lchild=p;elseq->rchild=p;return t;/-二叉树排序树

19、的构建-/不得用于商业用途仅供个人参考bstree CreatTree()/不断输入学生信息以插入到二叉树中bstree t=NULL;keytype key;nametype name;double grade;cout<<" 请输入 - 学号 - 姓名 - 成绩 - （输入 0 时结束） :"<<endl;cin>>key;if(key=0)return t;cin>>name;cin>>grade;while(key)/key=0时退出t=InsertBST(t,key,name,grade);cout<

20、;<" 请输入 - 学号 - 姓名 - 成绩 - （输入 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;else if(!p->lchild)q=p;p=p->rchild;delete q;elseq=p;s=p-

21、>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>>key;DeleteData(t,key);elseif(t->key=key)Del

22、ete(t);/若找到结点直接删除cout<<" 删除成功！ "<<endl;else if(t->key>key)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

23、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;while(key!="0&qu

24、ot;)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<<endl;cout&l

25、t;<"进行数组和二叉排序树的查询效率比较（比较：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<=)/循环模拟数组查找不得用于商业用途仅供

26、个人参考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();/同

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

28、=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)in

29、t k;if(t=NULL)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<<" 二叉排序树的树形表示如下"<<

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

31、除信息|"<<endl;cout<<"|c查询信息|"<<endl;cout<<"|d修改信息|"<<endl;不得用于商业用途仅供个人参考cout<<"|0退出|"<<endl;cout<<"|e对二叉排序树进行非递归遍历|"<<endl;cout<<"|f进行数组和二叉树查找效率实验|"<<endl;cout<<"|-|"

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

33、<<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<<"

34、请输入要删除信息学生的成绩："<<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<<" 无查询的

35、关键字："<<key<<endl;elsecout<<"成 绩 "<<"t"<<setw(20)<<"姓 名 "<<"t"<<setw(20)<<"学 号"<<endl;cout<<p->key<<"t"<<setw(20);cout<<p->name<<"t&quo

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

37、t; 请输入修改的成绩："cin>>grade;p->name=name;p->grade=grade;break;case 'e':if(!t)cout<<" 没有任何信息，请先输入信息！"elsecout<<"学 号 "<<"t"<<setw(20)<<"姓 名 "<<"t"<<setw(20)<<"成 绩"<<en

38、dl;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<<"*此实验为独立实验，实验数据独立于外部数

39、据*"<<endl;cout<<"*请重新输入相关信息*"<<endl;compare();break;default:cout<<" 选择错误！ "break;cout<<endl;cout<<endl;cout<<" "<<endl;cout<<"-请输入你要选择的操作-"<<endl;cout<<"|-|"<<endl;cout<<"|-|&quo