《二叉排序树与平衡二叉树》由会员分享，可在线阅读，更多相关《二叉排序树与平衡二叉树（28页珍藏版）》请在金锄头文库上搜索。
1、编号：学号：课程设计教学院计算机学院课程名称数据结构与算法设计B题 目二叉排序树与平衡二叉排序树专业计算机科学与技术班 级姓名甘全中同组人员指导教师2016年 12月 26 日一概述31.1课程设计的目的31.2课程设计的要求3二总体方案设计42.1二叉排序树的建立42.2二叉排序树的中序遍历52.3二叉排序树中元素的查找52.4二叉排序树中元素的删除62.5二叉排序树的平均查找长度62.6平衡二叉树（AVL） 62.7中序输出平衡二叉树82.8在平衡二叉排序树上插入一个新元素92.9在平衡二叉排序树上删除一个元素92.10求平衡二叉树的平均查找长度9三详细设计113.1功能设计：输入数列时，
2、生成平衡二叉树113.2功能设计：插入新元素之后，保证仍为平衡二叉树13四程序的调试与运行结果说明20五课程设计总结24参考文献25一概述11课程设计的目的1. 理解和掌握该课程中的有关基本概念，程序设计思想和方法。2. 培养综合运用所学知识独立完成课题的能力。3. 培养勇于探索、严谨推理、实事求是、有错必改，用实践来检验理论， 全方位考虑问题等科学技术人员应具有的素质。4. 掌握从资料文献、科学实验中获得知识的能力，提高学生从别人经验中 找到解决问题的新途径的悟性，初步培养工程意识和创新能力。5. 本课程是数据结构课程的实践环节。主要目的在于加强学生在课程中学 习的相关算法和这些方法的具体应
3、用，使学生进一步掌握在C或其他语言中应用 这些算法的能力。通过课程设计题目的练习，强化学生对所学知识的掌握及对问 题分析和任务定义的理解。另外，数据结构是计算机科学与技术专业的一门核心专业基础课程，在该专 业的课程体系中起着承上启下的作用，学好数据结构对于提高理论认知水平和实 践能力有着极为重要的作用。学习数据结构的最终目的是为了获得求解问题的能 力。对于现实世界中的问题，应该能从中抽象出一个适当的数学模型，该数学模 型在计算机内部用相应的数据结构来表示，然后设计一个解此数学模型的算法， 再进行编程调试，最后获得问题的解答。12课程设计的要求用二叉链表作存储结构，编写程序实现二叉排序树上的基本
4、操作：以回车 (n)为输入结束标志，输入数列L,生成二叉排序树T；对二叉排序树T作中序 遍历；计算二叉排序树T的平均查找长度，输出结果；输入元素x,查找二叉排序 树T,若存在含x的结点，则删除该结点，并作中序遍历；否则输出信息“无结点 x”；判断二叉排序树T是否为平衡二叉排序树；再用数列L,生成平衡二叉排序 树BT:对平衡二叉树作中序遍历输出；当插入新元素之后，发现当前的二叉排序 树BT不是平衡二叉排序树，则立即将它转换成新的平衡二叉排序树BT；当删除 元素之后，发现当前的二叉排序树BT不是平衡二叉排序树，则立即将它转换成新 的平衡二叉排序树BT；计算平衡的二叉排序树BT的平均查找长度，输出结
5、果。二总体方案设计用二叉链表作存储结构实现二叉排序树：(1) 以回车(0)为输入结束标志，输入数列L,生成一棵二叉排序树T；(2) 对二叉排序树T作中序遍历，输出结果；(3) 求二叉排序树的平均查找长度；(4) 输入元素x,查找二叉排序树T,若存在含x的结点，则删除该结点，并作中序遍历(执行操作2)；否则输出信息“无x”。(5) 判断二叉排序树是不是平衡二叉树；(6) 以回车(0)为输入结束标志，输入数列L,生成一棵平衡二叉树T；(7) 对平衡二叉树T作中序遍历，输出结果；(8) 在平衡二叉树中插入新元素，并作中序输出；(9) 在平衡二叉树中删除元素，并作中序输出；(10) 求平衡二叉树的平均
6、查找长度；2.1二叉排序树的建立二叉排序树(Binary Sort Tree)又称二叉查找(搜索)树(Binary Search Tree)。其定义为：二叉排序树或者是空树，或者是满足如下性质的二叉树： 若它的左子树非空，则左子树上所有结点的值均小于根结点的值； 若它的右子树非空，则右子树上所有结点的值均大于根结点的值； 左、右子树本身又各是一棵二叉排序树。建二叉树的结点至少应当包含三个域，分别存放结点的数据data，左子女 结点指针leftChild和右子女结点指针rightChildo整个二叉树的链表要有一 个表头指针，它指向二叉树的根结点，其作用是当作树的访问点从空的二叉排序树开始，经过
7、一系列的查找插入操作以后，生成了一棵二叉 排序树。根据二叉排序树的定义，建立一棵二叉排序树的过程是按照待排序序列元素 的先后次序，不断动态生成二叉树的结点，逐个插入到二叉树中。若p为根结点 指针，b为当前待插入元素，其过程可以描述为：若为空树（p=nil）,动态生成一个结点，其数据域为当前待插入元素b,左、 右指针域为“空”，P指向该结点。若非空树，比较b与根结点数据data （p）如果b=1)个关键字的序列中，i个关键字小于第一个关键字，n- i-1个关键字大于第一个关键字，则由此构造而得的二叉排序树在n个记录的查 找概率相等的情况下，其平均查找长度为：ASL(n,i) = 1+i *(P(
8、i)+1) + (n-i-1)(P(n-i-1)+1)/n其中P(i)为含有i个结点的二叉排序树的平均查找长度，则P(i)+1为查找 左子树中每个关键字时所用比较次数的平均值，P (n-i-1) +1为查找右子树中每 个关键字时所用比较次数的平均值。又假设表中n个关键字的排列是“随机”的， 即任一个关键字在序列中将是第1个，或第2个，或第n个的概率相同，则 可对上式从i等于0至n-1取平均值。最终会推导出：当 n=2 时，ASL(n)=2(1 + 1/n)ln(n)由此可见，在随机的情况下，二叉排序树的平均查找长度和log (n)是等数 量级的。2.6平衡二叉树(AVL)若T是一棵非空二叉树，
9、其左、右子树分别为TL和TR ,令hl和hr分 别为左、右子树的深度。当且仅当 TL、TR都是平衡二叉树； 丨 hl hr | 1；时，则T是平衡二叉树。构造平衡二叉排序树的过程中，每当插入一个结点时，首先检查是否因插入而 破坏了树的平衡性，如果是因插入结点而破坏了树的平衡性，则找出其中最小不 平衡子树，在保持排序树特性的前提下，调整最小不平衡子树中各结点之间的连 接关系，以达到新的平衡。最小不平衡子树：以离插入结点最近、且平衡因子绝对值大于1的结点作根结点的子树。假设二叉排序树的最小不平衡子树的根结点为A，则调整该子树的规律可新结点X插在A的左孩子的左子树里。调整方法见上图。图中以B为轴使A
10、成为B的右孩子。新结点X插在A的右孩子的右子树里。调整方法见上图。图中以B为轴心，将A结点从B的左上方转到B的左下侧，使A成为B的左孩子。（3） LR 型：新结点X插在A的左孩子的右子树里。调整方法见图1 5。分为两步 进行：第一步以X为轴心，将B从X的左上方转到X的左下侧，使B成为 X的左孩子，X成为A的左孩子。第二步跟LL型一样处理（应以X为轴 心）。（4） RL 型：新结点X插在A的右孩子的左子树里。调整方法见上图。分为两步进行: 第一步以X为轴心，将B从X的右上方转到X的右下侧，使B成为X的 右孩子，X成为A的右孩子。第二步跟RR型一样处理（应以X为轴心）。27中序输出平衡二叉树右遍历
11、的定义可知，中序遍历二叉树的递规算法可以定义为：若二叉树为空，则空操作；否则中序遍历左子树，访问根结点，中序遍历右子树。2.8在平衡二叉排序树上插入一个新元素1. 若BBST为空树，则插入一个数据元素为e的新结点作为BBST的根结点, 树的深度增加1；2. 若e的关键字和BBST的根结点的关键字相等，则不进行插入；3. 若e的关键字小于BBST的根结点的关键字，而且在BBST的左子树中不存 在和e有相同关键字的结点，则将e插入在BBST的左子树上。4. 若e的关键字大于BBST的根结点的关键字，而且在BBST的右子树中不存 在和e相同关键字的结点，则将e插入在BBST的右子树上2.9在平衡二叉
12、排序树上删除一个元素删除结点过程与插入结点的操作类似，基本过程是：平衡二叉树-T找到要 删除的结点一T删除一个结点一T变成二叉树-弓旋转-弓变回平衡二叉树。具 体过程将详细设计中的代码。2.10求平衡二叉树的平均查找长度计算平衡二叉排序树的平均查找长度时，采用类似中序遍历的递归方式，用 s记录总查找长度，j记录每个结点的查找长度，s置初值为0，采用累加的方式 最终得到总查找长度S。平均查找长度就等于s/i（i为树中结点的总个数）。A. 使用的头文件#include #include B. 常量定义# define LH +1 /左高# define EH 0 /等高# define RH -1 /右高# define TRUE 1# define FALSE 0# define EQ(a,b) (a)=(b)# define L
