平衡二叉树

平衡⼆叉排序树（完整案例详解及完整C代码实现）

写在前⾯：博主是⼀位普普通通的19届双⾮软⼯在读⽣，平时最⼤的爱好就是听听歌，逛逛B站。博主很喜欢的⼀句话花开堪折直须

折，莫待⽆花空折枝：博主的理解是头⼀次为⼈，就应该做⾃⼰想做的事，做⾃⼰不后悔的事，做⾃⼰以后不会留有遗憾的事，做⾃⼰

觉得有意义的事，不浪费这⼤好的青春年华。博主写博客⽬的是记录所学到的知识并⽅便⾃⼰复习，在记录知识的同时获得部分浏览

量，得到更多⼈的认可，满⾜⼩⼩的成就感，同时在写博客的途中结交更多志同道合的朋友，让⾃⼰在技术的路上并不孤单。

⽬录:

1.平衡⼆叉树简介

平衡⼆叉树，⼜称为AVL树。实际上就是遵循以下两个特点的⼆叉树：

每棵⼦树中的左⼦树和右⼦树的深度差不能超过1；

⼆叉树中每棵⼦树都要求是平衡⼆叉树；

其实就是在⼆叉树的基础上，若树中每棵⼦树都满⾜其左⼦树和右⼦树的深度差都不超过1，则这棵⼆叉树就是平衡⼆叉树。

如下图所⽰，其中（a）的两棵⼆叉树中由于各个结点的平衡因⼦数的绝对值都不超过1，所以（a）中两棵⼆叉树都是平衡⼆叉树；⽽

（b）的两棵⼆叉树中有结点的平衡因⼦数的绝对值超过1，所以都不是平衡⼆叉树。

平衡因⼦：每个结点都有其各⾃的平衡因⼦，表⽰的就是其左⼦树深度同右⼦树深度的差。平衡⼆叉树中各结点平衡因⼦的取值只可

能是：0、1和-1。

2.⼆叉排序树转换平衡为平衡⼆叉树

为了排除动态查找表中不同的数据排列⽅式对算法性能的影响，需要考虑在不会破坏⼆叉排序树本⾝结构的前提下，将⼆叉排序树转化为平

衡⼆叉树。

例如，使⽤上⼀节的算法在对查找表{13，24，37，90，53}构建⼆叉排序树时，当插⼊13和24时，⼆叉排序树此时还是平衡⼆叉

树：

当继续插⼊37时，⽣成的⼆叉排序树如下图（a），平衡⼆叉树的结构被破坏，此时只需要对⼆叉排序树做“旋转”操作（如下图

（b）），即整棵树以结点24为根结点，⼆叉排序树的结构没有破坏，同时将该树转化为了平衡⼆叉树：

当⼆叉排序树的平衡性被打破时，就如同扁担的两头出现了⼀头重⼀头轻的现象，如下图（a）所⽰，此时只需要改变扁担的⽀撑点（树的

树根），就能使其重新归为平衡。实际上图b中的（b）是对（a）的⼆叉树做了⼀个向左逆时针旋转的操作。

继续插⼊90和53后，⼆叉排序树如下图（a）所⽰，导致⼆叉树中结点24和37的平衡因⼦的绝对值⼤于1，整棵树的平衡被打破。

此时，需要做两步操作：

1.如下图（b）所⽰，将结点53和90整体向右顺时针旋转，使本该以90为根结点的⼦树改为以结点53为根结点；

2.如下图（c）所⽰，将以结点37为根结点的⼦树向左逆时针旋转，使本该以37为根结点的⼦树，改为以结点53为根结点；

做完以上操作，即完成了由不平衡的⼆叉排序树转变为平衡⼆叉树。

3.不平衡因⼦的四种情况

1.单向右旋平衡处理：若由于结点a的左⼦树为根结点的左⼦树上插⼊结点，导致结点a的平衡因⼦由1增⾄2，致使以a为根结点的⼦

树失去平衡，则只需进⾏⼀次向右的顺时针旋转，如下图这种情况：

2.单向左旋平衡处理：如果由于结点a的右⼦树为根结点的右⼦树上插⼊结点，导致结点a的平衡因⼦由-1变为-2，则以a为根结点的⼦

树需要进⾏⼀次向左的逆时针旋转，如下图这种情况：

3.双向旋转（先左后右）平衡处理：如果由于结点a的左⼦树为根结点的右⼦树上插⼊结点，导致结点a平衡因⼦由1增⾄2，致使以a

为根结点的⼦树失去平衡，则需要进⾏两次旋转操作，如下图这种情况：

上图中插⼊结点也可以为结点C的右孩⼦，则（b）中插⼊结点的位置还是结点C右孩⼦，（c）中插⼊结点的位置为结点A的左孩

⼦。

4.双向旋转（先右后左）平衡处理：如果由于结点a的右⼦树为根结点的左⼦树上插⼊结点，导致结点a平衡因⼦由-1变为-2，致使以a

为根结点的⼦树失去平衡，则需要进⾏两次旋转（先右旋后左旋）操作，如下图这种情况：

上图中插⼊结点也可以为结点C的右孩⼦，则（b）中插⼊结点的位置改为结点B的左孩⼦，（c）中插⼊结点的位置为结点B的左

孩⼦

4.构建平衡⼆叉树的代码实现

#include

#include

//分别定义平衡因⼦数

#defineLH+1

#defineEH0

#defineRH-1

typedefintElemType;

typedefenum{false,true}bool;

//定义⼆叉排序树

typedefstructBSTNode{

ElemTypedata;

intbf;//balanceflag

structBSTNode*lchild,*rchild;

}*BSTree,BSTNode;

