二叉排序树及平衡二叉树.docx

编号，学号：课程设计教学院计克机学院课程名称数据结构及算法设计Bf1.目二叉排序树及平衡二叉排序树专业计算机科学及技术一班级姓名苴处同组人员指导老师2016年12月26日一概述1. 1课程设计的目的1 .理解和驾驭该课程中的有关基本概念，程序设计思想和方法.2 .培育粽合运用所学学问独立完成课题的实力.3 .培育更探究、严遂推理、实事求是、有错必改，用实践来检验理论，全方位考虑问题等科学技术人m应具有的素养.4 .学驭从资料文献、科学试验中获得学问的实力，提高学生从别人阅历中找到解决问题的新途径的悟性,初步培育工程意识和创新实力.5 .本课程是数据结构课程的实践环节。主要目的在于加强学生在课程中学习的相关算法和这些方法的具体应用，使学生进一步驾驭在C或其他语言中应用这些算法的实力。通过课程设计题目的练习，强化学生对所学学问的驾驭及对问题分析和任务定义的理解.另外，数据结构是计肾机科学及技术专业的一门核心专业基础课程，在该专业的课程体系中起着承上启下的作用，学好数据结构对于提高理论认知水平和实践实力仃着极为重要的作用.学习数据结构的最终目的是为了获得求解问题的实力。对于现实世界中的问烟，应当能从中抽象出一个适当的数学模型，该数学模型在计算机内部用相应的数据结构来表示，然后设计一个解此数学模型的算法,再进行编程调试，最终获得问题的解答012课程设计的要求用二叉链表作存储结构，编写程序实现二叉排序树上的基本操作：以回车('n')为输入结束标记,输入数列1.,生成二叉排序树T;对二叉排序树T作中序遍历：计算二叉排序树T的平均杳找长度,输出结果；输入元索X,杳找二叉排序树T,若存在含X的结点,则删除该结点,并作中序遍历；否则输出信息“无结点x”：推断二叉持序树T是否为平衡二叉排序树:再用数列1.,生成平衡二叉排序树BT：对平衡二义树作中序遍历输出；当插入新元素之后,发觉当前的二叉排序树BT不是平衡二义排序树，则马上将它转换成新的平衡.叉排序树BT;当删除元素之后，发觉当前的一叉排序树BT不是平衡二叉排序树,则马上将它转换成新的平衡：叉排序树BT：计算平衡的二叉排序树BT的平均查找长度，输出结果。二总体方案设计用二叉链表作存储结构实现二叉排序树：(1)以回车(,0,)为输入结束标记,输入数列1.,生成一棵二叉排序树T;(2)对二叉排序树T作中序遍历，输出结果：(3)求二叉排序树的平均查找长度：(4)辘入元素k杳找二叉排序树T,若存在含X的结点，则删除该结点,并作中序遍历(执行操作2)：否则输出信息“无x”.(5)推断二叉持序树是不是平衡二叉树：(6)以回车('O')为输入结束标记，输入数列1.,生成一棵平衡二叉树T;(7)对平衡二叉树T作中序遍历，输出结果：<8)在平衡二叉树中插入新元素,并作中序输出：<9)在平衡二叉树中删除元素,并作中序输出；(10)求平衡二叉树的平均杳找长度：2. 1二叉排序树的建立二又持序树(BinarySortTree)又称二叉查找(搜寻)树(BinarySearchTree).其定义为:二叉排序树或者是空树，或者是满意如下性艇的二叉树：若它的左子树非空,则左子树上全部结点的值均小于根结点的值；若它的右子树非空，则右子树上全部结点的值均大于根结点的值：左、右子树本身又各是一棵二叉排序树。建二叉树的结点至少应当包含三个域，分别存放结点的数据data,左子女结点指针IoftChi1.d和右子女结点指针rightChi1.d.整个二叉树的链表要有一个表头指针,它指向二叉树的根结点,其作用是当作树的访问点从空的二叉排序树起先,经过系列的查找插入操作以后，生成了棵二叉排序树。依据二叉排序树的定义，建立一棵：叉排序树的过程是依据待排序序列元素的先后次序，不断动态生成二叉树的结点，逐个插入到二叉树中。若P为根结点指针,b为当前待插入元素，其过程可以描述为：若为空树(PFi1.),动态生成一个结点，其数据域为当前待插入元素b,左、右指针域为“空”，P指向该结点。若非空树，比较b及根结点数据data<p)假如b<data(p),将b插入左子树中；假如b2da1.a(p),将b插入右子树中：左、右子树的插入方式及一：叉排序树的插入方式相同。不断调用上述的插入过程，直到全部待排序序列均持入后，就形成一棵二叉排序树.由此可见，建立二叉排序树就是多次调用二叉排序树的插入算法(递归调用)。2.2二叉排序树的中序遍历中序遍历二叉树算法的框架是：若二叉树为空,则空操作；否则中序遍历左子树(1.)；访问根结点(V):中序遍历右子树(R)。中序遍历二叉树也采纳递归函数的方式，先访问左子树,然后访问根结点，最终访问右子树。直至全部的结点都被访问完毕.2. 3二叉排序树中元素的查找在二叉排序树上进行查找，是个从根结点起先，沿某个分支逐层向下进行比较判等的过程,它可以是一个递归的过程,假设我们想要在二叉排序树中查找关键码为X的元素，直找过程从根结点起先。假如根指针为NU1.1.则隹找不胜利：否则用给定值X及根结点的关键码进行比较：假如给定值等于根结点的关键码，则杳找胜利，返回杳找胜利的信息，并报告杳找到的结点地址.假如给定值小于根结点的关键码，则接着递归查找根结点的左子树：否则，递归搜寻根结点的右子树.2.4二叉排序树中元索的删除对于一叉排序树，删去树上的一个结点相当于删去有序序列中的一个记录，只要在删除某个结点之后照旧保持二叉排序树的特性即可。假设在二叉排序树上被删除结点为*P(指向结点的指针是P，其双亲结点为*(结点指针为f),且不失一般性,可设*P是*1的左孩子，U若*p结点为叶子结点，即P和1均为空，只需修改其双亲结点指针即可。2。若*p结点只有左子树或者只有右子树，只要令左子树或右子树干脆成为其双亲结点即可.3。若左子树和右子树都不为空，令*p的干脆前驱替代*p，然后从二叉排序树中删除它的干脆前驱，即可。2. 5二叉排序树的平均查找长度计翼二叉排序树的平均查找长度时，采纳类似中序遍历的递归方式，用S记录总查找长度.j记录每个结点的查找长度,S置初值为0,采纳累加的方式最终得到总查找长度S.平均查找长度就等于si(i为树中结点的总个数.假设在含有n(n>=D个关键字的序列中，i个关键字小于第一个关键字，n-i-1.个关键字大于第一个关键字，则由此构造而得的二叉排序树在n个记录的查找概率相等的状况卜.，其平均查找长度为：AS1.(n,i)1.+i*(P(i)+1.)+(n-iI)(P(11-i-1.)+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分别为左、右子树的深度.当且仅当(DT1.、TR都是平衡二叉树；Ih1.-hrIWI：时，则T是平衡二叉树.构造平衡二叉排序树的过程中，每当插入个结点时，首先检查是否因插入而破坏了树的平衡性，假如是因插入结点而破坏了树的平衡性，则找出其中最小不平衡子树，在保持排序树将性的前提下，调整最小不平衡子树中各结点之间的连接关系，以达到新的平衡.最小不平衡子树：以离插入结点最近、旦平衡因子肯定值大于1的结点作根结点的子树.假设二叉排序树的最小不平衡子树的根结点为A,则调整该子树的规律可归纳为下列四种状况：G(1) 1.1.型:新结点X插在A的左孩子的左子树里。调整方法见上图。图中以B为轴心,将A结点从B的右上方转到B的右下恻，使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 中序输出平衡二叉树右遍历的定义可知，中序遍历二叉树的递规竟法可以定义为：若二叉树为空，则空操作：否则中序遍历左子树,访问根结点，中序遍历右子树。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在平衡二叉排序树上刷除一个元素割除结点过程及插入结点的操作类似，基本过程是：平衡二义树一?找到要删除的结点-一今删除一个结点一一»变成二叉树一一今旋转今变回平衡二叉树“具体过程将具体设计中的代码。2.10求平衡二叉树的平均查找长度计算平衡二叉排序树的平均查找长度时，采纳类似中序遍历的递归方式，用S记录总杳找长度,j记录每个结点的查找长度，S置初值为0,采纳累加的方式最终得到总查找长度s.平均杳找长度就等于s/i（i为树中结点的总个数）。A.运用的头文件# inc1.ude<s1.d1.ib«h># inc1.ude<s1.dio.h>B.常量定义# define1.H+1/左高# defineEH0等高# defineRH1右高# defineTRUE1# 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；/*分别指向左右孩子的指针*/BSTNode,*BSTree;/*同时声明一个BSTNode和一个指针类型的*BSTree*/三具体设计3.1功能设计，输入数列时，生成平衡二叉树函数原型：BSTreeBui1.dAV1.Tree<BSTreet)建立平衡二叉树函数函数功能及思想说明：如何使构成的二叉排序树成为平衡树呢？先看个具体的例子.假设表中关键字序列为(10,24,30,88,53).空树和1个结点10的树明显都是平衡的二叉树.在插入24之后依是平衡的，只是根结点的平衡因子BF由。变为一1;在接着插入30之后，由于结点10的BF值由一I变成一2,由此出现不平衡现象.此时好比一根扁担出现一头重一头轻的现象，若能将扁担的支撑点由10改成至24,扁担的两头就平衡了。由此可以对树左个向左逆时针“旋转”的操作，令结点24为根，而结点10为它的左子树.此时,结点10和24的平衡因子都为0,而且他保持二叉樗序树的特性。在接着插入88和53之后，由于结点30的BF值由一1变成一2,排序树中出现了新的不平衡现缴，须要调整，当此时由于结点53插在结点88结点的左子树上，因此不能和上作简洁调貉。对于以结点30为根的子树来说，即要保持二叉排序树的特性，又要平衡.则必需以53作为根结点，而使37为它的左子树的根，88成为它的左子树的根。这好比对树作了两次“旋转”操作一一先向右顺时针,后向左逆时针(见图3-1相维插入90和53；(g)第一次向右顺时针度转：（三）其次次向左逆时针旋转平衡函数源代码：BSTreeBuiIdAV1.Tree(BSTreet)/建立平衡二叉树函数intNodcVa1.ue;if(t!-N1.-1.D/假如传入根结点不为空，则树己构建过，退出函数(PrinIfr二叉平衡树已经创建!VT);returnNU1.1.;根结点为空则起先构建Printfr请输入结点值，每个数以空格分开，以0结束：")：scanf(%d",OodeVa1.ue);whi1.e(NodeVa1.ue)插入任何不为0的整数值BSTreeNodeCreatNode(NodeVa1.ue)；假如根为空,则将此结点设身为根结点，否则将此结点作为非根结点插入if(t=NU1.1.)t二Node;e1.set=InsertV1.(t,NodeVa1.ue);scanf(*%d-,&NodeVa1.ue);获得用户输入的新值)Printf("输入完成八n”)；returnt;)BSTreeCreatMode(intNodeVa1.ue)/建立新结点(BSTreeNode;Node=(BSTrce)ma11.oc(sizeof(BSTree)：申请结点空间Node>data-NodeVa1.ue;结点数据域存放NOdeYa1.UeNode->bf=0;结点初始值为0Node->1.eftchi1.d=NU1.1.;Node->rightchi1.d=NU1.1.;returnNode;3. 2功能设计：插入新元索之后,保证仍为平衡二叉树原型函数：BSTreeInsertAV1.(BSTreeT,inie)函数功能及思想说明：在平衡的二叉排序BBST上插入一个新的数据元素C的递归算法可描述如下：<1)若BBST为空树,则插入个数据元素为e的新结点作为BBST的根结点，树的深度增加1;(2)若e的关键字和BBST的根结点的关键字相等，则不进行插入：<3)若e的关键字小于BBST的根结点的关键字，而且在BBST的左子树中不存在和e有相同关键字的结点，则将e插入在BBST的左子树上,并且当插入之后的左子树深度增加(+1),分别就下列不同状况处理之：BBST的根结点的平衡因子为-1(右子树的深度大于左子树的深度)：则将根结点的平衡因子更改为0,BBST的深度不变；BBST的根结点的平衡因子为0(左、右子树的深度相等)：则将根结点的平衡因子更改为1.BBST的深度增加1；BBST的根结点的平衡因子为I(左子树的深度大于右子树的深度)：若BBST的左子树根结点的平衡因子为1.则需进行单向右旋转平衡处理，并且在右旋转处理之后，将根结点和其右子树根结点的平衡因子更改为0,树的深度不变；若BBST的左子树根结点的平衡因子为一1,则需进行先向左、后向右的双向旋转平衡处理,并且在旋转处理之后，修改根结点和其左、右子树根结点的平衡因了，树的深度不变：（4）若C的关键字大于BBST的根结点的关键字,而且在BBST的右子网中不存在和C有相同关键字的结点，则将e插入在BBST的右子树上,并且当插之后的右子树深度增加什1）时，分别就不同的状况处理之.4种插入中，（1）和（3）对称，（2）和（4）对称.旋转操作的正确性简洁由“保持二叉排序树的特性：中序遍历所得关键字序列自小到大有序”证明之,当平衡二叉树因插入或者删除结点而失去平衡时，仅需对最小不平衡了M进行平衡旋转处理即可，因为经过旋转处理之后的子树深度和插入或删除之前相同，因而不影响插入或删除路径上全部祖先结点的平衡.主要部分的具体流程图（右平衡）：以指针T所指结点为根的二叉树作右平衡旋转处理函数源代码：/对以P为根的树作右旋处理，处理之P指向新的树根结点即旋转处理之前的左子树根结BSTreeR_Rotate(BSTrecp)(BSTNode*Ics/声明BSTNode*临时变量1.c=p->Ief1.chi1.d:/1C指向的*p的左子树根结点p-)Ieftchi1.d=Ic>rightchi1.d;/1C的右子树挂接为*p的左子树Ic>rightchi1.d=p;P=Ic;p1.fi向新的根结点returnp：返回新的根结点/对以P为根的树作左旋处理,处理之P指向新的树根结点即旋转处理之前的右子树根结点BSTree1._ROtatQ(BSTreep)(BSTNode*rc；声明BSTNOde*临时变星rc-p)rightchi1.d；/rc指向的*p的右子树根结点P)righ1.chi1.d=rc>1.eftchi1.<1.;/rc的左子树挂接为*p的右子树rc->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->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:T>bf=EH;1.c->bf=1.H:break;)rd>bf=EH：T-Xeftchi1.d=1.Rotate(T-XeftchiId):对*T的左核子做左旋平衡处理T=R_Rotate(T);/对*T做右旋处理returnT；)对以指针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.<i=rc->1.eftchi1.d：Id指向*T的右孩子的左子树根switch(1.d-)bf)/修改*T及其右孩子的平衡因子caseUI：T-)bf=1.H;rc->bf=EH;break;caseEH:T-)bf=rc->bf=EH:break：caseRH:T>bf=EH;rc>bf=RH:break；)Id>bf=EH:T->rightchiId=RRotate(T->rightchiId)：/5*T的右孩子做右旋平衡处理T=1.Rotate(T)；对*T做左旋处理)returnT；)若在平衡的二叉排序树T中不存在和e有相同关键字的结点,则插入个数据元素为。的新结点，/并返回插入后所建成的平衡二叉排序树，否则返回N1.1.1./若因插入而使二叉数失去平衡，则作平衡旋转处理,布尔变量IaIIer反映T长高及否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.eftchi1.d,e)；/插入到左子树且左子树长高if(P)(T)Ieftchi1.d=P;if(ta1.1.er)(switch(T>bf)检查*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-)rightchi1.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主菜单输出全部功能界面EMW8Qtg*度槿制DbgBffW叫Q丽XX*XXXXXXWXXXxXXXXXXXXXXXXXXXXXXXXMXXXXMMXXX1：输入数列，生成二叉排序树XX2:中序输出二叉排序树XX3：求二叉排序树的平均看我长度XXH：输入元素，若存在则删除XX5：判断二叉排序树是否为平衡二叉树XX6:输入数列生成平衡二叉排序树XX7:中序输出平衡二叉树*X8:在平衡二叉树中插入新元素XX9:在平衡二叉树中删除元素XX10:求平衡二叉树的平均杳找长度MXXXXMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM口请输入选择序号:4. 1输入数列12、6、9、18、12、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：