二叉平衡排序树.docx
- 文档编号:5107916
- 上传时间:2023-05-08
- 格式:DOCX
- 页数:28
- 大小:20KB
二叉平衡排序树.docx
《二叉平衡排序树.docx》由会员分享,可在线阅读,更多相关《二叉平衡排序树.docx(28页珍藏版)》请在冰点文库上搜索。
二叉平衡排序树
《数据结构》
课程设计报告
专业:
计算机科学与技术
班级:
2009级1
姓名:
陈雪敏
指导教师:
张珑
学号:
2009040608
二叉平衡排序树
一、课程设计内容
问题描述:
从一棵空树开始创建,在创建过程中,保证树的有序性,同时还要针对树的平衡性做些调整。
最终要把创建好的二叉排序树转换为二叉平衡排序树。
基本要求:
1.创建(插入、调整、改组)
2.输出
二、概要设计
1、.主要数据结构定义
typedefstructnodenode;
structnode
{
node*parent;
node*left;
node*right;
intbalance;//左右子树高度之差
intkey;
};
2、主要函数说明
intsearchNode(intkey,node*root,node**parent):
按key查找结点
node*minNode(node*root):
树root的最小结点
node*maxNode(node*root):
树root的最大结点
node*preNode(node*target):
求前驱结点
node*nextNode(node*target):
求后继结点
node*adjustAVL(node*root,node*parent,node*child):
调整,保证二叉树的平衡性
node*insertNode(intkey,node*root):
插入
node*deleteNode(intkey,node*root):
删除
node*createAVL(int*data,intsize):
建造新的二叉树
voidinterordertraverse(node*root):
中序遍历
voidpreordertraverse(node*root):
先序遍历
3、二叉排序树的插入和删除
a.二叉排序树的插入
在二叉排序树中插入新结点,要保证插入后的二叉树仍符合二叉排序树的定义。
插入过程:
若二叉排序树已存在,则返回根节点;
当节点不存在时,将待插结点关键字key和树根关键字parent->key进行比较,
若key
否则,则插入到根的右子树中。
而子树中的插入过程和在树中的插入过程相同,如此进行下去,直到把结点作为一个新的树叶插入到二叉排序树中,或者直到发现树已有相同关键字的结点为止。
并且注意二叉树的平衡性,时刻调整。
b.二叉排序树的删除
假设在二叉排序树上被删结点为*tp,其双亲结点为*parent,且不失一般性,可设**parent是*parent->left;的左孩子。
下面分3种情况进行讨论:
(1)若*parent结点为叶子结点,即PL和PR均为空树。
由于删去叶子结点不破坏整棵树的结构,则只需要修改其双亲结点的指针即可。
(2)若*parent结点只有左子树PL或者只有右子树PR,此时只要令PL或PR直接成为其双亲结点*f的左子树即可。
显然,作此修改也不破坏二叉排序树的特性。
(3)若*parent结点的左子树和右子树均不空。
并且注意二叉树的平衡性,时刻调整。
4、中序遍历和先序遍历
voidinterordertraverse(node*root)//中序遍历
{
if(root!
=NULL)
{
interordertraverse(root->left);
printf("%d,%d\n",root->key,root->balance);
interordertraverse(root->right);
}
}
voidpreordertraverse(node*root)//先序遍历
{
if(root!
=NULL)
{
printf("%d,%d\n",root->key,root->balance);
preordertraverse(root->left);
preordertraverse(root->right);
}
}
5、调整二叉树的平衡性
node*adjustAVL(node*root,node*parent,node*child)
主要有四种调整类型根据平衡因子主要有LR、LL、RL、RR
(1)、根据parent->balance的值为2时,child->balance==-1时是LR型,否则为LL型;
if(child->balance==-1)//LR型
{
cur=child->right;
cur->parent=parent->parent;
child->right=cur->left;
if(cur->left!
=NULL)
cur->left->parent=child;
parent->left=cur->right;
if(cur->right!
=NULL)
cur->right->parent=parent;
cur->left=child;
child->parent=cur;
cur->right=parent;
if(parent->parent!
=NULL)
if(parent->parent->left==parent)
parent->parent->left=cur;
elseparent->parent->right=cur;
else
root=cur;
parent->parent=cur;
if(cur->balance==0)
{
parent->balance=0;
child->balance=0;
}
elseif(cur->balance==-1)
{
parent->balance=0;
child->balance=1;
}
else
{
parent->balance=-1;
child->balance=0;
}
cur->balance=0;
}
else//LL型
{
child->parent=parent->parent;
parent->left=child->right;
if(child->right!
=NULL)
child->right->parent=parent;
child->right=parent;
if(parent->parent!
=NULL)
if(parent->parent->left==parent)
parent->parent->left=child;
elseparent->parent->right=child;
else
root=child;
parent->parent=child;
if(child->balance==1)//插入时
{
child->balance=0;
parent->balance=0;
}
else//删除时
{
child->balance=-1;
parent->balance=1;
}
}
break;
(2)、parent->balance的值为-2时,child->balance==1时是RL型,否则为RR
if(child->balance==1)//RL型
{
cur=child->left;
cur->parent=parent->parent;
child->left=cur->right;
if(cur->right!
=NULL)
cur->right->parent=child;
parent->right=cur->left;
if(cur->left!
=NULL)
cur->left->parent=parent;
cur->left=parent;
cur->right=child;
child->parent=cur;
if(parent->parent!
=NULL)
if(parent->parent->left==parent)
parent->parent->left=cur;
elseparent->parent->right=cur;
else
root=cur;
parent->parent=cur;
if(cur->balance==0)
{
parent->balance=0;
child->balance=0;
}
elseif(cur->balance==1)
{
parent->balance=0;
child->balance=-1;
}
else
{
parent->balance=1;
child->balance=0;
}
cur->balance=0;
}
else//RR型
{
child->parent=parent->parent;
parent->right=child->left;
if(child->left!
=NULL)
child->left->parent=parent;
child->left=parent;
if(parent->parent!
=NULL)
if(parent->parent->left==parent)
parent->parent->left=child;
elseparent->parent->right=child;
else
root=child;
parent->parent=child;
if(child->balance==-1)//插入时
{
child->balance=0;
parent->balance=0;
}
else//删除时
{
child->balance=1;
parent->balance=-1;
}
}
break;
6、主函数voidmain()
给出了一组数据{1,13,7,4},对数据中序遍历和先序遍历,然后是插入、删除、查询、退出操作。
三、系统实现
运行环境
Windows7操作系统,MicrosoftVisualC++6.0。
四、程序
#include
#include
#include
#include
#include
#include
//错误当参数expression为false时程序执行被中断
typedefstructnodenode;
structnode
{node*parent;
node*left;
node*right;
intbalance;//平衡因子(左右子树高度之差)
intkey;
};
externvoidinterordertraverse(node*root);//中序遍历
externvoidpreordertraverse(node*root);//前序遍历
intsearchNode(intkey,node*root,node**parent)//按key查找结点
{
node*temp;
assert(root!
=NULL);
temp=root;
*parent=root->parent;
while(temp!
=NULL)
{
if(temp->key==key)return1;
else{
*parent=temp;
if(temp->key>key)
temp=temp->left;
else
temp=temp->right;
}
}
return0;
}
node*minNode(node*root)//树root的最小结点
{
if(root==NULL)
returnNULL;
while(root->left!
=NULL)
root=root->left;
returnroot;
}
node*maxNode(node*root)//树root的最大结点
{
if(root==NULL)
returnNULL;
while(root->right!
=NULL)
root=root->right;
returnroot;
}
node*preNode(node*target)//求前驱结点
{
if(target==NULL)
returnNULL;
if(target->left!
=NULL)
returnmaxNode(target->left);
else
while((target->parent!
=NULL)&&(target!
=target->parent->right))
target=target->parent;
returntarget->parent;
}
node*nextNode(node*target)//求后继结点
{
if(target==NULL)
returnNULL;
if(target->right!
=NULL)
returnminNode(target->right);
else
while((target->parent!
=NULL)&&(target!
=target->parent->left))
target=target->parent;
returntarget->parent;
}
node*adjustAVL(node*root,node*parent,node*child)//调整旋转操作
//保持二叉排序树的平衡性
{
node*cur;
assert((parent!
=NULL)&&(child!
=NULL));
switch(parent->balance)
{
case2:
//平衡因子由1增至2
if(child->balance==-1)//LR型双向旋转(先左后右)平衡处理
{
cur=child->right;
cur->parent=parent->parent;
child->right=cur->left;
if(cur->left!
=NULL)
cur->left->parent=child;
parent->left=cur->right;
if(cur->right!
=NULL)
cur->right->parent=parent;
cur->left=child;
child->parent=cur;
cur->right=parent;
if(parent->parent!
=NULL)
if(parent->parent->left==parent)
parent->parent->left=cur;
elseparent->parent->right=cur;
else
root=cur;
parent->parent=cur;
if(cur->balance==0)
{
parent->balance=0;
child->balance=0;
}
elseif(cur->balance==-1)
{
parent->balance=0;
child->balance=1;
}
else
{
parent->balance=-1;
child->balance=0;
}
cur->balance=0;
}
else//LL型单向右旋平衡处理
{
child->parent=parent->parent;
parent->left=child->right;
if(child->right!
=NULL)
child->right->parent=parent;
child->right=parent;
if(parent->parent!
=NULL)
if(parent->parent->left==parent)
parent->parent->left=child;
elseparent->parent->right=child;
else
root=child;
parent->parent=child;
if(child->balance==1)//插入时
{
child->balance=0;
parent->balance=0;
}
else//删除时
{
child->balance=-1;
parent->balance=1;
}
}
break;
case-2:
//平衡因子由-1变为-2
if(child->balance==1)//RL型双向旋转(先右后左)平衡处理
{
cur=child->left;
cur->parent=parent->parent;
child->left=cur->right;
if(cur->right!
=NULL)
cur->right->parent=child;
parent->right=cur->left;
if(cur->left!
=NULL)
cur->left->parent=parent;
cur->left=parent;
cur->right=child;
child->parent=cur;
if(parent->parent!
=NULL)
if(parent->parent->left==parent)
parent->parent->left=cur;
elseparent->parent->right=cur;
else
root=cur;
parent->parent=cur;
if(cur->balance==0)
{
parent->balance=0;
child->balance=0;
}
elseif(cur->balance==1)
{
parent->balance=0;
child->balance=-1;
}
else
{
parent->balance=1;
child->balance=0;
}
cur->balance=0;
}
else//RR型单向左旋平衡处理
{
child->parent=parent->parent;
parent->right=child->left;
if(child->left!
=NULL)
child->left->parent=parent;
child->left=parent;
if(parent->parent!
=NULL)
if(parent->parent->left==parent)
parent->parent->left=child;
elseparent->parent->right=child;
else
root=child;
parent->parent=child;
if(child->balance==-1)//插入时
{
child->balance=0;
parent->balance=0;
}
else//删除时
{
child->balance=1;
parent->balance=-1;
}
}
break;
}
returnroot;
}
node*insertNode(intkey,node*root)//插入
{
node*parent,*cur,*child;
assert(root!
=NULL);
if(searchNode(key,root,&parent))//结点已存在
returnroot;
else//节点不存在
{
cur=(node*)malloc(sizeof(node));
cur->parent=parent;
cur->key=key;
cur->left=NULL;
cur->right=NULL;
cur->balance=0;
if(key
{
parent->left=cur;
child=parent->left;
}
else
{
parent->right=cur;
child=parent->right;
}
while((parent!
=NULL))//查找需要调整的最小子树
{
if(child==parent->left)
if(parent->balance==-1)
{
parent->balance=0;
returnroot;
}
elseif(parent->balance==1)
{
parent->balance=2;
break;
}
else
{
parent->balance=1;
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 二叉 平衡 排序