BＳTNode＊ｐ１,＊p2;
if(p->bｆ=＝0)/／原本左右子树等高,现因左子树增高而使树增高
{p-＞bf＝１;
taller=1;
}
eｌse if(p->bf==-１)//原本右子树比左子树高,现左右子树等高
{p－＞bf=0;
ｔaller=0;
｝
eｌｓe//原本左子树比右子树高，须作左子树的平衡处理
reｔｕrn０;
iｆ（tallｅr==1)//已插入到*b的左子树中且左子树长高
Le（b,taｌler);
}
else//继续在*b的右子树中进行搜索
{if（(InsｅrtAＶL(b->rcｈild,ｅ，ｔａller)）＝=0)/／未插入
return0；
iｆ(talleｒ=＝1)//已插入到*b的右子树中且右子树长高
平衡二叉树操作的演示
———————————————————————————————— 作者：
———————————————————————————————— 日期：
＃include<stdio.h＞
#include<mａlｌoc.h>
tｙpedef int KeｙＴyｐe；//定义关键字类型
ｔｙpｅdｅf structｎodｅ//记录类型
{p2=p1->lｃhild;
ｐ1->lchilｄ＝p2->rcｈild;
ｐ2->ｒcｈｉld=p1;
p->rchild=p2->ｌchilｄ;
p2->lｃｈilｄ=p;
if(p２->bf==0)//新结点插在＊ｐ２处作为叶子结点的情况
ﻩ p->bf＝p1->bｆ=0;
elseif(ｐ2->ｂｆ==-1)//新结点插在*p2的右子树上的情况
{p１=p->rｃhild;／/p指向*ｐ的右子树根结点
if(p1－>ｂf＝＝-1)／/新结点插入在*p的右孩子的左子树上,要做RR调整
{p－>rchild=p１－>ｌcｈiｌd;
p1-＞ｌｃｈiｌd＝p;
p-＞ｂf=ｐ1-＞bｆ=0;
p=p1;
｝
elｓeif（ｐ１－>bf＝＝1）//新结点插入在*p的右孩子的左子树上，要做RＬ调整
{p2=p1->rｃhild;
ｐ1－>rｃhilｄ=p2->lcｈild；
ｐ2->ｌｃhiｌd=p1；
p－>lｃhiｌｄ=p2->ｒchiｌd;
p２－>ｒchilｄ＝p;
if(ｐ２->ｂf＝=０)//新结点插入在*ｐ2处作为叶子结点的情况
ﻩp->ｂf＝p1->bf＝0;
eｌseｉｆ(ｐ２->ｂf==1)//新结点插在*ｐ2的左子树上的情况
{／/若在平衡二叉排序树b中不存在和ｅ有相同关键字的结点，则插入一个数据元素为e的新结点,
／/并返回1,否则返回０。若因插入而使二叉排序树失去平衡，则作平衡旋转处理，布尔变量talｌｅr
／/反映b长高与否
if(b==NULＬ)//原树为空,插入新结点,树长高，置taｌleｒ为１
{b=(ＢSTNｏdｅ*)malloc（sｉzｅof(BSTＮｏｄｅ）)；
{ｐ１=p－＞lcｈiｌd;／/p指向*p的左子树根节点
if（p1->ｂｆ==1)/／新结点插入在*p的左孩子的左子树上，要做LL调整
{p-＞ｌcｈｉld＝p1－＞rchilｄ；
p1-＞rchｉld＝p;
p－>bf=ｐ1->bｆ=0;
p=p1;
}
eｌse if(p１－＞ｂf＝=-1）//新结点插入在*p的左孩子的右子树上，要做LR调整
{KeyTypｅｋｅy;//关键字项
iｎt bf;//平衡因子
ｓtrｕcｔnｏｄe *lｃhild，*rｃhｉｌd;／／左右孩子指针
}BＳTNodｅ;
voidＬe(BSTNode *&ｐ,ｉnｔ＆taller）
{/／对以指针p所指结点为根的二叉树作左平衡旋转处理,本算法结束时,
//指针p指向新的根结点
ｂ-＞keｙ=ｅ;
ｂ->lchｉlｄ＝ｂ-＞rｃhｉｌd＝NULL;
b－>bf=0;
tallｅr=1；
}
ｅlse
｛if(e==b->kｅy）//树中已存在和ｅ有相同关键字的结点则不插入
{taller=０;
rｅｔurn 0;
}
ｉf(e<b-＞keｙ）//继续在＊ｂ的左子树中进行搜索
{iｆ((InsertAVL(b－>lchild，e,taｌlｅr）)==0）//未插入
iｆ（p->bf==１）
{p->ｂｆ=0;
taｌler=1;
／/指针ｐ指向新的根结点
ＢSＴＮodｅ＊p1,*p2；
if(p->bｆ==0)／/原本左右子树等高，现因右子树增高而使树增高
{ｐ->bf=-1；
ｔaller＝1;
｝
eｌse if(p－>ｂf==1)／/原本左子树比右子树高，现左右子树等高
｛p->bf=0;
tallｅr=0;
}
ｅlse／/原本右子树比左子树高，须作右子树的平衡处理
RiｇhtＰrocess(b,taｌleｒ);
}
｝
retuｒn1;
}
void DiｓpＢＳTreｅ(BSTNode *b)
｛//以括号表示法输出AVL
if(b!=NULL）
{pｒinｔf("%d",b－>keｙ);
iｆ(ｂ-＞ｌchild!=NUＬL||b-＞rｃhild！=NＵＬL）
{printｆ(＂(");
DispBSＴrｅe（b->lchｉld);
if(b->rcｈilｄ！=NULＬ)printf(",");
ＤｉspBＳTreｅ(b->ｒｃhｉld);
ｐrinｔｆ(")＂);
}
}
｝
void Lｅ（ＢSTＮｏdｅ*&p，iｎｔ&ｔalleｒ)／/在删除结点时进行左处理
{ＢSＴNoｄe *p1,*p２;
{p１->ｂｆ=０;
p->bｆ＝１；
}
elsｅ／/新结点插在＊的左子树上的情况
{p1->ｂf＝-1;
p->bf=0;
}
p＝p2;
p->bf=０;/／仍将p指向新的结点，并置其bｆ值为０
}
tａller=0;
}
}
iｎt IｎｓertAＶL（BＳTNode*&ｂ,ＫeｙTyｐe e,iｎt&tallｅr)
{p1－>ｂf=０;
ｐ－>bｆ＝-1;
}
elｓｅ／/新结点插在＊p２的右子树上的情况
{p1-＞bf=1;
p－＞ｂf＝0;
}
p=ｐ2;
p-＞bf=０；/／仍将p指向新的根结点，并置其bf值为０
}
taｌleｒ=０;
｝
}
vｏｉdRighｔProcess（ＢSTNoｄe *＆p,int &tallｅr)
{//对以指针p所指结点为根的二叉树作右平衡旋转处理,本算法结束时,