创建二叉搜索树而不更新指针

Question

我正在创建一个简单的二叉搜索树。当我使用头指针调用 add 方法时，方法中所做的更改不会反射(reflect)到此头指针。它仍然指向 null。

struct node *add(struct node *root,int data)
{
    if (root==NULL)
    {
        root=(struct node *) malloc(sizeof(struct node));
        root->data=data;
        root->left=NULL;
        root->right=NULL;
        return root;
    }
    else
    {   
        if (data<=root->data)
        {
            root->left=add(root->left,data);
        }
        else
        {
            root->right=add(root->right,data);
        }
        return root;
    }

}

我将该函数称为

struct node *head=NULL;
add(head,1);
add(head,3);
add(head,15);

根据我的理解，在调用 add 方法时，root=head，因此 head 将指向 root 所指向的同一内存位置，并且应该相应地使用 root 的变化值进行更新。

更新

head=add(head,1);

Answer 1

当你传递一个指针(这里是node*)时，你只需复制它所指向的内存地址的值，你可以在函数中改变这个地址的内容，但它外面的指针仍然会包含相同的内容地址。

最初你有head = NULL，它没有指向任何地方。当您调用该函数时，您将创建一个名为 root 的局部变量，并将指针的值 (NULL) 复制到其中。然后分配一些空间并更改 root 指向那里，但是一旦离开函数，对局部变量的更改就会丢失，并且外部的 head 将继续保存值 NULL。实际上，您丢失了分配的内存，因为不再有人指向那里(valgrind 可能已经告诉您这一点)。

如果您将 &head 传递给函数(类型将为 node**，请注意，您必须使用 *root 以这种方式在函数内部)，更改将直接在外部变量上进行(由于 c 实际上会将 main() 在堆栈上分配它的地址直接传递给函数)。
顺便说一句，在 C++ 中，通过引用传递值会在内部模拟相同的事情，并且会更简单(您将能够保持代码按原样引用 root)。

或者，您可以只从函数返回新头指针的值。不过，这会将您限制为单个返回值(在本例中这很好)