проблема указателя при реализации дерева в C

Я реализую дерево avl для моего назначения.

#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>

struct TreeNode {
  char *item;
  struct TreeNode *left;
  struct TreeNode *right;
  signed char balance;
};

typedef struct TreeNode Node;

void _print_avl (Node *, int , const char *);

Node * get_new_node (char *);
int avl_insert(Node *, char *);
void print_avl (Node *);
void avl_swr(Node*);

int main (int argc, char *argv[])
{
  Node *root = get_new_node("thura");
  avl_insert(root, "thur2");
  print_avl(root);

  avl_insert(root, "thur1");

  return 0;
}

int avl_insert(Node *root, char *item)
{
  assert(root);

  if( strcmp(item, root->item) < 0) {

        if(!root->left) {
          root->left = get_new_node(item);
          if(--(root->balance)) return 1;
          return 0;
        } else  {
          if(avl_insert(root->left, item)) {
                if( root->balance-- < 0) {
                  avl_swr(root); //Rotate the node right.
                  print_avl(root); //Here, the tree is corrupted.
                  return 0;
                }
                return 1;
          }
        }
  } else {
        if(!root->right) {
          root->right = get_new_node(item);
          if(++(root->balance)) return 1;
          return 0;
        }
        else {
          if(avl_insert(root->right, item)) {
                root->balance++;
                return 1;
          }
        }
  }
  return 0;
}

void avl_swr(Node* root)
{
  Node *node = root;
  root = node->left;

  node->left = NULL;
  node->balance = 0;

  root->right = node;
  root->balance++;

  print_avl(root); // It is working fine here.
}

Node * get_new_node (char *item) {
  Node * node = (Node *)malloc(sizeof(Node));
  node->item  = item;
  node->left  = NULL;
  node->right = NULL;
  node->balance = 0;
  return node;
}

void print_avl (Node *node)
{
  _print_avl(node, 0, "\t\t");
}

void _print_avl (Node *node, int depth, const char *delim)
{
  if(!node)
        return;
  int i = 0;
  while(i++ < depth) printf("%s", delim);
  printf("--> %s:%d\n", node->item, node->balance);

  depth++;

  if(node->left)
        _print_avl (node->left, depth, delim);

  if(node->right)
        _print_avl (node->right, depth, delim);
}

Проблема в том, что когда я вращаю дерево, используя avl_swr (), оно успешно поворачивается в соответствии с print_avl (), но когда функция возвращается к вызывающей стороне, дерево повреждено. Любые идеи?

13.10.2009 13:01:31
4 ОТВЕТА
РЕШЕНИЕ

Проблема с avl_swr () связана с сигнатурой функции: void avl_swr(Node* root)и назначением: root = node->left;

Корневой указатель не обновляется при возврате функции (обновляется только локальная копия внутри функции). Подпись должна быть: void avl_swr(Node** root)для достижения желаемого результата.

5
13.10.2009 13:07:11

Копия указателя обновлена. Вам нужно передать указатель на указатель в вашей функции поворота.

1
13.10.2009 13:07:32

Это потому, что корневая переменная в avl_insert не изменяется в avl_swr. Когда вы передаете его в avl_swr, создается копия указателя. Вы меняете этот указатель.

Измените вызовы на root = avl_swr(...)avl_swr и верните рут.

1
13.10.2009 13:10:28
+1. Собирался обновить мой ответ. Преимущество этого метода заключается в том, что вы можете при необходимости выполнять цепочку вызовов.
dirkgently 13.10.2009 13:11:36

не уверен на 100%, но я вижу одну проблему. В avl_swr () вы меняете корень на левое поддерево. Поэтому, когда вы печатаете в avl_swr (), у вас будет root = "thur2". Но когда вы вернетесь к avl_insert (), root там не изменится, все еще указывая на «thura», который теперь не имеет дочерних элементов. Поэтому, когда вы печатаете этот корень, он не показывает детей. Возможно, это то, что вы имеете в виду под коррупцией? Очевидно, что решение состоит в том, чтобы изменить «корень» в avl_insert (). Это можно сделать, вернув avl_swr новое корневое значение или изменив параметр с «Node * root» на «Node ** root», чтобы изменение в avl_swr было «передано» обратно в avl_insert

0
13.10.2009 13:38:59