在BST中搜索元素

Question

以下是用于在BST中搜索元素的代码。谁能解释代码中&(*cur)->right或&(*cur)->left的含义吗？

谢谢

TreeNode *insertIntoBST(TreeNode *root, int val)
    {
        TreeNode **cur = &root;
        while( *cur )
            cur = (val > (*cur)->val) ? &(*cur)->right : &(*cur)->left;
        *cur = new TreeNode(val);
        return root;
    }

Answer 1

cur是一个指向指针的指针，因此，要访问其子级，需要先取消引用它（*cur），然后才访问元素（->left，->right）。

[获得下一个元素（right或left），它是一个指针后，需要将其存储在cur中。但是cur是指向该指针的指针，因此您需要引用if（使用&运算符）。

整体表达是丑陋的&(*cur)。

顺便说一句，您需要一个指针的原因是因为*cur = new TreeNode(val);行。

如果仅使用指针，则此行将不执行任何操作，仅更改您的临时指针。由于您使用的是指向指针的指针，因此您正在更改树中的原始节点。

Answer 2

这些属性是当前节点的左右子节点。而while遍历该树以找到该值的合适位置，因为该值大于或小于当前节点（如Binary Search Tree定义）