C语言AVL树
我目前正在做一个需要使用AVL树的项目, 我为 avl 编写的插入函数似乎不起作用,它最多适用于 3 或 4 个节点;
我非常感谢你的帮助 尝试如下
Tree insert(Tree t,char name[80],int num)
{
if(t==NULL)
{
t = (Tree)malloc(sizeof(struct node));
if(t! = NULL)
{
strcpy(t->name,name);
t->num = num;
t->left = NULL;
t->right = NULL;
t->height = 0;
}
}
else if(strcmp(name,t->name)<0)
{
t->left = insert(t->left,name,num);
if((height(t->left)-height(t->right))==2)
if(strcmp(name,t->left->name)<0)
t = s_rotate_left(t);
else
t = d_rotate_left(t);
}
else if(strcmp(name,t->name)>0)
{
t->right = insert(t->right,name,num);
if((height(t->right)-height(t->left))==2)
if(strcmp(name,t->right->name)>0)
t = s_rotate_right(t);
else
t = d_rotate_right(t);
}
t->height = max(height(t->left),height(t->right))+1;
return t;
}
i am currently doing a project that requires the use of AVL trees ,
the insert function i wrote for the avl does not seem to be working , it works for 3 or 4 nodes at maximum ;
i would really appreciate your help
The attempt is below
Tree insert(Tree t,char name[80],int num)
{
if(t==NULL)
{
t = (Tree)malloc(sizeof(struct node));
if(t! = NULL)
{
strcpy(t->name,name);
t->num = num;
t->left = NULL;
t->right = NULL;
t->height = 0;
}
}
else if(strcmp(name,t->name)<0)
{
t->left = insert(t->left,name,num);
if((height(t->left)-height(t->right))==2)
if(strcmp(name,t->left->name)<0)
t = s_rotate_left(t);
else
t = d_rotate_left(t);
}
else if(strcmp(name,t->name)>0)
{
t->right = insert(t->right,name,num);
if((height(t->right)-height(t->left))==2)
if(strcmp(name,t->right->name)>0)
t = s_rotate_right(t);
else
t = d_rotate_right(t);
}
t->height = max(height(t->left),height(t->right))+1;
return t;
}
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(1)
我不知道您遇到了什么类型的错误,但有一些事情需要修复。
您需要决定当
malloc
失败时要做什么。在这种情况下,现在您正在空指针上设置height
。如果
height(NULL)
返回 0,那么您将新节点上的高度设置为 0,然后设置为 1。如果它返回 -1,则这些分配之一是多余的。并且您无缘无故地调用了
strcmp
两次。我怀疑真正的问题隐藏在
s_rotate_left
、d_rotate_left
、s_rotate_right
或d_rotate_right
中。I don't know what sort of error you're getting, but there are a couple of things that need to be fixed.
You need to deside what you're going to do when the
malloc
fails. Right now you are settingheight
on a null pointer in that case.If
height(NULL)
returns 0, then you are setting the height on a new node to 0 and then to 1. If it returns -1, then one of those assignments is redundant.And you're calling
strcmp
twice for no good reason.I suspect the real problem is buried in
s_rotate_left
,d_rotate_left
,s_rotate_right
, ord_rotate_right
.