《二叉排序树及平衡二叉树.docx》由会员分享，可在线阅读，更多相关《二叉排序树及平衡二叉树.docx（21页珍藏版）》请在课桌文档上搜索。
1、编号，学号：课程设计教学院计克机学院课程名称数据结构及算法设计Bf1.目二叉排序树及平衡二叉排序树专业计算机科学及技术一班级姓名苴处同组人员指导老师2016年12月26日一概述1. 1课程设计的目的1 .理解和驾驭该课程中的有关基本概念，程序设计思想和方法.2 .培育粽合运用所学学问独立完成课题的实力.3 .培育更探究、严遂推理、实事求是、有错必改，用实践来检验理论，全方位考虑问题等科学技术人m应具有的素养.4 .学驭从资料文献、科学试验中获得学问的实力，提高学生从别人阅历中找到解决问题的新途径的悟性,初步培育工程意识和创新实力.5 .本课程是数据结构课程的实践环节。主要目的在于加强学生在课程
2、中学习的相关算法和这些方法的具体应用，使学生进一步驾驭在C或其他语言中应用这些算法的实力。通过课程设计题目的练习，强化学生对所学学问的驾驭及对问题分析和任务定义的理解.另外，数据结构是计肾机科学及技术专业的一门核心专业基础课程，在该专业的课程体系中起着承上启下的作用，学好数据结构对于提高理论认知水平和实践实力仃着极为重要的作用.学习数据结构的最终目的是为了获得求解问题的实力。对于现实世界中的问烟，应当能从中抽象出一个适当的数学模型，该数学模型在计算机内部用相应的数据结构来表示，然后设计一个解此数学模型的算法,再进行编程调试，最终获得问题的解答012课程设计的要求用二叉链表作存储结构，编写程序实
3、现二叉排序树上的基本操作：以回车(n)为输入结束标记,输入数列1.,生成二叉排序树T;对二叉排序树T作中序遍历：计算二叉排序树T的平均杳找长度,输出结果；输入元索X,杳找二叉排序树T,若存在含X的结点,则删除该结点,并作中序遍历；否则输出信息“无结点x”：推断二叉持序树T是否为平衡二叉排序树:再用数列1.,生成平衡二叉排序树BT：对平衡二义树作中序遍历输出；当插入新元素之后,发觉当前的二叉排序树BT不是平衡二义排序树，则马上将它转换成新的平衡.叉排序树BT;当删除元素之后，发觉当前的一叉排序树BT不是平衡二叉排序树,则马上将它转换成新的平衡：叉排序树BT：计算平衡的二叉排序树BT的平均查找长度
4、，输出结果。二总体方案设计用二叉链表作存储结构实现二叉排序树：(1)以回车(,0,)为输入结束标记,输入数列1.,生成一棵二叉排序树T;(2)对二叉排序树T作中序遍历，输出结果：(3)求二叉排序树的平均查找长度：(4)辘入元素k杳找二叉排序树T,若存在含X的结点，则删除该结点,并作中序遍历(执行操作2)：否则输出信息“无x”.(5)推断二叉持序树是不是平衡二叉树：(6)以回车(O)为输入结束标记，输入数列1.,生成一棵平衡二叉树T;(7)对平衡二叉树T作中序遍历，输出结果：8)在平衡二叉树中插入新元素,并作中序输出：9)在平衡二叉树中删除元素,并作中序输出；(10)求平衡二叉树的平均杳找长度：
5、2. 1二叉排序树的建立二又持序树(BinarySortTree)又称二叉查找(搜寻)树(BinarySearchTree).其定义为:二叉排序树或者是空树，或者是满意如下性艇的二叉树：若它的左子树非空,则左子树上全部结点的值均小于根结点的值；若它的右子树非空，则右子树上全部结点的值均大于根结点的值：左、右子树本身又各是一棵二叉排序树。建二叉树的结点至少应当包含三个域，分别存放结点的数据data,左子女结点指针IoftChi1.d和右子女结点指针rightChi1.d.整个二叉树的链表要有一个表头指针,它指向二叉树的根结点,其作用是当作树的访问点从空的二叉排序树起先,经过系列的查找插入操作以后
6、，生成了棵二叉排序树。依据二叉排序树的定义，建立一棵：叉排序树的过程是依据待排序序列元素的先后次序，不断动态生成二叉树的结点，逐个插入到二叉树中。若P为根结点指针,b为当前待插入元素，其过程可以描述为：若为空树(PFi1.),动态生成一个结点，其数据域为当前待插入元素b,左、右指针域为“空”，P指向该结点。若非空树，比较b及根结点数据datap)假如b=D个关键字的序列中，i个关键字小于第一个关键字，n-i-1.个关键字大于第一个关键字，则由此构造而得的二叉排序树在n个记录的查找概率相等的状况卜.，其平均查找长度为：AS1.(n,i)1.+i*(P(i)+1.)+(n-iI)(P(11-i-1
7、.)+1)n其中P(i)为含有i个结点的二叉排序树的平均查找长度，则P(i)+1为查找左子树中每个关键字时所用比较次数的平均值,P(niT)1为查找右子树中每个关键字时所用比较次数的平均值。又假设表中n个关健字的排列是“随机”的，即任一个关键字在序列中将是第1个,或第2个，,或第n个的概率相同，则可对上式从i等于0至n-1取平均值。最终会推导出：当n=2时，S1.(n)(=2(1.+1.n)1.n(n)由此可见，在随机的状况下，二叉排序树的平均查找长度和1.og(n)是等数垃级的.2.6平衡二叉树(AV1.)若T是一棵非空二叉树，其左、右子树分别为T1.和TR,令h1.和hr分别为左、右子树的
8、深度.当且仅当(DT1.、TR都是平衡二叉树；Ih1.-hrIWI：时，则T是平衡二叉树.构造平衡二叉排序树的过程中，每当插入个结点时，首先检查是否因插入而破坏了树的平衡性，假如是因插入结点而破坏了树的平衡性，则找出其中最小不平衡子树，在保持排序树将性的前提下，调整最小不平衡子树中各结点之间的连接关系，以达到新的平衡.最小不平衡子树：以离插入结点最近、旦平衡因子肯定值大于1的结点作根结点的子树.假设二叉排序树的最小不平衡子树的根结点为A,则调整该子树的规律可归纳为下列四种状况：G(1) 1.1.型:新结点X插在A的左孩子的左子树里。调整方法见上图。图中以B为轴心,将A结点从B的右上方转到B的右
9、下恻，使A成为B的右孩子。新结点X插在A的右孩子的右子树里.调整方法见上图。图中以B为轴心,将A结点从B的左上方转到B的左FWh使A成为B的左孩子。（3） 1.R型:新结点X插在A的左孩了的右子树里.调整方法见图15.分为两步进行:第步以X为轴心，将B从X的左上方转到X的左下侧，使B成为X的左孩子，X成为A的左孩子。其次步跟1.1.型样处理（应以X为轴心）。（4） R1.型：新结点X插在的右孩子的左子树里。调整方法见上图。分为两步进行：第一步以X为轴心,将B从X的右上方转到X的右下恻,使B成为X的右孩子，X成为A的右孩了%其次步跟RR型一样处理（应以X为轴心）2.7 中序输出平衡二叉树右遍历的
10、定义可知，中序遍历二叉树的递规竟法可以定义为：若二叉树为空，则空操作：否则中序遍历左子树,访问根结点，中序遍历右子树。2.8 在平衡二叉排序树上插入一个新元素1 .若BBST为空树，则插入一个数据元素为e的新结点作为BBST的根结点,树的深度增加h2 .若e的关键字和BBST的根结点的关键字相等，则不进行插入：3 .若e的关键字小于BBST的根结点的关键字，而I1.在BBST的左子树中不存在和e有相同关键字的结点，则将e插入在BBST的左子树上。4。若e的关键字大于BBST的根结点的关键字，而且在BBST的右子树中不存在和e相同关键字的结点，则将e插入在BBST的右子树上2. 9在平衡二叉排序
11、树上刷除一个元素割除结点过程及插入结点的操作类似，基本过程是：平衡二义树一?找到要删除的结点-一今删除一个结点一一变成二叉树一一今旋转今变回平衡二叉树“具体过程将具体设计中的代码。2.10求平衡二叉树的平均查找长度计算平衡二叉排序树的平均查找长度时，采纳类似中序遍历的递归方式，用S记录总杳找长度,j记录每个结点的查找长度，S置初值为0,采纳累加的方式最终得到总查找长度s.平均杳找长度就等于s/i（i为树中结点的总个数）。A.运用的头文件# inc1.ude# inc1.udeB.常量定义# define1.H+1/左高# defineEH0等高# defineRH1右高# defineTRUE
12、1# defineFA1.SE0# defineEQ(a,b)(（八）=(b)# define1.T(a,b)(（八）(b)# define1.Q(a,b)(（八）=(b)C.全局变量定义intIa1.1.er=O;*IU1.Ier反映T长高及否*/intShor1.er=O:*shor1.er反映T变矮及否*/D.数据结构定义/*依据平衡二义树特点可以定义平衡二叉树的存储结构*/*二叉排序树的类型定义*/IypedefstructBSTNode(intdata;/*结点值*/intbf：/*结点的平衡因子*/structBSTNode*1.eftchi1.d,*rightchiId；/*分别
13、指向左右孩子的指针*/BSTNode,*BSTree;/*同时声明一个BSTNode和一个指针类型的*BSTree*/三具体设计3.1功能设计，输入数列时，生成平衡二叉树函数原型：BSTreeBui1.dAV1.Treedata-NodeVa1.ue;结点数据域存放NOdeYa1.UeNode-bf=0;结点初始值为0Node-1.eftchi1.d=NU1.1.;Node-rightchi1.d=NU1.1.;returnNode;3. 2功能设计：插入新元索之后,保证仍为平衡二叉树原型函数：BSTreeInsertAV1.(BSTreeT,inie)函数功能及思想说明：在平衡的二叉排序BB
14、ST上插入一个新的数据元素C的递归算法可描述如下：1)若BBST为空树,则插入个数据元素为e的新结点作为BBST的根结点，树的深度增加1;(2)若e的关键字和BBST的根结点的关键字相等，则不进行插入：Ief1.chi1.d:/1C指向的*p的左子树根结点p-)Ieftchi1.d=Icrightchi1.d;/1C的右子树挂接为*p的左子树Icrightchi1.d=p;P=Ic;p1.fi向新的根结点returnp：返回新的根结点/对以P为根的树作左旋处理,处理之P指向新的树根结点即旋转处理之前的右子树根结点BSTree1._ROtatQ(BSTreep)(BSTNode*rc；声明BST
15、NOde*临时变星rc-p)rightchi1.d；/rc指向的*p的右子树根结点P)righ1.chi1.d=rc1.eftchi1.Ieftchi1.d=P;P=rc：P指向新的根结点returnp：/返回新的根结点对以指针T所指结点为根的二叉树作左平衡旋转处理，本算法结束时指针T指向新的根结点BSTNode*1.c,*rd;1.c=T-)1.eftchi1.d:switch(1.c-)bf)(CaSe1.U:旋处理BSTree1.eftBa1.anCe(BSTreeT)/Ic指向*T的左子树根结点/检杳*T的左子树平衡度，并做相应的平衡处理新结点插入在*T的左孩子的左子树上，要做单右T-
16、bf=1.c-bf=E1.hT=RRotated);break;caseRH：/新结点插入在*T的左孩子的右子树上，要做双旋处rd=1.c-)rightchi1.d:/rd指向*T的左孩子的右子树根SWiICh(rd-bf)修改*T及其左孩子的平衡因子case1.H:T-bf=RH;1.c-bf=EH;break：caseEH:T-)bf=1.c-bf=EH;break;caseRH:Tbf=EH;1.c-bf=1.H:break;)rdbf=EH：T-Xeftchi1.d=1.Rotate(T-XeftchiId):对*T的左核子做左旋平衡处理T=R_Rotate(T);/对*T做右旋处理r
17、eturnT；)对以指针T所指结点为根的二叉树作右平衡旋转处理，本算法结束时指针T指向新的根结点BSTreeRightBa1.ance(BSTreeT)BSTreerc.Id;rc=T-rightchi1.d：rc指向*T的右子树根结点switch(rc-)bf)检查*T的右子树平衡度,并做相应的平衡处理CaSeRH:新结点插入在*T的右孩子的右子树上，要做单右旋处理T-bf=rc-bf=EH:T=1.Rotate(T)；break：case1.H:新结点插入在*T的右孩子的左子树匕要做双旋处理1.1.eftchi1.d：Id指向*T的右孩子的左子树根switch(1.d-)bf)/修改*T及
18、其右孩子的平衡因子caseUI：T-)bf=1.H;rc-bf=EH;break;caseEH:T-)bf=rc-bf=EH:break：caseRH:Tbf=EH;rcbf=RH:break；)Idbf=EH:T-rightchiId=RRotate(T-rightchiId)：/5*T的右孩子做右旋平衡处理T=1.Rotate(T)；对*T做左旋处理)returnT；)若在平衡的二叉排序树T中不存在和e有相同关键字的结点,则插入个数据元素为。的新结点，/并返回插入后所建成的平衡二叉排序树，否则返回N1.1.1./若因插入而使二叉数失去平衡，则作平衡旋转处理,布尔变量IaIIer反映T长高及
19、否BSTreeInsertAV1.(BSTroeT,inte)(BSTreep；插入新结点，树长高置taiIer为TRUEif(!T)(T=(BSTree)ma1.1.oc(si2e0f(BSTNode)：T-data=e;T-1.cftchi1.d=T-rightchiId=NU1.1.:T-bf=EH;此时平衡因子为0,EH等高.taiIer=TRUE;树的深度增加)e1.se(树中存在和e有相同关健字的结点则不再插入if(e=T-)data)Ia1.1.er=FA1.SE;returnNU1.1.：值小于则接若在树的左子树中搜寻if(e(T-data)(P=InscrtAV1.(T-)1
20、.eftchi1.d,e)；/插入到左子树且左子树长高if(P)(T)Ieftchi1.d=P;if(ta1.1.er)(switch(Tbf)检查*T的平衡度(case1.H：原本左子树比右子树高，须要做左平衡处理T=1.eftBa1.ance(T);taiIer=FA1.SE;break;caseEH：原本左、右子树同高，现因左子树争高而使树增高T-bf=1.H:taiIer=TRUE5break；caseRH:/原本右子树比左子树高，现在左右子树等裔T-bf=EH;taiIer=FA1.SE;break；)接着在*T的右子树中搜寻e1.se(j=Inser1.AV1.(T-)rightc
21、hi1.d,e)；插入到右子树且使右子树长高if(p)(T-rightchi1.d=p;if(ta1.1.er)(switch(T-bf)/检查*T的平衡度(CaSe1.H：原本左子树比右子树高，现在左右子树等高T-bf=EH;U1.1.er=KA1.SE;break；caseEH：caseRH:原本左、右子树同高,现因右子树增高而使树增高T-bf=RH;taiIer=TRUE:break;原本右子树比左子树裔，须要做右平衡处理T=Righ1.Ba1.ance(T);taiIer=FA1.SE;break;)returnT；四程序的调试及运行结果说明4。运行的主菜单为：如图4-0主菜单输出全部
22、功能界面EMW8Qtg*度槿制DbgBffW叫Q丽XX*XXXXXXWXXXxXXXXXXXXXXXXXXXXXXXXMXXXXMMXXX1：输入数列，生成二叉排序树XX2:中序输出二叉排序树XX3：求二叉排序树的平均看我长度XXH：输入元素，若存在则删除XX5：判断二叉排序树是否为平衡二叉树XX6:输入数列生成平衡二叉排序树XX7:中序输出平衡二叉树*X8:在平衡二叉树中插入新元素XX9:在平衡二叉树中删除元素XX10:求平衡二叉树的平均杳找长度MXXXXMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM口请输入选择序号:4. 1输入数列12、6、9、18、1
23、2、25、16生成二叉排序树:如图4T输入数列生成二叉排序树R请输入选择序号：1建立二叉排序树请输入结点值，每个数以空格分开，以e结束:1269181225160输入完成，图4-14. 2中序输诞生成的二.叉排序树：如图4-2将生成的二叉排序树中序输出It请输入选择序号：2中序遍历输出结果为：6912161825图4-24. 3求二叉排序树的平均查找长度:如图4-3求生成的二叉排序树的AS1.请输入选择序号：3二叉排序树的平均查找长度（AS1.）;Iw6图4-34。4推断是不是平衡二叉树：如图44通过检杳平衡因子推断是不是平衡二叉树并请输入选择序号：5。口这是平衡二叉树!图4-44。5删除元素6、9：
