第九组数据结构课程设计(二叉排序树实现)

1、黄滚曇院“数据结构”课程设计报告系（院）： 信息工程学院 _设计题目： 二叉排序树的实现 _专业班级： 软件工程15级 _小组成员：唐二虎、赵梦娟、贾月 _指导教师：汪洋 _二叉排序树的实现1.设计任务1）实现二叉排序树，包括生成、插入，删除；2）对二叉排序树进行先根、中根、和后根非递归遍历；3）每次对树的修改操作和遍历操作的显示结果都需要在用树的形状表示出来。4）分别用二叉排序树和数组去存储一个班（50人以上）的成员信息（至少包括学号、姓名、成绩3项），对比查找效率，并说明 为什么二叉排序树效率高（或者低）。2程序设计流程图（设计思想）详细设计思想：建立二义排序树釆用边查找边插入的方式。查找

2、函数釆用递归的方式进行查找。 如果查找到相等的则插入其左子树。然后利用插入函数将该元素插入原树。对二义树进行中序遍历釆用递归函数的方式。在根结点不为空的惜况下，先访问 左子树，再访问根结点，最后访问右子树。删除结点函数，采用边查找边删除的方式。如果没有查找到，进行提示；如果查 找到结点则将其左子树最右边的节点的数据传给它，然后删除其左子树最右边的 节点。3. 函数模块：3.3. 1.1.主函数mainmain模块功能1.通过bstreeCreatTree ()操作建立.义排序树。2.在二义排序树 t 中通过操作 bstreelnsertBST(bstreet, intkey, ndmetype

3、name, double grade)扌番入一个节点。3.从二义排序树t中通过操作void Delete(bstree&p)删除任意节点。4.在:叉排序树 t 中通过操作 bstnode *SearchBST(bstreet, keytype key)查找节点。5.在二义排序树t中通过操作p=SearchBST (t, key)查询，并修改节点信息6.非递归遍历二叉排序树。7.定义函数void compare ()对数组和二义排序树的查找效率进行比较比较。3.3. 2 2创建二叉排序树CreatTreeCreatTree模块从键盘中输入关键字及记录，并同时调用插入函数并不断进行插入。最后, 返

4、回根节点T。3.3. 3 3删除模块：二义排序树上删除一个阶段相当于删去有序系列中的一个记录，只要在删 除某个节点之后依旧保持二义排序树的性质即可。假设二叉排序树上删除节 点为*P (指向节点的指针为P),其双亲节点为水f (节点指针为f)。若*p节点 为叶子节点，则即左右均为空树，由于删去叶子节点不破坏整棵树的结构， 则只需修改其双亲节点的指针即可；若叱节点只有左子树或只有右子树，此 时只要令左子树或右子树直接成为其双亲节点粒的左子树即可；若和节点的 左子树和右子树均不为空，其一可以令切的左子树为粒的左子树，而叱的右 子树为*s的右子树，其二可以令切的直接前驱(或直接后继)替代和，然后 再从

5、二义排序树中删去它的直接前驱(或直接后继)。在二义排序树中删除一 个节点的算法为voidDeleteData(bstree&t, keytype key)若二义排序树t中存在关键字等于key的数据元素，则删除该数据元素节点, 并返回TRUE,否则返回FALSEo3.3.4 4插入模块二义排序树是一种动态树表，其特点是树的结构通常不是一次生成的，而 是在查找的过程中，当树中不存在关键字等于给定值得节点时在进行插入。 新插入的节点一定是一个新添加的叶子节点，并且是查找不成功时查找路径 上访问的最后一个节点的左孩子或右孩子的节点。一个无序系列可以通过构 造一棵二义排序树而变成一个有序系列，构造树的过

6、程即为对无序系列进行 排序的过程，并且每次插入的节点都是二义排序树上新的叶子节点，则在进 行插入操作时，不必移动其他节点，仅需改变某个节点的指针由空变为非空 即可。二叉排序树的插入算法为bstreelnsertBST(bstreet, intkey, nametypename, double grade)若二义排序树中不存在关键字等于key的数据元素时，插入元素并返回TRUEo3.3. 5 5査找模块二义排序树乂称二义查找树，当二义排序树不为空时，首先将给定的值和 根节点的关键字比较，若相等则查找成功，否则将依据给定的值和根节点关 键字之间的大小关系，分别在左子树或右子树上继续进行查找。为此定

