没有合适的资源?快使用搜索试试~ 我知道了~
首页数据结构课程设计平衡二叉排序树的三种基本功能:查找、插入、删除。
数据结构课程设计平衡二叉排序树的三种基本功能:查找、插入、删除。
5星 · 超过95%的资源 需积分: 10 86 下载量 19 浏览量
更新于2023-07-09
9
收藏 326KB DOC 举报
1. 本程序实现平衡二叉排序树的三种基本功能:查找、插入、删除。 2. 初始平衡二叉树为空树,由用户输入要创建树的结点数,并输入每个结点的权值,以整数形式表示,边输入边排序构成平衡二叉排序树。 3. 对二叉树的插入和删除操作包含查找操作。插入的过程就要查找二叉树中是否存在和将插入结点的权值相等的结点,如果存在则不插入该结点。删除操作中如果指定要删除某个权值的结点,则也要先查找二叉树中是否存在与此权值相等的结点,若无,则删除失败。
资源详情
资源推荐
设计性实验报告
课程名称 数据结构
题目名称利用平衡二叉树实现一个动态查找表
2007 年 6 月 26 日
实习报告:6.4 平衡二叉树操作的演示
题目:编制一个演示平衡二叉树操作的程序
一、 需求分析
1. 本程序实现平衡二叉排序树的三种基本功能:查找、插入、删除。
2. 初始平衡二叉树为空树,由用户输入要创建树的结点数,并输入每个结点的权值 ,
以整数形式表示,边输入边排序构成平衡二叉排序树。
3. 对二叉树的插入和删除操作包含查找操作。插入的过程就要查找二叉树中是否存
在和将插入结点的权值相等的结点,如果存在则不插入该结点。删除操作中如果
指定要删除某个权值的结点,则也要先查找二叉树中是否存在与此权值相等的结
点,若无,则删除失败。
4. 每次对二叉树进行了插入或删除操作后都将输出更新后的二叉树,并以凹形表形
式输出,并同时输出关键字由小到大的排序结果。
5. 演示程序以用户和计算机的对话方式执行,即在计算机终端上显示“提示信息”下,
用户可由键盘输入二叉树的结点数,每个结点的权值,要插入结点的权值,要删
除结点的权值,并在完成一个操作后询问是否进行另外一个操作的演示。
二、概要设计
1.为实现本程序所构造的函数
R_Rotate(BSTree p)
操作结果:对以 p 为根的二叉排序树作右旋处理,处理之 p 指向新的树根结点,即旋
转处理之前的左子树根结点
L_Rotate(BSTree p)
操作结果:对以 p 为根的二叉排序树作左旋处理,处理之 p 指向新的树根结点,即旋
转处理之前的右子树根结点
LeftBalance(BSTree T)
操作结果:对以指针 T 所指结点为根的二叉树作左平衡旋转处理,本算法结束时指针
指向新的根结点
RightBalance(BSTree T)
操作结果:对以指针 T 所指结点为根的二叉树作右平衡旋转处理,本算法结束时指针
T 指向新的根结点
InsertAVL (BSTree T, int e)
操作结果:若在平衡的二叉排序树 T 中不存在和 e 有相同关键字的结点,则插入一个
数据元素为 e 的新结点,并返回插入后所建成的平衡二叉排序树,否则返回 NULL.若因
插入而使二叉数失去平衡,则作平衡旋转处理,布尔变量 taller 反映 T 长高与否
midorder(BSTree T)
操作结果:中序遍历二叉树并输出遍历结果
Print_BSTree(BSTree T,int i)
操作结果:按树状打印输出二叉树的元素,呈凹入表形式;
RightBalance1(BSTree p)
操作结果:删除结点时对以指针 p 所指结点为根的二叉树作右平衡旋转处理,本算法
结束时指针 p 指向新的根结点
LeftBalance1(BSTree p)
操作结果:删除结点时对以指针 p 所指结点为根的二叉树作左平衡旋转处理,本算法结束
时
指针 p 指向新的根结点
Delete(BSTree q, BSTree r)
操作结果:对结点进行删除处理
DeleteAVL(BSTree p, int e)
操作结果:找到要删除的结点,并调用删除函数对其进行删除
CreateBST()
操作结果:调用插入函数创建一颗二叉排序树;
Window();
操作结果:打印输出程序的主界面
Back()
操作结果:返回程序主界面
2.主程序
Void main()
{初始化;
do{
接受命令(输入要进行的操作);
处理命令;
}while(“命令”!=“退出”);
}
3.本程序有三个模块:主程序模块插入函数模块(也即构造二叉排序树模块)删除函数模
块。
主程序模块
插入函数模块 删除函数模块
三、 详细设计
1. -二叉排序树的类型
typedef struct BSTNode
{
int data;
int bf; /*结点的平衡因子*/
struct BSTNode * lchild, * rchild;
}BSTNode, *BSTree;
2.实现本程序的函数的代码:
/*对以 p 为根的二叉排序树作右旋处理,处理之 p 指向新的树根结点*/
/*----------即旋转处理之前的左子树根结点----------*/
BSTree R_Rotate(BSTree p)
{
BSTNode *lc;
lc=p->lchild; /*lc 指向*p 的左子树根结点*/
p->lchild=lc->rchild; /*lc 的右子树挂接为*p 的左子树*/
lc->rchild=p;p=lc; /*p 指向新的根结点*/
return p;
} /*R_Rotate*/
/*对以 p 为根的二叉排序树作左旋处理,处理之 p 指向新的树根结点*/
/*-----------即旋转处理之前的右子树根结点-------------*/
BSTree L_Rotate(BSTree p)
{
BSTNode *rc;
rc=p->rchild; /*rc 指向*p 的右子树根结点*/
p->rchild=rc->lchild; /*rc 的右子树挂接为*p 的右子树*/
rc->lchild=p;p=rc; /*p 指向新的根结点*/
return p;
}/*L_Rotate*/
/*对以指针 T 所指结点为根的二叉树作左平衡旋转处理,本算法结束时*/
/*--------指针 T 指向新的根结点---------*/
BSTree LeftBalance(BSTree T)
{
BSTNode *lc,*rd;
lc=T->lchild; /*lc 指向*T 的左子树根结点*/
switch(lc->bf) /* 检查*T 的左子树的平衡度,并作相应平衡处理 */
{
case LH:
T->bf=lc->bf=EH; /* 新结点插入在*T 的左孩子的左子树上,要作单右旋处理 */
T=R_Rotate(T);
break;
case RH: /* 新结点插入在*T 的左孩子的右子树上,要作双旋处理 */
rd=lc->rchild; /* rd 指向*T 的左孩子的右子树根 */
switch(rd->bf)
{ /* 修改*T 及其左孩子的平衡因子 */
case LH:T->bf=RH;lc->bf=EH; break;
case EH:T->bf=lc->bf=EH;break;
case RH:T->bf=EH;lc->bf=LH;break;
}/* switch(rd->bf) */
rd->bf=EH;
T->lchild=L_Rotate(T->lchild); /* 对*T 的左子树作左旋平衡处理 */
T=R_Rotate(T); /* 对*T 作右旋平衡处理 */
}/* switch(lc->bf) */
return T;
} /* LeftBalance */
/*对以指针 T 所指结点为根的二叉树作右平衡旋转处理,本算法结束时*/
/*指针 T 指向新的根结点*/
BSTree RightBalance(BSTree T)
{
BSTree rc,ld;
rc=T->rchild; /*rc 指向*T 的右子树根结点*/
switch(rc->bf) /* 检查*T 的右子树的平衡度,并作相应平衡处理 */
{
剩余16页未读,继续阅读
yan2hui
- 粉丝: 26
- 资源: 5
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- 保险服务门店新年工作计划PPT.pptx
- 车辆安全工作计划PPT.pptx
- ipqc工作总结PPT.pptx
- 车间员工上半年工作总结PPT.pptx
- 保险公司员工的工作总结PPT.pptx
- 报价工作总结PPT.pptx
- 冲压车间实习工作总结PPT.pptx
- ktv周工作总结PPT.pptx
- 保育院总务工作计划PPT.pptx
- xx年度现代教育技术工作总结PPT.pptx
- 出纳的年终总结PPT.pptx
- 贝贝班班级工作计划PPT.pptx
- 变电值班员技术个人工作总结PPT.pptx
- 大学生读书活动策划书PPT.pptx
- 财务出纳月工作总结PPT.pptx
- 大学生“三支一扶”服务期满工作总结(2)PPT.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功