pivotloc=Part_QuickSort（L2,low,high）;
Quick_Sort（L2,low,pivotloc-1）;
Quick_Sort（L2,pivotloc+1,high）;
}//endif
returnL2;
}
voidBubble_Sort（SqListL）
{
inti,j,temp;
for（i=1;i<=L.length;i++）
{
for（j=1;j<=L.length-1;j++）
{
if（L.data[j]>L.data[j+1]）
{
temp=L.data[j+1];
L.data[j+1]=L.data[j];
L.data[j]=temp;
}
}
}
for（i=1;i<=L.length;i++）{
printf（"%d\t",L.data[i]）;
}
putchar（'\n'）;
}
//右旋处理，即LL调整
voidR_Rotate（BiTree*p）
{
BiTreeL;
L=（*p）->lchild;
（*p）->lchild=L->rchild;
L->rchild=*p;
*p=L;
}
//左旋处理，即RR调整
voidL_Rotate（BiTree*p）
{
BiTreeR;
R=（*p）->rchild;
（*p）->rchild=R->lchild;
R->lchild=*p;
*p=R;
}
//左平衡旋转处理，包括LL和LR调整
voidLeftBalance（BiTree*T）
{
BiTreeL,Lr;
L=（*T）->lchild;
switch（L->bf）
{
case1:
//新结点插入在T的左孩子的左子树上，为LL型，作右旋处理即LL调整
（*T）->bf=L->bf=0;
R_Rotate（T）;
break;
case-1:
//新结点插入在T的左孩子的右子树上，为LR型，作双旋处理
Lr=L->rchild;
switch（Lr->bf）
{
case1:
（*T）->bf=-1;
L->bf=0;
break;
case0:
（*T）->bf=L->bf=0;
break;
case-1:
（*T）->bf=0;
L->bf=1;
break;
}
Lr->bf=0;
L_Rotate（&（*T）->lchild）;//先对T的左子树进行左旋处理即RR调整
R_Rotate（T）;//再对T进行右旋处理即LL调整
}
}
//右平衡旋转处理，包括RR和RL调整
voidRightBalance（BiTree*T）
{
BiTreeR,Rl;
R=（*T）->rchild;
switch（R->bf）
{
case-1:
//新结点插入在T的右孩子的右子树上，为RR型，作左旋处理即RR调整
（*T）->bf=R->bf=0;
L_Rotate（T）;
break;
case1:
//新结点插入在T的右孩子的左子树上，为RL型，作双旋处理
Rl=R->lchild;
switch（Rl->bf）
{
case1:
（*T）->bf=0;
R->bf=-1;
break;
case0:
（*T）->bf=R->bf=0;
break;
case-1:
（*T）->bf=1;
R->bf=0;
break;
}
Rl->bf=0;
R_Rotate（&（*T）->rchild）;//先对T的左子树进行左旋即RR调整
L_Rotate（T）;//再对T进行右旋即LL调整
}
}
//若在平衡二叉树T中不存在和e具有相同数据的结点，则插入数据元素为e的新结点，
//若因插入使二叉排序树失去平衡，则要作平衡调整，
//布尔变量taller表示T的深度是否增加，TRUE表示增加，FALSE表示没有增加
intInsertAVL（BiTree*T,inte,int*taller）
{
if（!
*T）
{
*T=（BiTree）malloc（sizeof（BiTNode））;
（*T）->data=e;
（*T）->lchild=（*T）->rchild=NULL;
（*T）->bf=0;
*taller=TRUE;
}
else
{
//树中已有和e具有相同数据的结点，则不再插入
if（e==（*T）->data）
{
*taller=FALSE;
returnFALSE;
}
if（e<（*T）->data）//继续在T的左子树进行搜索
{
if（!
InsertAVL（&（*T）->lchild,e,taller））//InsertAVL（&（*T）->lchild,e,taller）得到的是T的左孩子结点（*T）->lchild的data,bf等相关信息
{
returnFALSE;
}
//如果e已插入到T的左子树中，且左子树深度增加
if（*taller）
{
switch（（*T）->bf）//检查T的平衡因子
{
case1:
//原本左子树比右子树高，再加上此结点，导致不平衡，需要作LL或LR调整
LeftBalance（T）;
*taller=FALSE;
break;
case0:
//原本左右子树等高，再加上此结点，左子树增高
（*T）->bf=1;
*taller=TRUE;
break;
case-1:
//原本右子树比左子树高，再加上此结点，左右子树变为等高
（*T）->bf=0;
*taller=FALSE;
break;
}
}
}
else//在T的右子树进行搜索
{
if（!
InsertAVL（&（*T）->rchild,e,taller））
{
returnFALSE;
}
if（*taller）
{
switch（（*T）->bf）
{
case1:
//原先左子树比右子树高，现在左右子树等高
（*T）->bf=0;
*taller=FALSE;
break;
case0:
//原先左右子树等高，现在右子树增高
（*T）->bf=-1;
*taller=TRUE;
break;
case-1:
//原先右子树比左子树高，现在再加上此结点，导致不平衡，需要作RR或RL调整
RightBalance（T）;
*taller=FALSE;
break;
}
}
}
}
returnTRUE;
}
BiTreeCreateAVL（SqListL）
{
inti;
BiTreeT=NULL;
inttaller;
for（i=1;i{
InsertAVL（&T,L.data[i],&taller）;
}
returnT;
}
intInOrderTraverse（BiTreeT）//中序遍历算法//
{
if（T==NULL）return0;
else
{
InOrderTraverse（T->lchild）;//递归遍历左子树//
printf（"%d\t",T->data）;//访问根节点//
InOrderTraverse（T->rchild）;//递归遍历右子树//
}
}
voidmain（）{
inti;
SqListL;
L.length=0;
BiTreeT;
for（i=1;iscanf_s（"%d",&L.data[i]）;
if（getchar（）=='#'）break;
L.length++;
}
T=CreateAVL（L）;//建立二叉排序平衡树//
InOrderTraverse（T）;
putchar（'\n'）;
Bubble_Sort（L）;
Quick_Sort（L,1,L.length）;
for（i=1;i<=L.length;i++）{
printf（"%d\t",L.data[i]）;
}
putchar（'\n'）;
}
升级会员 