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

Question

Я выполняю дерево 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 (), но когда функция возвращается к вызывающей стороне, дерево повреждено. Есть идеи?

Answer 1

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

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

Answer 2

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

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

Answer 3

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

Answer 4

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