二叉排序树及平衡二叉树.docx
《二叉排序树及平衡二叉树.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
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 二叉排序树 平衡 二叉