二叉平衡排序树.docx
《二叉平衡排序树.docx》由会员分享，可在线阅读，更多相关《二叉平衡排序树.docx（18页珍藏版）》请在冰点文库上搜索。
《数据结构》课程设计报告
专 业：
计算机科学与技术
班 级：
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进行比较，若keykey，则插入到根的左子树中，
否则，则插入到根的右子树中。
而子树中的插入过程和在树中的插入过程相同，如此进行下去，直到把结点作为一个新的树叶插入到二叉排序树中，或者直到发现树已有相同关键字的结点为止。
并且注意二叉树的平衡性，时刻调整。
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//assert用于调试声明宏，用于定位程序开发中的逻辑
//错误当参数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（keykey）
{
parent->left=cur;child=parent->left;
}
else
{
parent->righ
升级会员 