c - 在AVL树中出现错误

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

在以下代码中，mknode函数用于创建node，而lr,rl,right,leftfunctions用于执行所需的旋转，而insert函数用于将值插入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;
}

最佳答案

这是错误的：

  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的返回值。

关于c - 在AVL树中出现错误，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/46846079/