参考链接：
http://www.cnblogs.com/hustcat/archive/2008/04/13/1151586.html
《数据结构(C语言版)》p237介绍了平衡二叉树的左平衡算法void LeftBalance(BSTree &T);
对于该算法的理解可以参考p235的图9.13的图例。
备注：
LeftBalance的代码片段：
case EH: T->bf = lc->bf = EH; break;
可以对照9.13的图例的b，当C为新插入节点（Cl=Cr=NULL，Bl=NULL，Ar=NULL），此时B的bf由0->-1，A的bf由1->2，双旋之后A,B,C的bf都为0
完整示例代码：
#include <iostream>
#define LH 1 //左高
#define EH 0 //等高
#define RH -1 //右高
typedef int Status;
typedef struct ElemType {
struct ElemType(int e) : key(e) {}
int key;
}ElemType;
typedef struct BSTNode {
ElemType data;
int bf; //节点的平衡因子
struct BSTNode *lchild, *rchild; //左、右孩子指针
}BSTNode, *BSTree;
void R_Rotate(BSTree &p) {
//对以*p为根的二叉排序树作右旋处理，处理之后p指向新的树根节点，即旋转
//处理之前的左子树的根节点
BSTree lc = p->lchild; //lc指向的*p的左子树根节点
p->lchild = lc->rchild; //lc的右子树挂接为*p的左子树
lc->rchild = p; p = lc; //p指向新的根节点
}//R_Rotate
void L_Rotate(BSTree &p) {
//对以*p为根的二叉排序树作左旋处理，处理之后p指向新的节点，即旋转
//处理之前的右子树的根节点
BSTree rc = p->rchild; //rc指向的*p的右子树的根节点
p->rchild = rc->lchild; //rc的左子树挂接为*p的右子树
rc->lchild = p; p = rc; //p指向新的根节点
}//L_Rotate
void LeftBalance(BSTree &T) {
//对以指针T所指的节点为根的二叉树作左平衡处理，本算法结束时，指针T指向
//新的根节点
BSTree lc = T->lchild; //lc指向*T的左子树根节点
switch (lc->bf) { //检查*T的左子树的平衡度，并作相应的平衡处理
case LH: //新节点插入在*T的左孩子的左子树上，要作单右旋处理
T->bf = lc->bf = EH;
R_Rotate(T);
break;
case RH: //新节点插入在*T的左孩子的右子树上，要作双旋处理
BSTree rd = lc->rchild; //rd指向*T的左孩子的右子树根
switch (rd->bf) { //修改*T及其左孩子的平衡因子
case LH:
T->bf = RH;
lc->bf = EH;
break;
case EH:
T->bf = lc->bf = EH;
break;
case RH:
T->bf = EH;
lc->bf = LH;
break;
} //switch (rd->bf)
rd->bf = EH;
L_Rotate(T->lchild); //对*T的左子树作左旋平衡处理
R_Rotate(T); //对*T作右旋平衡处理
break;
} //switch (lc->bf)
} //LeftBalance
void RightBalance(BSTree &T) {
//对以指针T所指的节点为根的二叉树作右平衡处理，本算法结束时，指针T指向
//新的根节点
BSTree rc = T->rchild; //rd指向*T的右子树根节点
switch (rc->bf) { //检查*T的右子树的平衡度，并作相应的平衡处理
case RH: //新节点插入在*T的右孩子的右子树上，要作单左旋处理
T->bf = rc->bf = EH;
L_Rotate(T);
break;
case LH: //新节点插入在*T的右孩子的左子树上，要作双旋处理
BSTree ld = rc->lchild; //ld指向*T的右孩子的左子树根
switch (ld->bf) { //修改*T及其右孩子的平衡因子
case RH:
T->bf = LH;
rc->bf = EH;
break;
case EH:
T->bf = rc->bf = EH;
break;
case LH:
T->bf = EH;
rc->bf = RH;
break;
} //switch (ld->bf)
ld->bf = EH;
R_Rotate(T->rchild);
L_Rotate(T);
break;
} //switch (rc->bf)
} //RightBalance
Status InsertAVL(BSTree &T, ElemType e, bool &taller) {
//若在平衡的二叉树T中不存在和e有相同关键字的节点，则插入一个数据元素
//为e的新节点，并返回1，否则返回0。若因插入而使二排序树失去平衡，则作平衡
//旋转处理，布尔变量taller反映T长高与否
if (!T) { //插入新节点，树“长高”，置taller为TRUE
T = (BSTree)malloc(sizeof(BSTNode));
T->data = e;
T->lchild = T->rchild = NULL;
T->bf = EH;
taller = true;
}
else {
if (e.key == T->data.key) { //树中已存在和e有相同关键字的节点
taller = false; //则不插入
return 0;
}
if (e.key < T->data.key) { //应继续在*T的左子树中进行搜索
if (!InsertAVL(T->lchild, e, taller))
return 0; //未插入
if (taller) { //已插入到*T的左子树中且左子树“长高”
switch (T->bf) { //检查*T的平衡度
case LH: //原本左子树比右子树高，需要作左平衡处理
LeftBalance(T);
taller = false;
break;
case EH: //原本左、右子树登高，现因左子树增高而使树增高
T->bf = LH;
taller = true;
break;
case RH: //原本右子树比左子树高，现左、右子树等高
T->bf = EH;
taller = false;
break;
} //switch(T->bf)
} //if(taller)
}//if
else { //应继续在*T的右子树中进行搜索
if (!InsertAVL(T->rchild, e, taller))
return 0; //未插入
if (taller) { //已插入到*T的右子树并且右子树长高
switch (T->bf) { //检查*T的平衡度
case LH: //原本左子树比右子树高，现左、右子树等高
T->bf = EH; taller = false;
break;
case EH: //原本左、右子树等高，现因右子树增高而使树增高
T->bf = RH; taller = true;
break;
case RH: //原本右子树比左子树高，需要作右平衡处理
RightBalance(T); taller = false;
break;
} //switch(T->bf)
} //if(taller)
} //else
} //else
return 1;
} //InsertAVL
void InOrderTraverse(BSTree root) { //中序遍历
if (root) {
InOrderTraverse(root->lchild);
std::cout << root->data.key << ", ";
InOrderTraverse(root->rchild);
}
}
int main()
{
BSTree root = NULL;
BSTree r;
bool taller = false;
int array[] = {13,24,37,90,53};
for (int i = 0; i < 5; ++i) {
InsertAVL(root, array[i], taller);
}
std::cout << "inorder travese..." << std::endl;
InOrderTraverse(root);
return 0;
}
输出结果：
inorder travese...
13, 24, 37, 53, 90, Press any key to continue