黄淮学院
“数据结构”课程设计
报告
系 （院）： 信息工程学院
设计题目： 二叉排序树的实现
专业班级： 软件工程15级
小组成员： 唐二虎、赵梦娟、贾月 指导教师: 汪洋 完成时间： 2016。12。27
二叉排序树的实现
1.设计任务
1）实现二叉排序树，包括生成、插入，删除；
2）对二叉排序树进行先根、中根、和后根非递归遍历；
3）每次对树的修改操作和遍历操作的显示结果都需要在用树的形状表示出来。 4）分别用二叉排序树和数组去存储一个班(50人以上）的成员信 息(至少包括学号、姓名、成绩3项),对比查找效率，并说明 为什么二叉排序树效率高（或者低）。
2.程序设计流程图（设计思想）
二叉链表作存储结构和顺序表作存储结构 输入数列L， 以回车(‘\\\\n’)为输入结束标志生成二叉排序树T； 对二叉排序树T作中序遍历,并输出结果
输入元素x，查找二叉排序树T 找到该节点x 无结点x 存在含x的结点，则删除该结点，并作中序遍历 1
详细设计思想：
建立二叉排序树采用边查找边插入的方式。查找函数采用递归的方式进行查找。如果查找到相等的则插入其左子树.然后利用插入函数将该元素插入原树。 对二叉树进行中序遍历采用递归函数的方式。在根结点不为空的情况下,先访问左子树，再访问根结点，最后访问右子树。
删除结点函数，采用边查找边删除的方式。如果没有查找到，进行提示；如果查找到结点则将其左子树最右边的节点的数据传给它，然后删除其左子树最右边的节点.
3。函数模块：
3.1.主函数main模块功能
1。通过bstreeCreatTree（)操作建立二叉排序树。
2。在二叉排序树t中通过操作bstreeInsertBST(bstreet,int key，nametypename,double grade)插入一个节点。
3. 从二叉排序树t中通过操作void Delete（bstree&p）删除任意节点。 4。在二叉排序树t中通过操作bstnode *SearchBST(bstreet,keytype key)
查找节点.
5.在二叉排序树t中通过操作p=SearchBST（t,key）查询，并修改节点信息
3。2创建二叉排序树CreatTree模块
从键盘中输入关键字及记录，并同时调用插入函数并不断进行插入。最后，返回根节点T。 3。3删除模块：
二叉排序树上删除一个阶段相当于删去有序系列中的一个记录，只要在删除某个节点之后依旧保持二叉排序树的性质即可.假设二叉排序树上删除节点为＊p(指向节点的指针为p），其双亲节点为＊f(节点指针为f）。若＊p节点为叶子节点，则即左右均为空树，由于删去叶子节点不破坏整棵树的结构，则只需修改其双亲节点的指针即可；若＊p节点只有左子树或只有右子树，此时只要令左子树或右子树直接成为其双亲节点*f的左子树即可;若＊p节点的左子树和右子树均不为空,其一可以令*p的左子树为＊f的左子树，而*p的右子树为＊s的右子树，其二可以令＊p的直接前驱（或直接后继）替代＊p，然后再从二叉排序树中删去它的直接前驱（或直接后继）。在二叉排序树中删除一个节点的算法为
voidDeleteData(bstree＆t,keytype key)
2
6.非递归遍历二叉排序树。
7.定义函数void compare（）对数组和二叉排序树的查找效率进行比较比较.
若二叉排序树t中存在关键字等于key的数据元素，则删除该数据元素节点，并返回TRUE，否则返回FALSE。 3.4插入模块
二叉排序树是一种动态树表,其特点是树的结构通常不是一次生成的，而是在查找的过程中，当树中不存在关键字等于给定值得节点时在进行插入。新插入的节点一定是一个新添加的叶子节点,并且是查找不成功时查找路径上访问的最后一个节点的左孩子或右孩子的节点。一个无序系列可以通过构造一棵二叉排序树而变成一个有序系列,构造树的过程即为对无序系列进行排序的过程, 并且每次插入的节点都是二叉排序树上新的叶子节点,则在进行插入操作时，不必移动其他节点，仅需改变某个节点的指针由空变为非空即可。二叉排序树的插入算法为
bstreeInsertBST（bstreet,intkey，nametypename,double grade) 若二叉排序树中不存在关键字等于key的数据元素时，插入元素并返回TRUE。 3.5查找模块
二叉排序树又称二叉查找树，当二叉排序树不为空时，首先将给定的值和根节点的关键字比较，若相等则查找成功，否则将依据给定的值和根节点关键字之间的大小关系，分别在左子树或右子树上继续进行查找。为此定义一个二叉排序树的查找算法为
bstnode *SearchBST（bstreet，keytype key)
在根指针t所指向的二叉排序树中查找关键字等于key的数据元素,如成功，返回指向该元素节点的指针，否则返回空指针。 3。6二叉排序树的遍历
先序遍历也叫做先根遍历.首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时,仍然先访问根结点，然后遍历左子树,最后遍历右子树，如果二叉树为空则返回.其实过程为：先遍历左子树root-〉left—〉left->left。.。->null，由于是先序遍历，因此一遇到节点，便需要立即访问；由于一直走到最左边后，需要逐步返回到父节点访问右节点，因此必须有一个措施能够对节点序列回溯.其一可以用栈记忆在访问途中将依次遇到的节点保存下来.根据栈的先进后出、后进先出的特点特点。则可以用栈保存。每次都将遇到的节点压入栈,当左子树遍历完毕后从栈中弹出最后一个访问的节点，然后访问其右子树。
基本算法思想：
1.先访问根节点，将根节点入栈
2.重复执行两大步骤：如果该节点左孩子存在，则访问该左孩子节点，并将其指针入栈.重复以上操作，直到节点的左孩子不存在。将栈顶的元素,即
3
其指针出栈，回到父节点，如果该指针节点的右孩子存在,则将该指针指向的右孩子节点重复执行以上步骤，直到桟为空为止. 操作函数为void x_print(Tree T）
中序遍历：中序遍历和先序遍历访问的顺序不同.中序遍历访问顺序为中序遍历左子数，在访问根节点，最后中序遍历右子树。先序遍历是先访问,再入栈;而中序遍历则是先入栈,弹栈后再访问。将二叉树的根节点入栈，如果该节点有左孩子，将左孩子直接入栈，重复该操作，直到该节点无左孩子;在将栈顶元素出栈，并访问该节点指向的节点,如果该指针指向的右孩子存在，则将当前指针指向右孩子节点.重复执行步骤直到栈为空为止。 操作函数为void z_print(Tree T )。
后序遍历：先后序遍历左子树，在后序遍历右子树，最后访问根节点。先将根节点入栈，如果该节点左孩子节点存在，将该节点左孩子节点入栈。重复执行此操作，直到节点左孩子节点为空.取栈顶元素,并赋值给P，如果P的右孩子为空或P的右孩子等于q（即如果p的右孩子已访问，则访问根节点,即p指向的节点，并用q来记录刚刚访问的节点的指针),若p有右孩子，且右孩子没有别访问过，则p=p—>rchild. 操作函数为void h_print（Tree T）
4。源代码
＃include /＊ run this program using the console pauser or add your own getch， system(”pause\"） or input loop */ ＃include〈stdio.h> ＃include〈iostream〉 ＃include typedefstruct node //结点的结构体 { keytype key; nametype name； int grade； struct node *lchild,＊rchild； }bstnode； typedefbstnode *bstree； 4 //栈的定义// typedefstruct{ bstree *base; bstree *top； intstacksize; }Sqstack； intInitStack (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; elses。top=s。top-1; e=*s.top； return 1； ｝; //非递归历遍并输出结点信息// /*—-—--——-——————-先序非递归遍历—--—-—---——---—＊/ voidx_print(node *t) { Sqstack s; InitStack（s)； bstnode *p; p=t； while（p||!（s。top==s.base)） { if（p) ｛ Push(s,p）； cout< cout< Pop(s，p）； p=p—>rchild; } } } /*-——--—--—--————中序非递归遍历—-—-----—---———＊/ voidz_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< /＊—-——-————-————-非递归后序遍历—--——-———--—-——＊/ voidh_print（node *t） { Sqstack s; InitStack(s); node *p，＊q； 6 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< cout<〈q-〉name〈<”\”〈 p=p->rchild；q=NULL; } ｝ } ｝ //递归查找二叉树// /*-——归查找，若找到就返回指向该结点的指针,否则返回空-—-*/ bstnode *SearchBST（bstreet,keytype key) ｛ if（t==NULL||key==t—>key） return t; if(key returnSearchBST(t—>lchild ,key)； else returnSearchBST(t—>rchild ，key）； } //——---—-—-——----—---给定学生信息插入到——-———--—-———-————-// bstreeInsertBST（bstreet,intkey，nametypename，double grade） ｛ bstreep,q; if（t==NULL) ｛ t=new bstnode()； t->key=key; t->name=name； 7 二叉树中 t—〉grade=grade； t—〉lchild=t—〉rchild=NULL; } else { p=t； while（p) ｛ q=p; if(p—>key〉key） p=q—>lchild； else if(p->key cout< p—〉lchild=p->rchild=NULL; if（q—〉key>key） q-〉lchild=p； else q—>rchild=p; } return t; } //--—-—-—-—-————--——-二叉树排序树的构 -—————————--—--——--// bstreeCreatTree() { bstree t=NULL; keytype key; nametype name； double grade; printf（\"\\n＊＊＊＊*本系统由二胡科技所有成员公同组建!＊***＊\\n\\n\\n\")； printf（\"请输入—--学号-——姓名—-—成绩—-—（输入0时结束）：\\n\")； 8 建 cin〉〉key； if(key==0) return t； cin〉>name; cin〉〉grade; while（key） ｛ t=InsertBST（t，key，name，grade); printf(”请输入-——学号-—-姓名——-成绩-——（输入0时结束）：\\n”); cin〉>key； if(key==0） break; cin>>name； cin〉>grade； } return t; ｝ //--—---—---—-—---—-—删除树中的结点-—-————-———-——--——-// void Delete（bstree＆p） { bstreeq，s; 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; ｝ 9 p-〉name=s—〉name; if（q！=p) q—〉rchild=s->lchild； else q—〉lchild=s-〉lchild; delete s； } ｝ voidDeleteData(bstree&t，keytype key） { if(！t){ printf(”没有该信息，请重新输入！\\n”); cin>>key; DeleteData(t,key)； } else ｛ if（t-〉key==key) { Delete（t)； printf（”删除成功！\\n”）； } else if（t-〉key>key） DeleteData(t—〉lchild,key）; DeleteData(t->rchild，key）； } } //二叉树的深度 intTreeDepth（bstree t) ｛ intleft，right,max； if(t!=NULL） ｛ left=TreeDepth（t—〉lchild）; right=TreeDepth(t—>rchild）； max=left〉right？left：right; return max+1; }else ｛ return 0; ｝ ｝ //树状输出二叉树 10 else voidPrintTree(bstreet,int layer） ｛ int k; if(t==NULL） return ; PrintTree(t-〉rchild，layer+1）； for(k=0；k〈layer;k++) cout<〈” \"； cout< PrintTree(t->lchild,layer+1）； } //—---—-——————--—-—--主函数测试-——---——----——--———// int main（) ｛ int d; //system(”cls\"）； system（”Color 2f\")； keytype key; bstree t=NULL; t=CreatTree()； d=TreeDepth（t); printf(\"二叉排序树的树形表示如下\\n\"）; PrintTree(t，d)； char choose； nametype name; bstree p; double grade; printf(\" \\n\"）; printf（”-—————--————-——---—--—————-——请输入你要选择的操作——--—-—--——-—-—-———---—-—--—-—-\\n\"）； printf（” ｜—--——-—-——-—-———--—-—-——-——--——-—--——|\\n”）; printf(” ||--——-—-—----——----——-—-—————----——-｜|\\n\")； printf（\" ｜| a 插入信息 ||\\n\"）; printf（\" ｜｜ b 删除信息 ||\\n\"）; printf(\" ｜| c 查询信息 ||\\n\")； printf（” ｜| d 修改信息 ||\\n\"）; printf(\" || 0 退出 ||\\n”); printf（\" ｜| e 对二叉排序树进行非递归遍历 ｜|\\n”）； 11 printf（” ｜|-———-—-——-—---———-————--—--------—-|｜\\n\"）； printf(\" ｜———---——--————-—-—---——---————--—-——-｜\\n”); printf(\"\\n”）； printf（”需要选择的操作为：”)； cin>>choose; cout<〈endl； while(choose) { switch（choose） ｛ case ’a’: printf(\"输入需要插入的学生信息信息（学号为0时结束).\\n\")； printf（\"请输入-——学号--—姓名———成绩-——(输入0时结束）:\\n\")； cin>>key; if(key==0) ｛ PrintTree(t，d)； printf（\"\\n***＊＊插入信息结束！”）； break；} cin>>name； cin〉〉grade； while(key) { t=InsertBST（t,key，name，grade）; printf(”请输入—--学号---姓名-——成绩——-（输入0时结束)：\\n\"）； cin>〉key； if(key==0） printf(”插入信息结束！”）; break； cin>〉name； cin〉>grade； } break; case ’b’： printf（\"请输入要删除信息学生的学号：\\n”）； cin>〉key； DeleteData(t，key）; d=TreeDepth(t); printf（\"删除结点后二叉树的树形显示如下\\n”）； PrintTree(t，d）； break; 12 case 'c’： cout<<\"请输入要查询学生的学号:”<〈endl; cin>>key； p=SearchBST（t，key）; if（p==NULL) cout〈<”无查询的关键字：”〈 printf(”请输入要修改学生的学号:\\n”）； cin〉>key； p=SearchBST（t，key）; if(p==NULL） cout<〈”无你所要修改的关键字:”< printf（\"\\n请输入修改的成绩:\")； cin>〉grade； p->name=name; p—〉grade=grade； printf（”\\n修改成功！\\n\"）; ｝ break； case ’e’: if（！t） printf(\"没有任何信息，请先输入信息！”）; else { cout<<”学号”<<”\\"<〈setw(20）〈<”姓名\"<〈”\\"<〈setw（20）<〈\"成绩\"<〈endl； printf(\"——-——-——----——————非递归先序遍历---—-—----——----\\n\"）； printf（”\\n\")； x_print（t)； printf（”--—--—----—-—-—-—-非递归中序遍历——-—-—-—-—--—-——-\\n”）； printf(”\\n”）； 13 z_print（t）; printf(\"--———————-----——-—非递归后序遍历—-—-——-——-————-——\\n\"）； printf（\"\\n\")； h_print（t）; ｝ break; case '0': { printf（\"程序终止!\\n\"）; return 0； ｝ default： printf(\"选择错误！\\n”); break； ｝ printf(”\\n”）； printf(\"\\n\"）； printf(” \\n”）; printf（”--—————--—--—————-——-—-—-—---请输入你要选择的操作———---——-——-——-----—-——-——----—\\n\"）； printf(\" |----—--—-—--—-—-—-———-——-—-——-—--———-｜\\n\"); printf(” ||--———-————---————---——--———-—---——-|｜\\n\"）； printf(\" |｜ a 插入信息 ｜|\\n\")； printf（” ｜｜ b 删除信息 |｜\\n”）； printf(” ｜｜ c 查询信息 |｜\\n\"); printf(” |｜ d 修改信息 ｜｜\\n”）； printf（\" ｜｜ 0 退出 |｜\\n”）; printf(\" || e 对二叉排序树进行非递归遍历 ｜|\\n”）; printf(” ｜｜-—-———---——-——-—---—-———-——---—--——||\\n”）; printf(” ｜--——----—-————-——------————-——--—-—--|\\n”); printf(\"\\n\")； printf（\"选择的操作位：\"）； cin〉〉choose; cout〈〈endl; 14 ｝ return 0； } 5.运行结果及截图 从键盘读入数据 以0作为结束标志可得二叉排序树树状表示 主菜单选择模块 15 需要在树种添加节点则执行操作a 需要在书中删除节点执行操作b 需要查询节点信息执行操作c 修改某一节点信息执行操作d 16 执行操作e对树进行先序遍历、后序遍历、中序遍历运行结果如下图 执行操作0退出程序执行 17 因篇幅问题不能全部显示，请点此查看更多更全内容