二叉排序树与平衡二叉树解读.docx

编 号： 学 号： 201540410126 课 程 设 计 教 学 院 计算机学院 课程名称 数据结构与算法设计B 题 目 二叉排序树与平衡二叉排序树 专 业 计算机科学与技术 班 级 2015级（1）班 姓 名 甘全中 同组人员 指导教师 2016 年 12 月 26 日 目 录 一 概述 2 1.1课程设计的目的 2 1.2课程设计的要求 2 二 总体方案设计 3 2.1二叉排序树的建立 3 2.2二叉排序树的中序遍历 4 2.3二叉排序树中元素的查找 4 2.4二叉排序树中元素的删除 5 2.5二叉排序树的平均查找长度 5 2.6平衡二叉树（AVL） 5 2.7中序输出平衡二叉树 7 2.8在平衡二叉排序树上插入一个新元素 8 2.9在平衡二叉排序树上删除一个元素 8 2.10求平衡二叉树的平均查找长度 8 三 详细设计 9 四 程序的调试与运行结果说明 12 五 课程设计总结 13 参考文献 14 一 概述 1.1课程设计的目的 1．理解和掌握该课程中的有关基本概念，程序设计思想和方法。 2．培养综合运用所学知识独立完成课题的能力。 3．培养勇于探索、严谨推理、实事求是、有错必改，用实践来检验理论，全方位考虑问题等科学技术人员应具有的素质。 4．掌握从资料文献、科学实验中获得知识的能力，提高学生从别人经验中找到解决问题的新途径的悟性，初步培养工程意识和创新能力。 5. 本课程是数据结构课程的实践环节。主要目的在于加强学生在课程中学习的相关算法和这些方法的具体应用，使学生进一步掌握在C或其他语言中应用这些算法的能力。通过课程设计题目的练习，强化学生对所学知识的掌握及对问题分析和任务定义的理解。 另外，数据结构是计算机科学与技术专业的一门核心专业基础课程，在该专业的课程体系中起着承上启下的作用，学好数据结构对于提高理论认知水平和实践能力有着极为重要的作用。学习数据结构的最终目的是为了获得求解问题的能力。对于现实世界中的问题，应该能从中抽象出一个适当的数学模型，该数学模型在计算机内部用相应的数据结构来表示，然后设计一个解此数学模型的算法，再进行编程调试，最后获得问题的解答。 1.2课程设计的要求 用二叉链表作存储结构，编写程序实现二叉排序树上的基本操作：以回车(\n)为输入结束标志,输入数列L,生成二叉排序树T；对二叉排序树T作中序遍历；计算二叉排序树T的平均查找长度,输出结果；输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历；否则输出信息“无结点x”； 判断二叉排序树T是否为平衡二叉排序树；再用数列L,生成平衡二叉排序树BT:对平衡二叉树作中序遍历输出；当插入新元素之后,发现当前的二叉排序树BT不是平衡二叉排序树,则立即将它转换成新的平衡二叉排序树BT；当删除元素之后，发现当前的二叉排序树BT不是平衡二叉排序树,则立即将它转换成新的平衡二叉排序树BT；计算平衡的二叉排序树BT的平均查找长度，输出结果。 二 总体方案设计 用二叉链表作存储结构实现二叉排序树： （1）以回车(0)为输入结束标志,输入数列L，生成一棵二叉排序树T； （2）对二叉排序树T作中序遍历，输出结果； （3）求二叉排序树的平均查找长度； （4）输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历(执行操作2)；否则输出信息“无x”。 （5）判断二叉排序树是不是平衡二叉树； （6）以回车(0)为输入结束标志,输入数列L，生成一棵平衡二叉树T； （7）对平衡二叉树T作中序遍历，输出结果； （8）在平衡二叉树中插入新元素，并作中序输出； （9）在平衡二叉树中删除元素，并作中序输出； （10）求平衡二叉树的平均查找长度； 2.1二叉排序树的建立 二叉排序树(Binary Sort Tree)又称二叉查找(有哪些信誉好的足球投注网站)树(Binary Search Tree)。其定义为：二叉排序树或者是空树，或者是满足如下性质的二叉树： 　　①若它的左子树非空，则左子树上所有结点的值均小于根结点的值； 　　②若它的右子树非空，则右子树上所有结点的值均大于根结点的值； ③左、右子树本身又各是一棵二叉排序树。 建二叉树的结点至少应当包含三个域，分别存放结点的数据data，左子女结点指针leftChild和右子女结点指针rightChild。整个二叉树的链表要有一个表头指针，它指向二叉树的根结点，其作用是当作树的访问点 从空的二叉排序树开始，经过一系列的查找插入操作以后，生成了一棵二叉排序树。 根据二叉排序树的定义，建立一棵二叉排序树的过程是按照待排序序列元素的先后次序，不断动态生成二叉树的结点，逐个插入到二叉树中。若p为根结点指