c - AVL 树出现错误

Question

我在创建 AVL 树时遇到错误，我的代码的输出每次都给出无限循环。

在下面的代码中，mknode函数用于创建一个节点，lr,rl,right,leftfunctions用于执行所需的操作旋转，而插入函数用于将值插入到AVL树中，然后根据要求进行旋转。

我多次检查了我的代码，但找不到错误。

请帮助我。

struct node
{int a;
struct node *left,*right;
int height;
}*root;
 int bal_factor(struct node*);
 int height(struct node*);
 int greater(int,int);
 struct node*mknode(int);
 struct node*insert(struct node*,int);
 struct node*left(struct node*);
 struct node*right(struct node*);
 struct node*lr(struct node*);
 struct node*rl(struct node*);
 void inorder(struct node*);
 void main()
{
printf("avl tree\n");
root=insert(root,30);
root=insert(root,40);
root=insert(root,20);
root=insert(root,10);
root=insert(root,45);
inorder(root);
}
void inorder(struct node *temp)
{
if(temp==NULL)
    return;
inorder(temp->left);
printf("%d\t",temp->a);
inorder(temp->right);
}
int bal_factor(struct node *temp)
{
if(temp==NULL)
    return 0;
else
 return(height(temp->left)-height(temp->right));
}
int height(struct node *temp)
{
if(temp==NULL)
    return 0;
else
    return greater(height(temp->left),height(temp->right))+1;

}
int greater(int a,int b)
{
if(a>b)
    return a;
else
    return b;
}
struct node* mknode(int t)
{
struct node *temp;
temp=(struct node*)malloc(sizeof(struct node));
temp->a=t;
temp->left=temp->right=NULL;
temp->height=1;
return temp;
};
struct node*right(struct node *temp)
{struct node* temp1;
temp1=temp->left;
temp->left=temp1->right;
temp1->right=temp;
temp1->height=greater(height(temp1->left),height(temp1->right))+1;
temp->height=greater(height(temp->left),height(temp->right))+1;
return temp1;
};
struct node* left(struct node *temp)
{   struct node* temp1;
temp1=temp->right;
temp->right=temp1->left;
temp1->left=temp;
temp1->height=greater(height(temp1->left),height(temp1->right))+1;
temp->height=greater(height(temp->left),height(temp->right))+1;
return temp1;
};
struct node* lr(struct node *temp)
{
temp->left=left(temp->left);
return right(temp);
};
struct node* rl(struct node *temp)
{
temp->right=right(temp->right);
return left(temp);
};
struct node* insert(struct node *temp,int t1)
{
if(temp==NULL)
    return mknode(t1);
if(t1<temp->a)
    temp->left=insert(temp->left,t1);
else
    temp->right=insert(temp->right,t1);
int t;
temp->height=greater(height(temp->left),height(temp->right))+1;
t=bal_factor(temp);
if(t>1&&t1<temp->left->a);
return right(temp);
if(t1<-1&&t1>temp->right->a);
return left(temp);
if(t<-1&&t1<temp->right->a);
return rl(temp);
if(t>1&&t1>temp->left->a);
return lr(temp);

return temp;
}

Answer 1

这是错误的:

  if (t>1 && t1<temp->left->a);
  return right(temp);
  if (t1<-1 && t1>temp->right->a);
  return left(temp);
  if (t<-1 && t1<temp->right->a);
  return rl(temp);
  if (t>1 && t1>temp->left->a);
  return lr(temp);

您可能想要这个:

  if (t>1 && t1<temp->left->a)
    return right(temp);
  if (t1<-1 && t1>temp->right->a)
    return left(temp);
  if (t<-1 && t1<temp->right->a)
    return rl(temp);
  if (t>1 && t1>temp->left->a)
    return lr(temp);

请注意，以 if 开头的行后面没有 ;。

不相关:

temp = (struct node*)malloc(sizeof(struct node));

应该写

temp = malloc(sizeof(struct node));

您不会在 C 中转换 malloc 的返回值。