二叉排序树及平衡二叉树.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.