AVL树C语言 [英] AVL tree in C language

问题描述

我正在做一个需要使用AVL树的项目，
我为avl写的insert函数似乎不起作用，最多可以在3或4个节点上运行;

我真的很感激你的帮助
尝试在

 树插入（Tree t，char name [80]，int num）
 {
 if（t == NULL）
 {
t =（Tree）malloc（sizeof ）; 
 
 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 > 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; 
} 
  

解决方案

我不知道你会得到一些错误，但有几件事情需要修复。

你需要确定你将要做什么，当 malloc 失败。在这种情况下，您现在要在空指针上设置 height 。

如果 height （NULL）返回0，那么您将新节点上的高度设置为0，然后设置为1.如果返回-1，则其中一个分配是多余的。

你不是很有道理地打电话给 strcmp 两次。

我怀疑真正的问题是埋在 s_rotate_left ， d_rotate_left ， s_rotate_right 或 d_rotate_right 。

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;
}

解决方案

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 setting height 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, or d_rotate_right.

这篇关于AVL树C语言的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！