c - 本地指针问题

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 block 的末尾:

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;
}