#define LH 1
#define EH 0
#define RH -1
typedef struct BiTNode
{
int data;
int bf;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
void R_Rotate(BiTree*p)
{
BiTree L;
L=(*p)->lchild;
(*p)->lchild=L->rchild;
L->rchild=(*p);
(*p)=L;
}
void L_Rotate(BiTree*p)
{
BiTree L;
L=(*p)->rchild;
(*p)->rchild=L->rchild;
L->lchild=(*p);
(*p)=L;
}
void LeftBalance(BiTree *T) //此处T为不平衡点
{
BiTree L,Lr; //L为毗邻T的左孩子,Lr为毗邻L的右孩子
L=(*T)->lchild;
switch(L->bf) //这里L->bf不可能为EH,因为是先为L连接一个孩子结点,再判断L->bf。续
//而L的双亲T为不平衡点,若L->bf=EH,则L结点连接一个孩子结点之前T结点已不平衡,续
//或者L结点连接一个孩子结点之前T结点平衡,则L连接一个孩子之后T仍平衡,这时L->bf=EH,而本函数中T不可能平衡。
{
case LH:
(*T)->bf=L->bf=EH; //右旋处理T节点之后的最终结果
R_Rotate(T);
break;
case RH:
Lr=L->rchild;
switch(Lr->bf)
{
case LH:
(*T)->bf=RH; //先左旋处理L、后右旋处理T节点之后的最终结果
L->bf=EH;
break;
case EH:
(*T)->bf=L->bf=EH; //先左旋处理L、后右旋处理T节点之后的最终结果
break;
case RH:
(*T)->bf=EH; //先左旋处理L、后右旋处理T节点之后的最终结果
L->bf=LH;
break;
}
Lr->bf=EH; //先左旋处理L、后右旋处理T节点之后的最终结果。小甲鱼的代码这里好像有误
break;
}
L_Rotate(&(*T)->lchild); //对L结点及其孩子结点调整位置使L->bf与T->bf符号一致
R_Rotate(T); //调整T结点及其孩子结点位置使|T->bf|<1
}
void RightBalance(BiTree *T)
{
BiTree L,Lr;
L=(*T)->rchild;
switch(L->bf)
{
case RH:
(*T)->bf=L->bf=EH;
L_Rotate(T);
break;
case LH:
Lr=L->lchild;
switch(Lr->bf)
{
case RH:
(*T)->bf=LH;
L->bf=EH;
break;
case EH:
(*T)->bf=L->bf=EH;
break;
case LH:
(*T)->bf=EH;
L->bf=RH;
break;
}
Lr->bf=EH;
break;
}
R_Rotate(&(*T)->rchild);
L_Rotate(T);
}
int InsertAVL(BiTree*T,int e,int *taller)
{
if(!(*T)) //创建一个新的结点T或新创建一棵树
{
*T=(BiTree)malloc(sizeof(BiTNode));
(*T)->data=e;
(*T)->lchild=(*T)->rchild=NULL;
(*T)->bf=EH;
*taller=TRUE; //新增结点T
}
else
{
if(e==(*T)->data)
{
*taller=FALSE;
return FALSE;
}
else if(e<(*T)->data)
{
if(!InsertAVL(&(*T)->lchild,e,taller)
{
return FALSE;
}
if(*taller) //每次插入一个结点后修改结点的bf值及调整平衡
{
switch((*T)->bf)
{
case LH:
LeftBalance(T);
break;
case EH:
(*T)->bf=LH;
break;
case RH:
(*T)->bf=EH;
break;
}
*taller=FALSE; //插入的结点处理完毕后*taller初始化
}
}
else
{
if(!InsertAVL(&(*T)->rchild,e,taller)
{
return FALSE;
}
if(*taller)
{
switch((*T)->bf)
{
case RH:
RightBalance(T);
break;
case EH:
(*T)->bf=RH;
break;
case LH:
(*T)->bf=EH;
break;
}
*taller=FALSE; //插入的结点处理完毕后*taller初始化
}
}
}
} 圣狄雅哥 发表于 2018-5-18 22:29
#define LH 1
#define EH 0
#define RH -1
对小甲鱼老师这节代码的补充及整理。标绿处的图例如图 感谢小甲鱼,学完留个念! 小甲鱼牛逼 捕获1的第二个图是不是错了 本帖最后由 1569044682 于 2021-12-3 00:51 编辑
最后两行注释是测试用例
#include <stdio.h>
#include <stdlib.h>
#define LH 1
#define EH 0
#define RH -1
typedef struct BTNode{
int data;
int bf;
struct BTNode * lchild;
struct BTNode * rchild;
}*BiTree;
void R_Rotate(BiTree *p)
{
BiTree L;
L = (*p)->lchild;
(*p)->lchild = L->rchild;
L->rchild = (*p);
*p = L;
}
void L_Rotate(BiTree *p)
{
BiTree R;
R = (*p)->rchild;
(*p)->rchild = R->lchild;
R->lchild = (*p);
*p = R;
}
void LeftBalance(BiTree *T)
{
BiTree L,Lr;
L = (*T)->lchild;
switch(L->bf)
{
case LH:
(*T)->bf = L->bf = EH;
R_Rotate(T);
break;
case RH:
Lr = L->rchild;
switch(Lr->bf)
{
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);
R_Rotate(T);
}
}
void RightBalance(BiTree *T)
{
BiTree L,Lr;
L=(*T)->rchild;
switch(L->bf)
{
case RH:
(*T)->bf=L->bf=EH;
L_Rotate(T);
break;
case LH:
Lr=L->lchild;
switch(Lr->bf)
{
case RH:
(*T)->bf=LH;
L->bf=EH;
break;
case EH:
(*T)->bf=L->bf=EH;
break;
case LH:
(*T)->bf=EH;
L->bf=RH;
break;
}
Lr->bf=EH;
R_Rotate(&(*T)->rchild);
L_Rotate(T);
}
}
int InsertAVL(BiTree *T, int e, int *taller)
{
if( !(*T) )
{
*T = (BiTree)malloc(sizeof(BiTree));
(*T)->data = e;
(*T)->lchild = (*T)->rchild = NULL;
(*T)->bf = EH;
*taller = true;
}
else
{
if(e == (*T)->data)
{
*taller = false;
return false;
}
if(e < (*T)->data)
{
if(!InsertAVL(&(*T)->lchild, e, taller))
{
return true;
}
if(*taller)
{
switch((*T)->bf)
{
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;
}
if(*taller)
{
switch((*T)->bf)
{
case LH:
(*T)->bf = EH;
*taller = false;
break;
case EH:
(*T)->bf = RH;
*taller = true;
break;
case RH:
RightBalance(T);
*taller = false;
break;
}
}
}
}
return true;
}
void printBIT( BiTree root, int x)
{
if (root != NULL)
{
printBIT(root->lchild, x + 1);
for (int i = 0; i < x; i++)
{
printf(" ");
}
printf("%d\n",root->data);
printBIT(root->rchild, x + 1);
}
}
void Inorder( BiTree BT )//中序遍历
{
if( BT == NULL ){
return ;
}
Inorder( BT->lchild );
printf(" %d", BT->data);
Inorder( BT->rchild );
}
int main()
{
int n=0,i=0,e,taller = 0;
char c;
BiTree T=NULL;
while(1)
{
scanf("%d",&e);
if(e == 0){
break;
}
InsertAVL( &T,e,&taller );
}
printf("中序遍历结果:\n");
Inorder( T );
printf("\n二叉树凹入表示:\n");
printBIT( T,0 );
printf("\n");
return 0;
}
//56 78 34 89 12 35 67 77 22 57 0
//147 106 291 130 71 51 7 202 94 249 132 24 85 0
页:
[1]