Двоичное дерево поиска. Указатель как ссылочный параметр

Question

Итак, я работаю над функцией двоичного поиска. Почему я должен добавить знак & перед указателем на узел? Я думал, что это уже указатель, и он уже указывает на местоположение. Я понимаю, что если я добавлю узел, то мне нужно убедиться, что родительский узел указывает на новый узел или узел родителя будет по-прежнему указывать на NULL. Но почему бы мне не сделать это, если я передам указатель на узел как узел * &?

bool bst::remove123(int data, node*& x) 
{ 
if (x == NULL) 
{ 
    return false; 
} 
else if (x->getData() < data) 
{ 
    return remove123(data, x->right); 
} 
else if (x->getData() > data) 
{ 
    return remove123(data, x->left); 
} 
else 
{ 
    node* old = x; 
    if (x->left == NULL) 
    { 
     x = x->right; 
    } 
    else if (x->right == NULL) 
    { 
     x = x->left; 
    } 
    else 
    { 
     replacement(old, x->left); 
    } 
    delete old; 
    return true; 
} 
} 

Спасибо

Answer 1

node*& x является ссылкой на node*. Это означает, что когда bst::remove123 изменяет x, чтобы указать на другой адрес, код, который называется bst::remove123, видит то же изменение в переменной node*, которое он передал методу. Если вы указали параметр x как node *x, то bst::remove123 будет изменять только копию переменной, переданной в этом параметре, и эти изменения будут потеряны после возврата метода. В то время как & используется для обозначения ссылки, это очень отличается от оператора & (часто используется с указателями), который возвращает адрес переменной, следующей за ней.

int n = 10; 
int *pn = &n; // Create a pointer to int, set it to the address of n. 
int& rn = n; // Create an int reference, set it to reference the same variable as n. 

*pn = 5; // Set n to 5 via a dereferenced pn. A dereferencing operator * 
     // is needed to indicate that we want to change the memory that 
     // pn points to, not the address that the pointer contains. 

rn = 20; // Set n to 20 via the reference rn. Unlike with pointers, 
     // references do not use a dereferencing operator.