平衡二叉树操作的演示Word下载.docx
《平衡二叉树操作的演示Word下载.docx》由会员分享，可在线阅读，更多相关《平衡二叉树操作的演示Word下载.docx（13页珍藏版）》请在冰点文库上搜索。
if（p->
bf==0）//原本左右子树等高，现因左子树增高而使树增高
{p->
bf=1;
taller=1;
}
elseif（p->
bf==-1）//原本右子树比左子树高，现左右子树等高
bf=0;
taller=0;
else//原本左子树比右子树高，须作左子树的平衡处理
{p1=p->
lchild;
//p指向*p的左子树根节点
if（p1->
bf==1）//新结点插入在*p的左孩子的左子树上，要做LL调整
lchild=p1->
rchild;
p1->
rchild=p;
p->
bf=p1->
p=p1;
elseif（p1->
bf==-1）//新结点插入在*p的左孩子的右子树上，要做LR调整
{p2=p1->
rchild=p2->
p2->
lchild=p1;
lchild=p2->
if（p2->
bf==0）//新结点插入在*p2处作为叶子结点的情况
elseif（p2->
bf==1）//新结点插在*p2的左子树上的情况
{p1->
bf=-1;
else//新结点插在*p2的右子树上的情况
p=p2;
//仍将p指向新的根结点，并置其bf值为0
}
voidRightProcess（BSTNode*&
{//对以指针p所指结点为根的二叉树作右平衡旋转处理，本算法结束时，
bf==0）//原本左右子树等高，现因右子树增高而使树增高
bf==1）//原本左子树比右子树高，现左右子树等高
else//原本右子树比左子树高，须作右子树的平衡处理
//p指向*p的右子树根结点
bf==-1）//新结点插入在*p的右孩子的左子树上，要做RR调整
rchild=p1->
lchild=p;
bf==1）//新结点插入在*p的右孩子的左子树上，要做RL调整
rchild=p1;
bf==0）//新结点插在*p2处作为叶子结点的情况
bf==-1）//新结点插在*p2的右子树上的情况
else//新结点插在*p2的左子树上的情况
//仍将p指向新的结点，并置其bf值为0
intInsertAVL（BSTNode*&
b,KeyTypee,int&
{//若在平衡二叉排序树b中不存在和e有相同关键字的结点，则插入一个数据元素为e的新结点，
//并返回1，否则返回0。
若因插入而使二叉排序树失去平衡，则作平衡旋转处理，布尔变量taller
//反映b长高与否
if（b==NULL）//原树为空，插入新结点，树长高，置taller为1
{b=（BSTNode*）malloc（sizeof（BSTNode））;
b->
key=e;
lchild=b->
rchild=NULL;
else
{if（e==b->
key）//树中已存在和e有相同关键字的结点则不插入
{taller=0;
return0;
if（e<
b->
key）//继续在*b的左子树中进行搜索
{if（（InsertAVL（b->
lchild,e,taller））==0）//未插入
if（taller==1）//已插入到*b的左子树中且左子树长高
LeftProcess（b,taller）;
else//继续在*b的右子树中进行搜索
rchild,e,taller））==0）//未插入
if（taller==1）//已插入到*b的右子树中且右子树长高
RightProcess（b,taller）;
return1;
voidDispBSTree（BSTNode*b）
{//以括号表示法输出AVL
if（b!
=NULL）
{printf（"
%d"
b->
key）;
if（b->
lchild!
=NULL||b->
rchild!
{printf（"
（"
）;
DispBSTree（b->
lchild）;
=NULL）printf（"
"
rchild）;
printf（"
）"
voidLeftProcess1（BSTNode*&
p,int&
taller）//在删除结点时进行左处理
{BSTNode*p1,*p2;
bf==1）
bf==0）
else
bf==0）//须作RR调整
bf==-1）//须作RR调整
bf=p->
else//须作RL调整
bf==-1）
voidRightProcess1（BSTNode*&
taller）//在删除结点是进行右处理
bf==0）//须作LL调整
bf==1）//须作LL调整
else//须作LR调整
voidDelete（BSTNode*q,BSTNode*&
r,int&
{//由DeleteAVL调用，用于处理被删结点左右子树均不空的情况
if（r->
rchild==NULL）
{q->
key=r->
key;
q=r;
r=r->
free（q）;
{Delete（q,r->
rchild,taller）;
if（taller==1）
RightProcess1（r,taller）;
intDeleteAVL（BSTNode*&
p,KeyTypex,int&
{//在AVL树中删除关键字为x的结点
intk;
BSTNode*q;
if（p==NULL）
elseif（x<
p->
key）
{k=DeleteAVL（p->
lchild,x,taller）;
LeftProcess1（p,taller）;
returnk;
elseif（x>
rchild,x,taller）;
RightProcess1（p,taller）;
else//找到了关键字为x的结点，由p指向它
{q=p;
rchild==NULL）//被删结点右子树为空
{p=p->
lchild==NULL）//被删结点左子树为空
else//被删结点左右子树均不为空
{Delete（q,q->
lchild,taller）;
LeftProcess1（q,taller）;
p=q;
return1;
voidmain（）
{BSTNode*b=NULL;
inti,j,k;
KeyTypea[]={4,9,0,1,8,6,3,5,2,7},n=10;
创建一棵AVL树:
\n"
for（i=0;
i<
n;
i++）
第%d步，插入%d元素:
"
i+1,a[i]）;
InsertAVL（b,a[i],j）;
DispBSTree（b）;
AVL:
删除结点:
k=8;
删除结点%d:
k）;
DeleteAVL（b,k,j）;
k=2;
\n\n"
升级会员 