为什么 Node *root 没有更新？

Question

这是一个非常简单的插入数字的示例。

typedef struct node {
    int data;
    struct node *left, *right;

} node;

node * newNode(int val) {
    node* n = malloc(sizeof(node));
    n->data=val;
    n->left=NULL;
    n->right=NULL;
    return n; }

void insert(node* node, int key) {    
    if (node == NULL)
        node = newNode(key);
}

int main() {
    node *root = NULL;
    insert(root, 5);

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

    return 0;
}

问题是，当我在 root 中插入 5 时，为什么 printf 不打印任何内容？

Answer 1

在 C 中，所有参数都按值传递。这意味着该值被复制到参数变量中，当您进行赋值时 node = newNode(key); 您只分配给本地 node 变量。

这个问题有两种解决方法：

Return 新节点改为：

node* insert(node* the_node, int key) {    
    if (the_node == NULL)
        the_node = newNode(key);
    return the_node;
}

...

root = insert(root, 5);

模拟按引用传递，这可以通过使用寻址运算符&:[=传递指向变量的指针来完成15=]

void insert(node** the_node, int key) {    
    if (*the_node == NULL)
        *the_node = newNode(key);
}

...

insert(&root, 5);

Answer 2

您按值将指针 root 传递给了函数 insert。您可以想象函数定义及其调用方式如下

node *root = NULL;
insert(root, 5);

//...

void insert( /* node* node, int key */ ) {    
    node* node = root;
    int key = 5;
    if (node == NULL)
        node = newNode(key);
}

如您所见，该函数处理指针根的副本。更改作为局部变量 node 中值的副本不会影响存储在指针 root.

中的值

您必须通过引用传递指针 root。例如

void insert(node** node, int key) {    
    if (*node == NULL)
        *node = newNode(key);
}

int main() {
    node *root = NULL;
    insert(&root, 5);
    //...

在 C 术语中，按引用传递意味着通过指向对象的指针间接传递对象。在这种情况下，可以通过传递的指针在函数中访问该对象。

注意函数newNode按如下方式定义会更安全

node * newNode( int val ) 
{
    node *n = malloc( sizeof( node ) );

    if ( n != NULL )
    {
        n->data  = val;
        n->left  = NULL;
        n->right = NULL;
    }

    return n; 
}

在这种情况下，函数 insert 可以看起来像

int insert( node **node, int key ) 
{
    while ( *node != NULL )
    {
        if ( key < ( *node )->data )
        {
            node = &( *node )->left;
        }
        else
        {
            node = &( *node )->right;
        }
    }

    *node = newNode( key );

    return *node != NULL;
}

为什么 Node *root 没有更新？

why does there is no update in Node *root?

c

struct

pass-by-reference

binary-search-tree