没有合适的资源?快使用搜索试试~ 我知道了~
计算机科学与技术课程设计.docx
资源推荐
资源详情
资源评论
一、课程设计题目
二叉平衡排序树
摘要 问题描述:从一棵空树开始创建,在创建过程中,保证树的有序性,同时
还要针对树的平衡性做些调整。最终要把创建好的二叉排序树转换为二叉平衡排
序树。
基本要求:1.创建(插入、调整、改组)
2.输出
开发工具:windows XP 操作系统,Microsoft visual c++ 6.0 编译系统;
关键词:C++ ;
二、设计主要目的及意义
目的:
1.熟悉掌握二叉树的基本操作
2.熟悉二叉树的创建(插入、调整、改组),输出以及把二叉排序树转换为二
叉平衡排序树
3.更进一步掌握有关二叉排序树的操作
意义:
软件课程设计是计算机科学与技术专业软件方向的一个重要环节,是语言类
课程学习的总结。通过课程设计使我们加深对程序设计的理解,掌握程序开发的
基本方法,深化学生面向对象的编程设计思想和新一代程序设计的逻辑思维方式,
把课堂上所学到的多个单元串到一起,提高我们在软件设计过程中分析问题和解
决问题的实际动手能力,使我们的理论知识和实践技能得到共同发展,最终提高
我们解决问题和分析问题的能力。为我们踏上工作岗位之前提供了一次专业研究
和项目开发的宝贵实践机会,为今后的工作积累经验。
三、课程设计的过程
主要算法说明:
1.主要数据结构定义
typedef struct node node ;
Struct node
{
Node*parent;
Node*left;
Node*right;
Int balance;//左右子树高度之差
Int key;
}
2.主要函数说明
Int scarchNode(int key, node* root, node*parent):按 key 查找结点
Node* minNode(node* root):树 root 的最小结点
Node* maxNode(node* root):树 root 的最大结点
Node* preNode(node* target):求前驱结点
Node* nextNode(node* targer):求后继结点
node* adjustAVL(node* root, node* parent, node* child);调整,保证二叉树的平衡
性
Node* insertNode(int key, node* root):插入
Node* deletevode(int key, node* root):删除
Node*createAVL(int* data, int size):创建新的二叉树
Void interordertraverse (node*root):中序遍历
Void preordertraverse(node* root):先序遍历
3.二叉排序树的插入和删除
a.二叉排序树的插入
在二叉排序树插入新结点,要保证插入后的二叉树仍符合二叉排序树的定义
插入过程:若二叉排序树正存在,则返回根结点;
当结点不存在时,将待插入到根结点的关键字 key 和树根关键字 parent->key 进行
比较.
若 key<parent->key,则插入到根的左子树中,否则,插入到根的右子树中.而子树中
的插入过程和在树中的插入过程相同,如此进行下去,直到把结点作为一个新的树
叶插入到二叉排序树中或者直到发现树已有相同关键字的结点为止,并且注意二
叉树的平衡,时刻调整.
b.二叉排序树的删除
假设在二叉排序树上被删结点为*tp,其双亲结点为*parent,且不失一般性,可设
*parent 是*parent->left 的左孩子.
下面分了 3 种情况进行讨论:
(1).若*parent 结点为叶子结点,即 PL 和 PR 均为空树.由于删去叶子结点不破坏整
棵树的结构,则只需要修改其双亲,结构点的指针即可.
(2).若*parent 结点凡有左子树 PL 或者只有右子树 PR,此时只要令 PL 或 PR 直接成
为其双亲结点*f 的左子树即可.显然,作此修改也不破坏二叉排序树的特性.
(3).若*parent 结点的左子树均不空,并且注意二叉树的平衡性,时刻调整.
4.中序遍历和先序遍历
Void interordertraverse(node* root)//中序遍历
{
If(root 1=NULL)
{
Interordertraverse(root->left);
Printf("%d,%d\n,"root->key,root->balance);
Interordertraverse(root->right);
}
}
Void preordertraverse (node* root)//先序遍历
{
If (root!=NULL)
{
Printf("%d,%d\n",root->key,root->balance);
Preorderstraverse(root->left);
Preorderstraverse(root->right);
}
}
5.动态平衡技术的概念
Adelson-Velskii 和 Landis 提出了一个动态地保持二叉排序树平衡的方法,其基本思想
是:
在构造二叉排序树的过程中,每当插入一个结点时,首先检查是否因插入而破坏了树的
平衡性,如果是因插入结点而破坏了树的平衡性,则找出其中最小不平衡子树,在保持排序
树特性的前提下,调整最小不平衡子树中各结点之间的连接关系,以达到新的平衡。通常将
这样得到的平衡二叉排序树简称为 AVL 树。
为了保证二叉排序树的高度为 lgn,从而保证二叉排序树上实现的插入、删除和查找等
基本操作的平均时间为 O(lgn),在往树中插入或删除结点时,要调整树的形态来保持树的平
衡。使之既保持 BST 性质不变又保证树的高度在任何情况下均为 O(lgn),从而确保树上的基
本操作在最坏情况下的时间均为 O(lgn)。
6. 最小不平衡子树的概念
以离插入结点最近、且平衡因子绝对值大于 1 的结点作根结点的子树。为了简化讨论,
不妨假设二叉排序树的最小不平衡子树的根结点为 A ,则调整该子树的规律可归纳为下列
四种情况:
图 3 平衡调整的 4 种基本类型(结点旁的数字是平衡因子)
(1) LL 型:
新结点 X 插在 A 的左孩子的左子树里。调整方法见图 3(a)。图中以 B 为轴心,将
A 结点从 B 的右上方转到 B 的右下侧,使 A 成为 B 的右孩子。
(2)RR 型:
新结点 X 插在 A 的右孩子的右子树里。调整方法见图 3(b) 。图中以 B 为轴心,将 A
结点从 B 的左上方转到 B 的左下侧,使 A 成为 B 的左孩子。
(3)LR 型:
新结点 X 插在 A 的左孩子的右子树里。调整方法见图 3(c) 。分为两步进行:第一步
以 X 为轴心,将 B 从 X 的左上方转到 X 的左下侧,使 B 成为 X 的左孩子, X 成为 A
的左孩子。第二步跟 LL 型一样处理 ( 应以 X 为轴心 ) 。
(4)RL 型:
新结点 X 插在 A 的右孩子的左子树里。调整方法见图 3(d) 。分为两步进行:第一步
以 X 为轴心,将 B 从 X 的右上方转到 X 的右下侧,使 B 成为 X 的右孩子, X 成为 A
的右孩子。第二步跟 RR 型一样处理 ( 应以 X 为轴心 ) 。
7.调整叉树的平衡性
剩余20页未读,继续阅读
资源评论
财云量化
- 粉丝: 684
- 资源: 171
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功