数据结构课程设计报告-二叉排序树与平衡二叉树的实现
更新时间:2023-12-04 01:56:01 阅读量: 教育文库 文档下载
二叉排序树与平衡二叉树的实现
【摘要】
本课程设计分为两部分。第一部分为分别用二叉链表和顺序表作为存储结构实现二叉排序树,并实现树的生成,中序遍历,计算平均查找长度,对结点进行查找、删除等操作。第二部分为用二叉链表作为存储结构实现平衡二叉树,并实现树的生成,计算平均查找长度,元素的插入、删除及之后的重新平衡等操作。
【关键词】二叉排序树,平衡二叉树,中序遍历,平均查找长度 1.介绍
该设计分别采用二叉链表和顺序表作存储结构,实现对二叉排序树和平衡二叉树的以下操作:
(1)用二叉链表作存储结构实现二叉排序树。
1)以0作为输入结束标志,输入数列L,生成一棵二叉排序 树T;
2)对二叉排序树T作中序遍历,输出结果;
3)计算二叉排序树T查找成功的平均查找长度,输出结果; 4)输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历(执行操作2);否则,输出信息“无x”; (2)用顺序表(一维数组)作存储结构实现二叉排序树。
1)以回车符(‘\\n’)为输入结束标志,输入数列L,生成一棵二叉排序树T;
34
2)对二叉排序树T作中序遍历,输出结果;
3)计算二叉排序树T查找成功的平均查找长度,输出结果; 4)输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历(执行操作2);否则,输出信息“无x”; (3)用二叉链表作存储结构实现平衡的二叉排序树。
1)用数列L,生成平衡的二叉排序树BT:当插入新元素之后,发现当前的二叉排序树BT不是平衡的二叉排序树,则立即将它转换成新的平衡的二叉排序树BT;
2)计算平衡的二叉排序树BT的平均查找长度,输出结果。
2.主体部分
生成二叉排序树:
建二叉树的结点至少应当包含三个域,分别存放结点的数据data,左子女结点指针leftChild和右子女结点指针rightChild。整个二叉树的链表要有一个表头指针,它指向二叉树的根结点,其作用是当作树的访问点。从空的二叉排序树开始,经过一系列的查找插入操作以后,生成了一棵二叉排序树。
根据二叉排序树的定义,建立一棵二叉排序树的过程是按照待排序序列元素的先后次序,不断动态生成二叉树的结点,逐个插入到二叉树中。若p为根结点指针,b为当前待插入元素,其过程可以描述为:若为空树(p=NULL),动态生成一个结点,其数据域为当前待插入元素b,左、右指针域为“空”,p指向该结点。若非空树,比较b与根结点数据data(p)如果b 35 b≥data(p),将b插入右子树中;左、右子树的插入方式与二叉排序树的插入方式相同。不断调用上述的插入过程,直到所有待排序序列均排入后,就形成一棵二叉排序树。 中序遍历: 中序遍历二叉树算法的框架是:若二叉树为空,则空操作;否则 中序遍历左子树(L),访问根结点(V),中序遍历右子树(R)。中序遍历二叉树也采用递归函数的方式,先访问左子树,然后访问根结点,最后访问右子树,直至所有的结点都被访问完毕。 元素的查找 在二叉排序树上进行查找,是一个从根结点开始,沿某一个分支逐层向下进行比较判等的过程。它可以是一个递归的过程。假设我们想要在二叉排序树中查找关键码为x的元素,查找过程从根结点开始。如果根指针为NULL,则查找不成功;否则用给定值x与根结点的关键码进行比较;如果给定值等于根结点的关键码,则查找成功,返回查找成功的信息,并报告查找到的结点地址。如果给定值小于根结点的关键码,则继续递归查找根结点的左子树;否则,递归搜索根结点的右子树。 平均查找长度: 计算二叉排序树的平均查找长度,仍采用类似中序遍历的递归方式,用s记录总查找长度,j记录每个结点的查找长度,s置初值为0,采用累加的方式最终得到总查找长度s,平均查找长度就等于s/j(i为树中结点的总个数)。 36 元素的删除: 对于二叉排序树,删去树上的一个结点相当于删去有序序列中的一个记录,只要在删除某个结点之后依旧保持二叉排序树的特性即可。假设在二叉排序树上被删除结点为*p(指向结点的指针是p),其双亲结点为*f(结点指针为f),且不失一般性,可设*p是*f的左孩子,若*p结点为叶子结点,即p和l均为空,只需修改其双亲结点指针即可。若*p结点只有左子树或者只有右子树,只要令左子树或右子树直接成为其双亲结点即可。若左子树和右子树都不为空,令*p的直接前驱替代*p,然后从二叉排序树中删除它的直接前驱,即可。 37 3.运行效果 (1)用二叉链表作存储结构实现二叉排序树。 设插入的数据为1,2,3,4,5,需要查找的数据为3: 若需要查找的数据为7,而7不存在时: 38
正在阅读:
数据结构课程设计报告-二叉排序树与平衡二叉树的实现12-04
2017-2018学年新人教版二年级数学第二学期 期末试卷07-10
小班建构游戏小动物的家教案04-27
综合楼毕业设计任务书03-13
我的拿手好戏(优秀4篇)03-22
《狼王梦》读后感600字07-01
四边形复习提纲(经典题型解析)汇总05-24
诚信承诺书(优秀3篇)03-28
《编译原理》期中及期末习题04-14
中考文言文阅读专题训练(八下)05-22
- exercise2
- 铅锌矿详查地质设计 - 图文
- 厨余垃圾、餐厨垃圾堆肥系统设计方案
- 陈明珠开题报告
- 化工原理精选例题
- 政府形象宣传册营销案例
- 小学一至三年级语文阅读专项练习题
- 2014.民诉 期末考试 复习题
- 巅峰智业 - 做好顶层设计对建设城市的重要意义
- (三起)冀教版三年级英语上册Unit4 Lesson24练习题及答案
- 2017年实心轮胎现状及发展趋势分析(目录)
- 基于GIS的农用地定级技术研究定稿
- 2017-2022年中国医疗保健市场调查与市场前景预测报告(目录) - 图文
- 作业
- OFDM技术仿真(MATLAB代码) - 图文
- Android工程师笔试题及答案
- 生命密码联合密码
- 空间地上权若干法律问题探究
- 江苏学业水平测试《机械基础》模拟试题
- 选课走班实施方案
- 数据结构
- 排序
- 平衡
- 课程
- 实现
- 报告
- 设计
- 高中心理活动课教案集上
- 城乡居民养老待遇和低保的比较
- 列方程解决问题—行程问题
- 高频课后习题答案
- 《微型计算机接口技术》试题(A)
- 古代表示官职升迁任免的词语
- 少先队知识十知道
- 酒店市场调研报告范本3
- 齿轮加工工艺说明书
- 丰城市特殊教育学校安全大排查工作实施方案
- 2017国考时政热点:代写论文被骗一万八,这钱花得值
- 条石堡坎施工规范案例
- 分析化学全部作业共五次
- 2018年中国增强现实(AR)行业市场分析报告 - 图文
- 战略合作框架协议合同范本(模板)
- 上海市中小学体育器材配置现状分析-最新教育文档
- 多选题题库(学生)
- 大气污染控制技术试卷及答案评分标准-A
- 2016年浙江省高等职业技术教育招生考试语文
- 优易电商ERP操作手册(自有仓)