поиск элемента в 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

Эти свойства являются правыми и левыми дочерними элементами текущего узла. и в то время как время пересекает дерево, чтобы найти подходящее место для значения как его большего или меньшего, чем текущий узел, как определение Двоичного поиска