平衡二叉树的实现过程

平衡二叉树构建的基本思想就是在构建二叉排序树的过程中，每当插入一个结点，先检查是否因为插入而破坏了树的平衡特性，若是，则找出最小不平衡子树。在保持二叉排序树特性的前提下，调整最小不平衡子树中各结点之间的链接关系，进行相应的旋转，使之成为最新的平衡子树。

二插链表的二插链表结构定义

/*二叉树的二插链表结构*/ typedef struct BiTNode /*结点结构*/ { int data; /*结点数据*/ int bf; /*结点的平衡因子*/ struct BiTNode *lchild, *rchild; /*左右孩子指针*/ }BiTNode,*BiTree;

对以p为根的二叉排序树作右旋处理

void R_Rotate(BiTree *p) { BiTree L; L = (*p)->lchild; /*L指向p的左子树结点*/ (*p)->lchild = L->rchild; L->lchild = (*p); (*p) = L; }

对以p为根的二叉排序树作左旋处理

void L_Rotate(BiTree *P) { BiTree L; L = (*P)->rchild; /* L指向P的左子树根结点 */ (*P)->rchild = L->lchild; /* L的右子树挂接为P的左子树 */ L->lchild = (*P); *P = L; /* P指向新的根结点 */ }

对以指针T所指结点为根的二叉树作左平衡旋转处理

#define LH +1 /* 左高 */ #define EH 0 /* 等高 */ #define RH -1 /* 右高 */ /* 本算法结束时，指针T指向新的根结点 */ void LeftBalance(BiTree *T) { BiTree L, Lr; L = (*T)->lchild; /* L指向T的左子树根结点 */ switch (L->bf) { /* 检查T的左子树的平衡度，并作对应平衡处理 */ case LH: /* 新结点插入在T的左孩子的左子树上。要作单右旋处理 */ (*T)->bf = L->bf = EH; R_Rotate(T); break; case RH: /* 新结点插入在T的左孩子的右子树上。要作双旋处理 */ Lr = L->rchild; /* Lr指向T的左孩子的右子树根 */ switch (Lr->bf) { /* 改动T及其左孩子的平衡因子 */ case LH: (*T)->bf = RH; L->bf = EH; break; case EH: (*T)->bf = L->bf = EH; break; case RH: (*T)->bf = EH; L->bf = LH; break; } Lr->bf = EH; L_Rotate(&(*T)->lchild); /* 对T的左子树作左旋平衡处理 */ R_Rotate(T); /* 对T作右旋平衡处理 */ } }

对以p为根的二叉排序树作左旋处理

void RightBalance(BiTree *T) { BiTree L, Lr; L = (*T)->rchild; /* L指向T的左子树根结点 */ switch (L->bf) { /* 检查T的右子树的平衡度，并作对应平衡处理 */ case RH: /* 新结点插入在T的右孩子的右子树上。要作单左旋处理 */ (*T)->bf = L->bf = EH; L_Rotate(T); break; case LH: /* 新结点插入在T的右孩子的左子树上。要作双旋处理 */ Lr = L->lchild; /* Lr指向T的左孩子的右子树根 */ switch (Lr->bf) { /* 改动T及其左孩子的平衡因子 */ case LH: (*T)->bf = EH; L->bf = RH; break; case EH: (*T)->bf = L->bf = EH; break; case RH: (*T)->bf = LH; L->bf = EH; break; } Lr->bf = EH; L_Rotate(&(*T)->lchild); /* 对T的左子树作左旋平衡处理 */ R_Rotate(T); /* 对T作右旋平衡处理 */ } }

对以p为根的二叉排序树作右旋处理

void RightBalance(BiTree *T) { BiTree L, Lr; L = (*T)->rchild; /* L指向T的左子树根结点 */ switch (L->bf) { /* 检查T的右子树的平衡度，并作对应平衡处理 */ case RH: /* 新结点插入在T的右孩子的右子树上。要作单左旋处理 */ (*T)->bf = L->bf = EH; L_Rotate(T); break; case LH: /* 新结点插入在T的右孩子的左子树上。要作双旋处理 */ Lr = L->lchild; /* Lr指向T的左孩子的右子树根 */ switch (Lr->bf) { /* 改动T及其左孩子的平衡因子 */ case LH: (*T)->bf = EH; L->bf = RH; break; case EH: (*T)->bf = L->bf = EH; break; case RH: (*T)->bf = LH; L->bf = EH; break; } Lr->bf = EH; L_Rotate(&(*T)->lchild); /* 对T的左子树作左旋平衡处理 */ R_Rotate(T); /* 对T作右旋平衡处理 */ } }

若平衡的二叉排序树T中不存在和e有相同关键字的结点，则插入一个数据元素为e的新结点并返回1，否则返回0.若因插入使得二叉排序树失去平衡，则作旋转处理，布尔变量taller反映T长高与否。

int InsertAVL(BiTree *T, int e, bool *taller) { if (!*T) { /*插入新结点，树长高，置taller为TRUE*/ *T = (BiTree)malloc(sizeof(BiTNode)); (*T)->data = e; (*T)->lchild = (*T)->rchild = NULL; (*T)->bf = EH; *taller = true; } else { if (e == (*T)->data) {/*树中已存在和e有相同的关键字的结点则不再插入*/ *taller = false; return false; } if (e < (*T)->data) { /*应继续在左子树中进行搜索插入*/ if (!InsertAVL(&(*T)->lchild, e, taller))/*未插入*/ return false; if(*taller) { 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; } } } else { /*应继续在左子树中进行搜索插入*/ if(!InsertAVL(&(*T)->rchild, e, taller)) /*未插入*/ return false; switch((*T)->bf) { case EH: (*T)->bf=RH; *taller=true; break; case LH: (*T)->bf=TH; *taller=false; break; case RH: RightBalance(T); *taller=false; break; } } } return true; }