没有合适的资源?快使用搜索试试~ 我知道了~
首页课设 - 平衡二叉树的演示 .docx
源码博客上有,所有人可看 一、需求分析: (1) 构建一个平衡二叉树并实现创建、插入、查找、删除、销毁等操作。每种操作均提示输入关键字。每次插入或删除一个结点后,更新平衡二叉树的显示。 (2) 平衡二叉树的显示采用凹入表现形式。 (3)输入的形式时数字,无论对功能的选择还是对数据的录入,都是以数字的形式进行输入,无需使用文件保存数据。 (4) 输出的形式时在dos界面进行输出,一旦检测到错误的输入就会报错提示用户从新输入。 (5)程序所能达到的功能: A:创建一颗非空平衡二叉树 B:向平衡二叉树中添加结点 C:从平衡二叉树中删除结点 D:在平衡二叉树中查找结点 E:销毁平衡二叉树 F:输出打印一棵平衡二叉树 G:合并两棵平衡二叉树 H:分裂一颗平衡二叉树
资源详情
资源评论
资源推荐
数据结构课程设计报告
题目:平衡二叉树操作的演示
学 院 计算机学院
专 业 软件工程
年级班别 2018
级 班
编 号
成 绩 ____________________
2020 年 01 月
报告:
报告内容: □详细 □完整 □基本完整 □不完整
设计方案: □非常合理 □合理 □基本合理 □较差
算法实现: □全部实现 □基本实现 □部分实现 □实现较差
测试样例: □完备 □比较完备 □基本完备 □不完备
文档格式: □规范 □比较规范 □基本规范 □不规范
答辩:
□理解题目透彻,问题回答流利
□理解题目较透彻,回答问题基本正确
□部分理解题目,部分问题回答正确
□未能完全理解题目,答辩情况较差
总评成绩:
□优 □良 □中 □及格 □不及格
1
目录:
1.需求分析--------------------------------------------- 3
2.课题设计内容--------------------------------------- 3
(1)概要设计----------------------------------------------------- 3
(2)流程图-------------------------------------------------------- 4
(3)主要函数----------------------------------------------------- 4
(4)存储结构定义------------------------------------------------ 5
(5)算法设计----------------------------------------------------- 5
3.调试分析--------------------------------------------- 16
(1)算法时空分析------------------------------------------------ 16
(2)程序的优点--------------------------------------------------- 16
(3)经验和体会--------------------------------------------------- 16
4.使用说明--------------------------------------------- 17
5 测试结果--------------------------------------------- 17
2
题目 12 平衡二叉树操作的演示(难度系数:1.3)
[运行环境]
DEV - c++
[问题描述]
利用平衡二叉树实现一个动态查找表。
[基本要求]
实现动态查找表的三种基本功能:查找、插入和删除。
[选做内容]
(1) 合并两棵平衡二叉树。(已做)
(2) 把一棵平衡二叉树分裂为两棵平衡二叉树,使得在一棵树中的所有关键字都小于或等于
x,另一棵树中的任一关键字都大于 x。(已做)
一、需求分析:
(1) 构建一个平衡二叉树并实现创建、插入、查找、删除、销毁等操作。每种操作均提
示输入关键字。每次插入或删除一个结点后,更新平衡二叉树的显示。
(2) 平衡二叉树的显示采用凹入表现形式。
(3)输入的形式时数字,无论对功能的选择还是对数据的录入,都是以数字的形式进行输
入,无需使用文件保存数据。
(4) 输出的形式时在 dos 界面进行输出,一旦检测到错误的输入就会报错提示用户从新
输入。
(5)程序所能达到的功能:
A:创建一颗非空平衡二叉树
B:向平衡二叉树中添加结点
C:从平衡二叉树中删除结点
D:在平衡二叉树中查找结点
E:销毁平衡二叉树
F:输出打印一棵平衡二叉树
G:合并两棵平衡二叉树
H:分裂一颗平衡二叉树
二、课题设计内容:
1、概要设计
本程序涉及的数据类型有:平衡二叉树,结构体数组
3
平衡二叉树是在构造二叉排序树的过程中,每当插入一个新结点时,首先检查是否因
插入新结点而破坏了二叉排序树的平衡性,若是,则找出其中的最小不平衡子树,在保持
二叉排序树特性的前提下,调整最小不平衡子树中各结点之间的链接关系,进行相应的旋
转,使之成为新的平衡子树。具体步骤如下:
(1) 每当插入一个新结点,从该结点开始向上计算各结点的平衡因子,即计算该结
点的祖先结点的平衡因子,若该结点的祖先结点的平衡因子的绝对值不超过 1,则平衡二
叉树没有失去平衡,继续插入结点;
(2) 若插入结点的某祖先结点的平衡因子的绝对值大于 1,则找出其中最小不平衡
子树的根结点;
(3) 判断新插入的结点与最小不平衡子树的根结点个关系,确定是那种类型的调整;
(4) 如果是 LL 型或 RR 型,只需应用扁担原理旋转一次,在旋转过程中,如果出现
冲突,应用旋转优先原则调整冲突;如果是 LR 型或 RL 型,则需应用扁担原理旋转两次,
第一次最小不平衡子树的根结点先不动,调整插入结点所在子树,第二次再调整最小不平
衡子树,在旋转过程中,如果出现冲突,应用旋转优先原则调整冲突;
(5) 计算调整后的平衡二叉树中各结点的平衡因子,检验是否因为旋转而破坏其他
结点的平衡因子,以及调整后平衡二叉树中是否存在平衡因子大于 1 的结点。
2、流程图:
1. 主要函数:
void CreatBBST(BBSTree &T); //构建一棵二叉平衡树
BBSTree SearchBBST(BBSTree T,KeyType Key); //二叉平衡树非递归查找
void R_Rotate(BBSTree &p); //对最小失衡子树 p 作右旋调整
void L_Rotate(BBSTree &p); //对最小失衡子树 p 作左旋调整
void LeftBalance(BBSTree &T); //左平衡处理操作
void RightBalance(BBSTree &T); //右平衡处理操作
Status InsertAVL(BBSTree &T,RcdType e,Status &taller); //将 e 插入到二叉树
4
剩余21页未读,继续阅读
戮漠
- 粉丝: 47
- 资源: 6
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- RTL8188FU-Linux-v5.7.4.2-36687.20200602.tar(20765).gz
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
- SPC统计方法基础知识.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论0