平衡二叉树的定义：
平衡二叉树（balanced binary tree)
创新互联是一家集网站建设,焦作企业网站建设,焦作品牌网站建设,网站定制,焦作网站建设报价,网络营销,网络优化,
焦作网站推广为一体的创新建站企业，帮助传统企业提升企业形象加强企业竞争力。可充分满足这一群体相比中小企业更为丰富、高端、多元的互联网需求。同时我们时刻保持专业、时尚、前沿，时刻以成就客户成长自我，坚持不断学习、思考、沉淀、净化自己，让我们为更多的企业打造出实用型网站。
又称AVL树（Adelson-Velskii and Landis)
一棵平衡二叉树或者是空树，或者是具有下列性质的二叉排序树：
１，左子树与右子树的高度之差的绝对值小于等于１；
２，左子树和右子树也是平衡二叉排序树．
为了方便起见，给每个结点附加一个数字，给出该结点左子树与右子树的高度差．这个数字称为结点的平衡因子（ＢＦ）．
平衡因子 ＝ 结点左子树的高度 － 结点右子树的高度
根据平衡二叉树的定义，平衡二叉树上所有结点的平衡因子只能是-1,0,或1.
例：
对于一棵有n个结点的AVL树，其高度保持在O(log2^n)数量级
失衡二叉排序树的分析与调整
当我们在一个平衡二叉排序树上插入一个结点时，有可能导致失衡，不再是一个平衡二叉排序树，即出现平衡因子绝对值大于１的结点．
如果在一棵ＡＶＬ树中插入一个新结点后造成失衡，则必须重新调整树的结构，使之恢复平衡
平衡调整的四种类型：
具体的调整为：
调整原则为：１）降低高度 ２）保持二叉排序树的性质
规律：按照二叉排序树的性质，挑选３个值的中间值作为调整后的根结点，最小值为根结点的左孩子，大值为根结点的右孩子．
例：ＬＬ型
例：ＲＬ型
ＲＲ型和ＬＲ型和上面类似，就不多介绍了，总之，一个总的原则，就是调整后必须保证１）降低高度 ２）保持二叉排序树的性质
还是那句话，只要知道调整类型，就可以确定Ａ，Ｂ，Ｃ三个顶点的位置，中间值为根结点，大值为右孩子，最小值为左孩子，确定好后，别的结点就很容易根据二叉排序树的特点找到各自的位置，网上看了很多左旋，右旋，左右旋，头都晕．只要知道这个规律，不用管什么旋，也不用死记硬背还怕忘．随时碰到随时都可以马上上手．
接下来用代码来实现一个平衡二叉树的建立：
例题：输入关键字序列(16,3,7,11,9,26,18,14,15),创建一个平衡二叉树
第一个方法是给结点加了一个parent域，方便查找，不过感觉挺麻烦的，每次调整都要给parent域赋值，不过这个代码在有多个失衡点时会挑选最小代价树的失衡点，不管失衡点是不是根结点都是通用的
#include#include#define MAXINT 10000
#define MAXSIZE 10
typedef struct BBTnode{
int data;//这里为了方便，直接用int,没有用结构体．
int balance;//平衡因子
struct BBTnode* lchild;
struct BBTnode* rchild;
struct BBTnode* parent;
}BBTnode,*BBTree;
BBTree MinBalance;//最小失衡结点地址
int k = 0;
int i = 0;
BBTree SearchBBT(BBTree T, int m, char* arr)//计算从某点出发，到指定数字的路径
{
if(!T || T->data == m)
{
return T;
}
else if(m< T->data)
{
arr[k++] = 'L';
return SearchBBT(T->lchild, m, arr);
}
else
{
arr[k++] = 'R';
return SearchBBT(T->rchild, m, arr);
}
}
int CountNodes(BBTree T)//计算树中的结点数，比较失衡结点树的大小，选择较小的树（当不止一个失衡点时）
{
if(!T)
{
return 0;
}
return CountNodes(T->lchild) + CountNodes(T->rchild) + 1;
}
int DepthBBT(BBTree T)//计算平衡二叉树的深度
{
int m, n;
if(!T)
{
return 0;
}
else
{
m = DepthBBT(T->lchild) + 1;//左边的深度
n = DepthBBT(T->rchild) + 1;//右边的深度
}
if(m >n)return m;//取较大值
else return n;
}
void OrderBBT(BBTree* T, BBTree Unbalance[MAXSIZE])//中序遍历二叉排序树,更新各结点平衡因子，把所有失衡点存储起来
{
if(*T == NULL)return;
else
{
OrderBBT(&(*T)->lchild,Unbalance);
(*T)->balance = abs(DepthBBT((*T)->lchild) - DepthBBT((*T)->rchild));//计算该结点平衡因子，左边深度－右边深度再取绝对值
if((*T)->balance>1)
{
Unbalance[i++] = *T;
}
OrderBBT(&(*T)->rchild,Unbalance);
}
}
void AddBBT(BBTree* T, int m, BBTree parent)//二叉排序树的递归添加元素
{
if(!(*T))
{
*T = malloc(sizeof(BBTnode));
(*T)->data = m;
(*T)->lchild = NULL;
(*T)->rchild = NULL;
(*T)->balance = 0;
(*T)->parent = parent;
}
else if(m< (*T)->data)
{
AddBBT(&(*T)->lchild, m, *T);
}
else
{
AddBBT(&(*T)->rchild, m, *T);
}
}
void creatBBT(BBTree* T)//创建平衡二叉排序树，实际上就是给一个空树添加元素
{
int input = 1;
BBTree A,B,C;//定义图示中表示的三个顶点
while(input)
{
printf("请依次输入数字序列，输入完毕以0结束:>");
scanf("%d",&input);
if(input == 0)break;
AddBBT(T, input,*T);
MinBalance = 0;//重置最小平衡因子为空
int temp = MAXINT;
int j;
BBTree Unbalance[MAXSIZE] = {0};//定义一个失衡结点数组，用来存放当前树中存在的失衡结点
i = 0;//重置数组Unbalance的下标为0开始
OrderBBT(T,Unbalance);//更新平衡因子，得到平衡因子数组Unbalance
for(j = 0; j< MAXSIZE; j++)//从数组Unbalance找出最小失衡因子，并返回该地址到MinBalance
{
if(!Unbalance[j])break;
if(CountNodes(Unbalance[j])< temp)
{
temp = CountNodes(Unbalance[j]);
MinBalance = Unbalance[j];
}
}
char ChoiceType[MAXSIZE] = {0};//选择调整类型的数组（ＬＬ，ＲＲ．ＬＲ，ＲＬ）
k = 0;//重置SearchBBT里的k变量
SearchBBT(MinBalance, input, ChoiceType);//得到从失衡点出发到添加结点间的路径
if(ChoiceType[0] == 'L' && ChoiceType[1] == 'L')//ＬＬ型调整
{
A = MinBalance;
B = MinBalance->lchild;
C = MinBalance->lchild->lchild;
if(A->parent)//如果这个失衡点不是根结点
{
if(A->data< A->parent->data)A->parent->lchild = B;
else A->parent->rchild = B;
}
else *T = B;
A->lchild = B->rchild;
if(B->rchild)B->rchild->parent = A;
B->rchild = A;
B->parent = A->parent;
A->parent = B;
}
else if(ChoiceType[0] == 'R' && ChoiceType[1] == 'R')//ＲＲ型调整
{
A = MinBalance;
B = MinBalance->rchild;
C = MinBalance->rchild->rchild;
if(A->parent)//如果这个失衡点不是根结点
{
if(A->data< A->parent->data)A->parent->lchild = A->rchild;
else A->parent->rchild = A->rchild;
}
else *T = B;//如果是根结点，那么根结点变成调整后的根结点
A->rchild = B->lchild;
if(B->lchild)B->lchild->parent = A;
B->lchild = A;
B->parent = A->parent;
A->parent = B;
}
else if(ChoiceType[0] == 'L' && ChoiceType[1] == 'R')//ＬＲ型调整
{
A = MinBalance;
B = MinBalance->lchild;
C = MinBalance->lchild->rchild;
if(A->parent)//如果这个失衡点不是根结点
{
if(A->data< A->parent->data)A->parent->lchild = C;
else A->parent->rchild = C;
}
else *T = C;
B->rchild = C->lchild;
if(C->lchild)C->lchild->parent =B;
A->lchild = C->rchild;
if(C->rchild)C->rchild->parent = A;
C->rchild = A;
C->lchild = B;
C->parent = A->parent;
A->parent = C;
B->parent = C;
}
else if(ChoiceType[0] == 'R' && ChoiceType[1] == 'L')//ＲＬ型调整
{
A = MinBalance;
B = MinBalance->rchild;
C = MinBalance->rchild->lchild;
if(A->parent)//如果这个失衡点不是根结点
{
if(A->data< A->parent->data)A->parent->lchild = C;
else A->parent->rchild = C;
}
else *T = C;
A->rchild = C->lchild;
if(C->lchild)C->lchild->parent = A;
B->lchild = C->rchild;
if(C->rchild)C->rchild->parent = B;
C->lchild = A;
C->rchild = B;
C->parent = A->parent;
A->parent = C;
B->parent = C;
}
}
BBTree arr[MAXSIZE] = {0};//这个只为为了下面这个OrderBBT函数能运行，没有别的意义
OrderBBT(T,arr);
}
void printBBT(BBTree T)//中序输出二叉排序树，得到的是一个递增数列
{
if(T == NULL)return;
else
{
printBBT(T->lchild);
printf("%d号结点平衡因子为%d\n",T->data,T->balance);
printBBT(T->rchild);
}
}
int main()
{
BBTree T = NULL;//定义二叉排序树Ｔ
creatBBT(&T);//创建二叉排序树
printBBT(T);//输出创建好的二叉排序树
return 0;
}
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
文章题目：数据结构之平衡二叉树详解-创新互联
链接地址：
http://cdkjz.cn/article/dchohd.html
