c - 指向二叉搜索树节点的双指针

Question

对你们中的一些人来说，这可能看起来是一个愚蠢的问题，我知道我经常把事情搞混，但我需要理解代码，这样我才能停止纠结于它并专注于我为什么需要这样做的真正问题使用它。

所以，在代码中我看到了几个这样的赋值:

struct bst_node** node = root;
node = &(*node)->left;
node = &(*node)->right;

is there an invisible parenthesis here?

node = &((*node)->right);

这个例子来自 literateprograms.org。

所以对我来说 &(*node) 似乎是不必要的，我还不如只写 node->left ，但是代码似乎在我无法理解的地方工作，我想知道它是否是因为我误解了那些线路上发生的事情。特别是，在代码中的一个地方，它通过不断地将“已删除”数据移动到树的底部以安全地删除节点而不必“破坏事物”来删除节点，我迷路了，因为我没有了解如何

old_node = *node;
if ((*node)->left == NULL) {
    *node = (*node)->right;
    free_node(old_node);
else if ((*node)->right == NULL) {
    *node = (*node)->left;
    free_node(old_node);
} else {
    struct bst_node **pred = &(*node)->left;
    while ((*pred)->right != NULL) {
        pred = &(*pred)->right;
    }
    psudo-code: swap values of *pred and *node when the 
    bottom-right of the left tree of old_node has been found.
    recursive call with pred;
}

可以保持树结构完整。我不明白这是如何确保结构完好无损的，希望知道发生了什么事的人提供一些帮助。我将节点解释为堆栈上的局部变量，在函数调用时创建。由于它是一个双指针，它指向堆栈中的一个位置(我假设是这样，因为他们在函数调用之前做了 &(*node) )，它是自己的堆栈或之前的函数，然后指向所述节点在堆上。

在上面的示例代码中，我认为它应该做的是向左或向右切换，因为其中一个为 NULL，然后切换不为 NULL 的那个(假设另一个不为 NULL？)正如我所说，我不确定这将如何运作。我的问题主要与我认为 &(*node) <=> node 的事实有关，但我想知道是否不是这种情况等。

Answer 1

node = &(*node)->right;

is there an invisible parenthesis here?

node = &((*node)->right);

是的。它正在获取 *node 的 right 成员的地址。 -> 优先于 &；见C++ Operator Precedence (-> 是 2，& 在该列表中是 3)(它与 C 的一般优先级相同)。

So to me it seems &(*node) is unnecessary and I might as well just write node->left instead,

你的前提是关闭的。没有表达式&(*node)，如上所述，&适用于整个(*node)->left，不是(*节点)。

在该代码中，双指针就是指向指针的指针。就像这样工作:

   int x = 0;
   int *xptr = &x;
   *xptr = 5;
   assert(x == 5);

这个是一样的，它改变了指针x的值:

   int someint;
   int *x = &someint;
   int **xptr = &x; 
   *xptr = NULL;
   assert(x == NULL);

在您发布的代码片段中，将指针分配给 *node 会更改 node 指向的指针的值。所以，例如(伪代码):

   typedef struct bst_node_ {
     struct bst_node_ *left;
     struct bst_node_ *right;
   } bst_node;

   bst_node * construct_node () {
     return a pointer to a new bst_node;
   }

   void create_node (bst_node ** destination_ptr) {
     *destination_ptr = construct_node();
   }

   void somewhere () {
     bst_node *n = construct_node();
     create_node(&n->left);  // after this, n->left points to a new node
     create_node(&n->right); // after this, n->right points to a new node
   }

再次注意 &n->left 由于优先规则与 &(n->left) 相同。希望对您有所帮助。

在 C++ 中，您可以通过引用将参数传递给函数，这与传递指针基本相同，只是在语法上它导致代码更易于阅读。