7、义一 个二叉排序树的查找算法为bstnode *SearchBST(bstreet,keytype key)在根指针t所指向的二义排序树中查找关键字等于key的数据元素，如成功, 返回指向该元素节点的指针，否则返回空指针。3.3. 6 6二叉排序树的遍历先序遍历也叫做先根遍历。首先访问根结点然后遍历左子树，最后遍历 右子树。在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后 遍历右子树，如果二义树为空则返回。其实过程为：先遍历左子树 root-left-left-left. . . -null,由于是先序遍历，因此一遇到节点， 便需要立即访问；山于一直走到最左边后，需要逐步返回到父节点

8、访问右节 点，因此必须有一个措施能够对节点序列回溯。其一可以用栈记忆在访问途 中将依次遇到的节点保存下来。根据栈的先进后出、后进先出的特点特点。 则可以用栈保存。每次都将遇到的节点压入栈，当左子树遍历完毕后从栈中 弹出最后一个访问的节点，然后访问其右子树。基本算法思想：1先访问根节点，将根节点入栈2.重复执行两大步骤：如果该节点左孩子存在，则访问该左孩子节点，并将 其指针入栈。重复以上操作，直到节点的左孩子不存在。将栈顶的元素， 即其指针出栈，回到父节点，如果该指针节点的右孩子存在，则将该指针 指向的右孩子节点重复执行以上步骤，直到栈为空为止。操作函数为 void x_print (Tree

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

10、复执行此操作，直到节点左孩子节点为空。取栈顶元素，并赋值给P,如果P 的右孩子为空或P的右孩子等于q(即如果P的右孩子已访问，则访问根节点, 即P指向的节点，并用q来记录刚刚访问的节点的指针)，若P有右孩子，且 右孩子没有别访问过，则p=p-rchildo操作函数为 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#include #include #includ

11、e include using namespace std;typedef stringnametype;typedef unsigned long keytype;typedefstruct node/结点的结构体keytype key;nametype name;int grade;struct node *lchild, *rchild;Jbstnode;typedefbstnode *bstree;/栈的总义/typedefstructbstree *base;bstree *top; intstacksize;Sqstack;intlnitStack (Sqstack&s)/sbas

12、e=(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(stop二二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;whi

13、le(p ! (s top=s base)if (p)Push(s, p);coutp-key/x tsetw (20); coutp-name，/t/setw(20);coutp-gradelchild;elsePop(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;elsePop(s, p)； coutp-key/x tsetw (20); coutp-na

14、me，/t/setw(20); coutp-graderchild;voidh_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;非递归后序遍历*/ elsep=*(s top-1);if(p-rchild=q)Pop(s, q) : p=NULL;coutq-key/zt/name/，t?/grade/，tyendl; elsep=p-rchild;q=NULL;递归査找二叉树/*_归査找，若找到就返回指向该结点的

15、指针，否则返回空一-*/bstnode *SearchBST(bstreet, keytype key) if(t=NULL key二二t-key)return t;if(keykey)returnSearchBST(t-lchild , key);elsereturnSearchBST(t-rchild , key);/ -给定学生信息插入到二叉树中 -/bstreelnsertBST (bstreet, intkey, nametypename, double grade)bstreep, q;if(t=NULL)t=new bstnode0; t-key=key;t-name=name;

16、t-grade=grade;t-lch订d二t-rchild二NULL;elsep=t;while (p)q 二P；if (p-keykey)p二q-lchild;else if (p-keyrchild;elsecoutendl;cout/z树中已有该节点:/keyendl;coutendl;return t;p=new bstnode 0;p-key=key;p-name=name;p-grade=grade;p-lchild=p-rchild=NULL;if(q-keykey)q-lchild=p;elseq-rchild=p;return t;/ -二叉树排序树的构建 -/bstree

17、CreatTree 0bstree t=NULL;keytype key;nametype name;double grade;printf (，?n*本系统由二胡科技所有成员公同组建！ *nnnz/); printf (w请输入-学号 -姓名 -成绩 -(输入0时结束)：n);cinkey;if(key=0)return t;cinname;cingrade;while(key)t=InsertBST(t, key, name, grade);printfC请输入一-学号-一姓名一-成绩-一(输入0时结朿)：n); cinkey;if(key=O)break;cinname;cingrade

18、;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;elseQ=P；s=p-lchild;while(s-rchild)q二 s;s=s-rchild;p-name=s-name; 辻(q!=p)q-rchild=s-lchiId; elseq-lch订d二s-lchild; delete s; voidDeleteData(bstree&t, keytype key)if (! t

19、) printfC没有该信息，请重新输入！ n); cinkey;DeleteData(t, key);elseif (t-key=key)Delete (t);printf (w删除成功！ n);else if(t-keykey) DeleteData(t-lchild, key); elseDeleteData(t-rchild, key);/二叉树的深度intTreeDepth (bstree t)intleft, right, max;if(t!二NULL) left=TreeDepth(t-lchild); right=TreeDepth(t-rchild); max=leftrig

20、ht?left:right;return max+1;elsereturn 0;/树状输出二叉树 voidPrintTree (bstreet,int layer) int k; if(t=NULL) return ;PrintTree(t-rchild, layer+1); for(k=0:layer:k+)cout/z ”；coutt-ke5r，z n/z;PrintTree(t-lchild, layer+1);/-主函数测试-/int mainOint d;/system(cls);system(，zColor 2f;keytype key;bstree t=NULL;t=CreatT

21、ree();d=TreeDepth(t);printf C二叉排序树的树形表示如下n);PrintTree (t, d);char choose;nametype name;bstree p;double grade;printf(” n);printf (- -请输入你要选择的操作-)；printfC-)printfC)printfCIIa插入信息llnz/)printfCIIb删除信息llnz0printfCIIc查询信息llnz0printfCIId修改信息H)printfCII0退出lln，z)printfCIIe对二叉排序树进行非递归遍历lln，z)printfC-IIW)print

