2

我目前正在做一个需要使用 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;
}
4

1 回答 1

1

我不知道您遇到了什么样的错误，但有几件事需要修复。

malloc你需要决定失败时你要做什么。现在，height在这种情况下，您正在设置一个空指针。

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

而且你strcmp无缘无故打了两次电话。

我怀疑真正的问题隐藏在s_rotate_left, d_rotate_left,s_rotate_right或d_rotate_right.

于 2010-04-09T15:28:39.003 回答