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 failure: 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

However, when I modified the function to pass in a double pointer and effectively do the same thing it worked

本质上是相同的，但数据根本不同。您最初尝试中的 (&node) 为您提供了一个指向局部变量的指针。当您取消引用它并分配给结果时，您正在修改局部变量。这样的修改对于调用者来说是不可见的。

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

It seems that both the original and modified function are identical

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