22、fC-AnOprintf (，zn/z);printf（z/需要选择的操作为：“）;cinchoose;coutendl;while(choose)switch(choose)case a :printf (”输入需要插入的学生信息信息(学号为0时结束).n); printfC请输入-一学号-一姓名一-成绩-一(输入0时结束)：n); cinkey;辻(key=0) PrintTree(t, d);printf(z，n*插入信息结束！ ”)； break;cinname;cingrade;while(key)t=InsertBST(t, key, name, grade);printf (谙输

23、入-学号-一姓名一-成绩一-(输入0时结朿)：n); cinkey;if(key=0)printf (插入信息结束!);break;cinname;cingrade;break;case b :printf (请输入要删除信息学生的学号：n)； cinkey;DeleteData(t, key); d=TreeDepth(t);printf (删除结点后二叉树的树形显示如下n);PrintTreeU, d);break;case c :cout请输入要查询学生的学号：endl; cinkey;p=SearchBST(t, key);辻(p=NULL)cout?，无査询的关键字：keyendl;

24、elsecout成绩tsetw(20)姓名tsetw(20)key，zt，zsetw(20);coutp-nameztgradeendl;break;case d，:printf(”请输入要修改学生的学号：n);cinkey;p=SearchBST(t, key);if(p=NULL)cout无你所要修改的关键字：name;printf (n谙输入修改的成绩：)；cingrade;p-name=name;p-grade=grade;printf (”n 修改成功! n);break;case e :printf(”没有任何信息，请先输入信息！ ”)；elsecout学号tsetw(20) 姓名tsetw(20)成绩endl;printf (-非递归先序遍历 -n);printf Cn9;x_print(t);printf (”-非递归中序遍历 -n);printf(n);z_print(t);printf (，?-非递归后序遍历 -n);printf(n);h_print(t);bre