本地指针问题

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语句之后立即退出。这似乎表明传入的指针（根）始终为空，这意味着节点没有被正确保存。不确定原因，但我认为问题在本地指针和第一个if语句末尾之间。

编辑2：我在第一个if块的末尾放置了以下检查：

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

它从未执行！

- Sam

---

如果你想简化这段代码，我建议将它改为void。除了构建根节点之外，它总是返回0。 - Fred Foo

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

- Jonathan Leffler

Answer 2

我认为：

insert(&(*n)->right, data); 和 insert(&c->right, data); 不是同一个意思。

c 在内存中的位置与 &(*n) 不同。

- TCS

---

@strDisplayName：好的，我明白了，C和N是内存中的不同指针，但它们不是指向同一块内存空间吗？ - Sam

@Sam，你并没有改变c指向的内容，而是改变了c本身。 - Philip Potter

特别是像 *n = (Node*) malloc(...); 这样的代码行会让你陷入麻烦，因为新分配的内存由 c 指向，而不是 *n。 - Andres Jaan Tack

@Andres：谢谢你告诉我这个。我在if语句的末尾添加了*n = c;，现在代码可以正常工作了。 - Sam

请注意，&(*n)->right 等同于 &((*n)->right)。如果 c == *n，那么 &(*n)->right == &c->right。然而，*n = (Node*) malloc(sizeof(Node)); 不等同于 c = (Node*) malloc(sizeof(Node));。 - outis

Answer 3

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

应该是：

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

在你的insert()调用中，使用(*n)代替&(*n)。这是因为*n是你的节点指针，你不需要（也不能）取*n的地址。如果这不起作用，请发布包括Node结构在内的完整代码。

- Bernd Elkemann

Answer 4

我并不理解为什么在树的情况下需要使用双指针。

这里有另一个建议：

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

目前在我的电脑上运行良好。

如果您需要更多的精确信息，请随时联系我。

- M'vy

---

这带来了一个有趣的问题。我猜因为我们不期望在树中移动节点，所以使用单指针比双指针更合适。无论如何，对我来说，这主要是关于指针的练习。 - Sam