二叉平衡排序树Word文档下载推荐.docx
《二叉平衡排序树Word文档下载推荐.docx》由会员分享，可在线阅读，更多相关《二叉平衡排序树Word文档下载推荐.docx（28页珍藏版）》请在冰点文库上搜索。
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<
parent->
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）;
right）;
}
}
voidpreordertraverse（node*root）//先序遍历
preordertraverse（root->
}
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->
if（cur->
left!
left->
parent=child;
parent->
left=cur->
right!
right->
parent=parent;
left=child;
parent=cur;
right=parent;
if（parent->
parent!
left==parent）
left=cur;
elseparent->
right=cur;
else
root=cur;
balance==0）
balance=0;
elseif（cur->
balance==-1）
{
balance=1;
}
balance=-1;
else//LL型
left=child->
if（child->
right=child;
root=child;
balance==1）//插入时
else//删除时
break;
（2）、parent->
balance的值为-2时，child->
balance==1时是RL型，否则为RR
balance==1）//RL型
left=parent;
balance==1）
else//RR型
right=child->
balance==-1）//插入时
6、主函数voidmain（）
给出了一组数据{1,13,7,4}，对数据中序遍历和先序遍历，然后是插入、删除、查询、退出操作。
三、系统实现
运行环境
Windows7操作系统，MicrosoftVisualC++6.0。
四、程序
#include<
stdio.h>
string.h>
stdlib.h>
errno.h>
assert.h>
//assert用于调试声明宏，用于定位程序开发中的逻辑
//错误当参数expression为false时程序执行被中断
{node*parent;
//平衡因子（左右子树高度之差）
externvoidinterordertraverse（node*root）;
//中序遍历
externvoidpreordertraverse（node*root）;
//前序遍历
intsearchNode（intkey,node*root,node**parent）//按key查找结点
node*temp;
assert（root!
=NULL）;
temp=root;
*parent=root->
while（temp!
=NULL）
if（temp->
key==key）return1;
else{
*parent=temp;
key>
key）
temp=temp->
return0;
node*minNode（node*root）//树root的最小结点
if（root==NULL）
returnNULL;
while（root->
root=root->
returnroot;
node*maxNode（node*root）//树root的最大结点
node*preNode（node*target）//求前驱结点
if（target==NULL）
if（target->
returnmaxNode（target->
while（（target->
parent!
=NULL）&
&
（target!
=target->
right））
target=target->
returntarget->
node*nextNode（node*target）//求后继结点
returnminNode（target->
left））
node*adjustAVL（node*root,node*parent,node*child）//调整旋转操作
//保持二叉排序树的平衡性
node*cur;
assert（（parent!
=NULL）&
（child!
=NULL））;
switch（parent->
balance）
case2:
//平衡因子由1增至2
balance==-1）//LR型双向旋转（先左后右）平衡处理
cur->
if（parent->
parent->
elseparent->
root=cur;
child->
else//LL型单向右旋平衡处理
root=child;
case-2:
//平衡因子由-1变为-2
if（child->
balance==1）//RL型双向旋转（先右后左）平衡处理
{
cur=child->
if（cur->
cur->
if（parent->
elseparent->
else
root=cur;
parent->
child->
}
elseif（cur->
else//RR型单向左旋平衡处理
parent->
root=child;
else//删除时
break;
node*insertNode（intkey,node*root）//插入
node*parent,*cur,*child;
assert（root!
if（searchNode（key,root,&
parent））//结点已存在
returnroot;
else//节点不存在
cur=（node*）malloc（sizeof（node））;
key=key;
left=NULL;
right=NULL;
if（key<
key）
child=parent->
while（（parent!
=NULL））//查找需要调整的最小子树
if（child==parent->
left）
{
returnroot;
}
elseif（parent->
balance=2;
break;
else
升级会员 