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

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

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 中，函数参数总是通过 by value 传递，因此每个函数参数都以 value 开头由调用者传递，但不是调用者相应参数的别名。指针类型参数也不例外

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

Inserting node into binary tree using pointers

c

binary-tree

pointers