//对以p为根结点的⼆叉树做右旋处理，令p指针指向新的树根结点

voidR_Rotate(BSTree*p)

{

//借助⽂章中的图5所⽰加以理解，其中结点A为p指针指向的根结点

BSTreelc=(*p)->lchild;

(*p)->lchild=lc->rchild;

lc->rchild=*p;

*p=lc;

}

对以p为根结点的⼆叉树做左旋处理，令p指针指向新的树根结点

voidL_Rotate(BSTree*p)

{

//借助⽂章中的图6所⽰加以理解，其中结点A为p指针指向的根结点

BSTreerc=(*p)->rchild;

(*p)->rchild=rc->lchild;

rc->lchild=*p;

*p=rc;

}

//对以指针T所指向结点为根结点的⼆叉树作左⼦树的平衡处理，令指针T指向新的根结点

voidLeftBalance(BSTree*T)

{

BSTreelc,rd;

lc=(*T)->lchild;

//查看以T的左⼦树为根结点的⼦树，失去平衡的原因，如果bf值为1，则说明添加在左⼦树为根结点的左⼦树中，需要对其进⾏右旋处理；反之，如果bf

值为-1，说明添加在以左⼦树为根结点的右⼦树中，需要进⾏双向先左旋后右旋的处理

switch(lc->bf)

{

caseLH:

(*T)->bf=lc->bf=EH;

R_Rotate(T);

break;

caseRH:

rd=lc->rchild;

switch(rd->bf)

{

caseLH:

(*T)->bf=RH;

lc->bf=EH;

break;

caseEH:

(*T)->bf=lc->bf=EH;

break;

caseRH:

(*T)->bf=EH;

lc->bf=LH;

break;

}

rd->bf=EH;

L_Rotate(&(*T)->lchild);

R_Rotate(T);

break;

}

}

//右⼦树的平衡处理同左⼦树的平衡处理完全类似

voidRightBalance(BSTree*T)

{

BSTreelc,rd;

lc=(*T)->rchild;

switch(lc->bf)

{

caseRH:

(*T)->bf=lc->bf=EH;

L_Rotate(T);

break;

caseLH:

rd=lc->lchild;

switch(rd->bf)

{

caseLH:

(*T)->bf=EH;

lc->bf=RH;

break;

caseEH:

(*T)->bf=lc->bf=EH;

break;

caseRH:

(*T)->bf=EH;

lc->bf=LH;

break;

}

rd->bf=EH;

R_Rotate(&(*T)->rchild);

L_Rotate(T);

break;

}

}

intInsertAVL(BSTree*T,ElemTypee,bool*taller)

{

//如果本⾝为空树，则直接添加e为根结点

if((*T)==NULL)

{

(*T)=(BSTree)malloc(sizeof(BSTNode));

(*T)->bf=EH;

(*T)->data=e;

(*T)->lchild=NULL;

(*T)->rchild=NULL;

*taller=true;

}

//如果⼆叉排序树中已经存在e，则不做任何处理

elseif(e==(*T)->data)

{

*taller=false;

return0;

}

//如果e⼩于结点T的数据域，则插⼊到T的左⼦树中

elseif(e<(*T)->data)

{

//如果插⼊过程，不会影响树本⾝的平衡，则直接结束

if(!InsertAVL(&(*T)->lchild,e,taller))

return0;

//判断插⼊过程是否会导致整棵树的深度+1

if(*taller)

{

//判断根结点T的平衡因⼦是多少，由于是在其左⼦树添加新结点的过程中导致失去平衡，所以当T结点的平衡因⼦本⾝为1时，需要进⾏左⼦树的平

衡处理，否则更新树中各结点的平衡因⼦数

switch((*T)->bf)

{

caseLH:

LeftBalance(T);

*taller=false;

break;

caseEH:

(*T)->bf=LH;

*taller=true;

break;

caseRH:

(*T)->bf=EH;

*taller=false;

break;

}

}

}

//同样，当e>T->data时，需要插⼊到以T为根结点的树的右⼦树中，同样需要做和以上同样的操作

else

{

if(!InsertAVL(&(*T)->rchild,e,taller))

return0;

if(*taller)

{

switch((*T)->bf)

{

caseLH:

(*T)->bf=EH;

*taller=false;

break;

caseEH:

(*T)->bf=RH;

*taller=true;

break;

caseRH:

RightBalance(T);

*taller=false;

break;

}

}

}

return1;

}

//判断现有平衡⼆叉树中是否已经具有数据域为e的结点

boolFindNode(BSTreeroot,ElemTypee,BSTree*pos)

{

BSTreept=root;

(*pos)=NULL;

while(pt)

{

if(pt->data==e)

{

//找到节点，pos指向该节点并返回true

(*pos)=pt;

returntrue;

}

elseif(pt->data>e)

{

pt=pt->lchild;

}

else

pt=pt->rchild;

}

returnfalse;

}

//中序遍历平衡⼆叉树

voidInorderTra(BSTreeroot)

{

if(root->lchild)

InorderTra(root->lchild);

printf("%d",root->data);

if(root->rchild)

InorderTra(root->rchild);

}

intmain()

{

inti,nArr[]={1,23,45,34,98,9,4,35,23};

BSTreeroot=NULL,pos;

booltaller;

//⽤nArr查找表构建平衡⼆叉树（不断插⼊数据的过程）

for(i=0;i<9;i++)

{

InsertAVL(&root,nArr[i],&taller);

}

//中序遍历输出

InorderTra(root);

//判断平衡⼆叉树中是否含有数据域为103的数据

if(FindNode(root,103,&pos))

printf("n%dn",pos->data);

else

printf("nNotfindthisNoden");

return0;

}

本篇博客转载