AVL дерево на языке Си - PullRequest
Новая
       10

AVL дерево на языке Си

2 голосов
/ 09 апреля 2010

В настоящее время я делаю проект, который требует использования деревьев 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;
}

1 Ответ

1 голос
/ 09 апреля 2010

Я не знаю, какую ошибку вы получаете, но есть пара вещей, которые необходимо исправить.

Вам нужно решить, что вы будете делать, когда malloc не удастся. Прямо сейчас вы устанавливаете height на нулевой указатель в этом случае.

Если height(NULL) возвращает 0, то вы устанавливаете высоту для нового узла на 0, а затем на 1. Если он возвращает -1, то одно из этих назначений избыточно.

И вы звоните strcmp дважды без веской причины.

Я подозреваю, что настоящая проблема скрыта в s_rotate_left, d_rotate_left, s_rotate_right или d_rotate_right.

...