我正在实现一个AVL树及其操作,如旋转。 最后当我尝试插入数组时,结果似乎如此 不同。谁都告诉我出了什么问题!谢谢 !
#include <stdio.h>
#include <stdlib.h>
#define LH +1
#define RH -1
#define EQ 0
typedef int BOOL;
typedef struct node
{
int bf;
struct node *left;
struct node *right;
int val;
}treeNode;
void L_Rotate(treeNode **T)
{
treeNode *p = (*T)->right;
(*T)->right = p->left;
p->left=*T;
*T=p;
}
void R_Rotate(treeNode **T)
{
treeNode *p=(*T)->left;
(*T)->left=p->right;
p->right=*T;
*T=p;
}
void Left_Balance(treeNode **T)
{
treeNode *p=(*T)->left;
treeNode *q;
switch(p->bf)
{
case LH:
p->bf=(*T)->bf=EQ;
R_Rotate(T);
break;
case RH:
q = p->right;
switch(q->bf)
{
case LH:
(*T)->bf=RH;
p->bf=EQ;
break;
case EQ:
(*T)->bf=q->bf=EQ;
break;
case RH:
p->bf=LH;
(*T)=EQ;
break;
}
q->bf=EQ;
L_Rotate(&p);
R_Rotate(T);
}
}
void Right_Balance(treeNode **T)
{
treeNode *p=(*T)->right;
treeNode *q;
switch(p->bf)
{
case RH:
(*T)->bf=p->bf=EQ;
L_Rotate(T);
break;
case LH:
q=p->left;
switch(q->bf)
{
case LH:
(*T)->bf=EQ;
p->bf=RH;
break;
case RH:
(*T)->bf=LH;
p->bf=EQ;
break;
}
q->bf=EQ;
R_Rotate(&p);
L_Rotate(T);
}
}
int insertAVL (treeNode **T,int key, BOOL *taller)
{
if(!*T)
{
*T=malloc(sizeof(treeNode));
if(!*T) return 0;
(*T)->left=(*T)->right=NULL;
(*T)->bf=EQ;
*taller = 1;
(*T)->val=key;
}
else
{
if(key==(*T)->val)
{
*taller= 0;
return 0;
}
else if(key<(*T)->val)
{
if(!insertAVL(&(*T)->left,key,taller)) return 0;
if(*taller)
{
switch((*T)->bf)
{
case LH:
Left_Balance(T);
*taller=0;
break;
case RH:
(*T)->bf=EQ;
*taller =0;
break;
case EQ:
(*T)->bf=LH;
*taller =1;
break;
}
}
}
else
{
if(!insertAVL(&(*T)->right,key,taller)) return 0;
if(*taller)
{
switch((*T)->bf)
{
case LH:
(*T)->bf=EQ;
*taller=0;
break;
case EQ:
(*T)->bf=RH;
*taller=1;
break;
case RH:
Right_Balance(T);
*taller =0;
break;
}
}
}
}
return 1;
}
void preOrder(treeNode *T)
{
if(!T)
{
return;
}
printf("%d\n",T->val);
preOrder(T->left);
preOrder(T->right);
}
int main() {
int i;
int a[10]={3,2,1,4,5,6,7,10,9,8};
treeNode *T=NULL;
BOOL taller;
for(i=0;i<10;i++)
{
insertAVL(&T,a[i],&taller);
preOrder(T);
printf("-------\n");
}
return 0;
}
每次插入树后我遍历树,结果是 直到我将9插入树中。
我还注意到你的左/右平衡功能不对称,右平衡代码错过了EQ情况。我做了一些尝试添加它并重写Right_Balance
对齐Left_Balance
,但没有解决任何问题。这个问题不是(仅限)。
如果管理AVL没有错,您必须考虑每个单元格的高度,以决定在插入新值后如何平衡。
在你的情况下,没有高度,但bf能够获得3个值LH / RH / EQ,在某种程度上bf相当于1到3范围内的高度。但是在插入10之后,值为4的单元格实际上高度为4,你无法管理,对我而言,这就是为什么你不能在10后正确插入9之后。
修改树(或子树)时,传入指向头指针的指针,以便更改反映在原始链接中,即全局头或节点的左/右链接之一。在我看来,这是一个很好的做法。
当你平衡树时,你也会这样做,但是有一个陷阱:
treeNode *p = (*T)->left;
// ... some stuff ...
L_Rotate(&p);
R_Rotate(T);
在这里,p
是(*T)->left
的本地副本。您最终修改了一个局部变量(它将立即超出范围),但不会修改父节点中的实际链接;节点被“吃掉”。
您可以将p
设为treeNode **
,或者,如果您不更改指针本身,请将您的旋转代码更改为:
L_Rotate(&(*T)->left);
R_Rotate(T);
同样适用于其他轮换。