Проблема с локальным указателем

Question

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

int insert(Node ** n, int data) {

  // create new node
  if (*n == NULL) {
    *n = (Node*) malloc(sizeof(Node));
    (*n)->data = data;
    (*n)->left = NULL;
    (*n)->right = NULL;
    return 1;
  }

  else if (data > (*n)->data) {
    insert(&(*n)->right, data);
  }

  else  {
    insert(&(*n)->left, data);
  }

  return 0;
}

Но затем, пытаясь упростить эту функцию, я попытался выделить * nна локальный указатель узла, например:

Node * c = *n;

Затем я прошел через функцию и заменил все экземпляры * n на c.Однако функция не выполняется должным образом.Может ли кто-нибудь объяснить мне, почему это не работает?Спасибо.

РЕДАКТИРОВАТЬ: Я должен отметить, что в новых изменениях, функция будет немедленно завершена после первого оператора if.Кажется, это указывает на то, что переданный указатель (корень) всегда равен NULL, что означает, что узлы не сохраняются должным образом.Не знаю, в чем причина, но я думаю, что это где-то между локальным указателем и концом первого оператора if.

EDIT2: Я поместил эту следующую проверку в конце первогоблок if:

if (*n != NULL) printf("Node has been allocated\n");

Он никогда не выполняется!

Answer 1

Ваша проблема в том, что вы превратили 'c' в локальную переменную и отредактировали ее содержимое, но вам нужно отредактировать нелокальную переменную.

С вами может быть все в порядке, если вы делаете *n = c; перед каждым возвратом (или изменяете код, чтобы был только один возврат, и выполняйте переназначение перед этим). Итак - непроверенный код:

int insert(Node ** n, int data) {

  Node *c = *n;
  int rc = 0;

  // create new node
  if (c == NULL) {
    c = (Node*) malloc(sizeof(Node));
    c->data = data;
    c->left = NULL;
    c->right = NULL;
    rc = 1;
  }
  else if (data > c->data) {
    rc = insert(&c->right, data);
  }
  else  {
    rc = insert(&c->left, data);
  }

  *n = c;
  return rc;
}

Проверенный код

С испытательным ремнем безопасности. Печать не великолепна - но, по крайней мере, работает. Обратите внимание, что вам нужно освободить дерево с помощью обхода после заказа; печать может быть сделана по предварительному заказу, либо по заказу (как здесь), либо по заказу.

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

typedef struct Node Node;
struct Node
{
    int    data;
    Node    *left;
    Node    *right;
};

static void insert(Node **n, int data)
{
    Node *c = *n;

    if (c == NULL)
    {
        // create new node
        c = (Node*) malloc(sizeof(Node));
        c->data = data;
        c->left = NULL;
        c->right = NULL;
    }
    else if (data > c->data)
        insert(&c->right, data);
    else 
        insert(&c->left, data);

    *n = c;
}

static void dumptree(Node **tree, const char *tag)
{
    assert(tree != 0);
    Node *node = *tree;
    if (node != 0)
    {
        dumptree(&node->left, "left");
        printf("data: %d (%s)\n", node->data, tag);
        dumptree(&node->right, "right");
    }
}

static void dump(Node **tree, const char *tag)
{
    printf("In-Order Dump (%s)\n", tag);
    dumptree(tree, "root");
}

static void freetree(Node **tree)
{
    assert(tree != 0);
    Node *node = *tree;
    if (node != 0)
    {
        freetree(&node->left);
        freetree(&node->right);
        free(node);
        //*tree = 0;
    }
}

int main(void)
{
    Node *base = 0;
    int array[] = { 3, 9, 1, 4, 8, 2, 5, 7, 0, 6 };
    int i;

    for (i = 0; i < 10; i++)
    {
        char buffer[32];
        sprintf(buffer, "Add node %d", array[i]);
        insert(&base, array[i]);
        dump(&base, buffer);
    }

    freetree(&base);
    return 0;
}

Answer 2

Я думаю , что:

вставка (& (* n) -> вправо, данные);и вставьте (& c-> right, data);

не то же самое.

c - это место в памяти, отличное от & (* n).

Answer 3

У меня нет смысла иметь двойной указатель на дерево.Вот еще одно предложение:

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

struct tree; //forward declaration

struct tree {
    int data;
    struct tree * right;
    struct tree * left;
};

typedef struct tree Node;

Node* insert(Node * n, int data) {

    // create new node
    if (n == NULL) { //We are at the first node
        //It is of no use to create a malloc on n since the value will not be updated in the previous calling function since n is NULL. So we would have to return it
        Node * n = (Node*) malloc(sizeof(Node));
        n->data = data;
        n->left = NULL;
        n->right = NULL;
        return n;
    } else {
        //n is not NULL
        if (data > n->data) {
            if(n->right != NULL) {
                //We have to do recursion
                insert(n->right, data); // n->right is a pointer, type Node*
            } else {
                //We don't want to send a NULL in the recursive call, cause it wouldn't update
                n->right = (Node*) malloc(sizeof(Node));
                n->right->data = data;
                n->right->right = NULL;
                n->right->left = NULL;
            }
        } else  {
            if(n->left != NULL) {
                //We have to do recursion
                insert(n->left, data); // n->right is a pointer, type Node*
            } else {
                //We don't want to send a NULL in the recursive call, cause it wouldn't update
                n->left = (Node*) malloc(sizeof(Node));
                n->left->data = data;
                n->left->right = NULL;
                n->left->left = NULL;
            }
        }

        return NULL;
    }
}

int main(void) {
    Node * root = NULL;

    root = insert(root, 10); //First call to initialise the root
    insert(root, 11);

    printf("%d \n", root->data);

    return 0;
}

Кажется, на моем компьютере все работает нормально.Будет ли это отвечать вашим потребностям?

Не стесняйтесь, если вам нужна точность.

Answer 4

insert(&(*n)->right, data);

должно быть:

insert((*n)->right, data);

(*n) вместо &(*n) в обоих ваших вызовах insert () -.Это потому, что * n - ваш указатель на узел, вам не нужно (и не может) брать адрес * n.Если это не работает, пожалуйста, отправьте ваш полный код вкл.Узел-структура.