C语言 使用指针将节点插入二叉树

Question

我正在尝试创建一种使用以下结构将节点插入BST的方法：

// node structure
struct Node {
    int val;
    struct Node* left;
    struct Node* right;
};
// binary tree structure
struct BinaryTree {
    struct Node* root;
};

最初，我创建了此方法以将节点添加到树中：

// add value to binary tree
void _AddNode(struct Node* node, int val) {
    if (node == NULL)
        *(&node) = CreateNode(val);
    else if (val <= node->val)
        _AddNode(node->left, val);
    else
        _AddNode(node->right, val);
}
void AddNode(struct BinaryTree* tree, int val) {
    _AddNode(tree->root, val);
}

使用此函数构造树，当我尝试遍历、打印、访问树中的数据时，我收到Segmentation fault: 11错误。

但是，当我修改函数以传入双指针并有效地执行相同的操作时，它起作用了：

// add value to binary tree
void _AddNode(struct Node** node, int val) {
    if (*node == NULL)
        *node = CreateNode(val);
    else if (val <= (*node)->val)
        _AddNode(&(*node)->left, val);
    else
        _AddNode(&(*node)->right, val);
}
void AddNode(struct BinaryTree* tree, int val) {
    _AddNode(&tree->root, val);
}

为什么后者有效，而前者不起作用。

Answer 1

但是，当我修改函数以传入双指针并有效地执行相同的操作时，它起作用了

本质上相同的事情，在根本不同的数据上。 原始尝试中的(&node)为您提供指向局部变量的指针。 因此，当您取消引用该变量并分配给结果时，您将修改局部变量。 此类修改对调用方不可见。

另一方面，如果你传递(比如(一个合适的双指针到你的函数，比如_AddNode(&(*node)->left, 42)，那么函数参数的值指向同一件事：调用者的(*node)->left。 如果取消引用该指针并分配给结果，则调用方自然可见。

似乎原始功能和修改后的功能都是相同的

显然，它们在词汇上并不相同。 你的意思似乎是它们在你看来是等价的，但由于行为的差异反驳了这种等价，因此有理由认为这两个函数的明显差异实际上产生了不同的语义。 似乎让你感到困惑的关键是，在 C 中，函数参数总是按值传递的，因此每个函数参数都以调用方传递的值开头，但不是调用方相应参数的别名。 指针类型的参数也不例外。