Рекурсивный вызов и назначение опорных указателей

Question

Я чувствую себя смущенным указателями в C++, где я пытаюсь реализовать BST.

Вместо (метода 1), имеющий тип узла, я хочу использовать опорный указатель (метод 2).

1. Как я могу переписать if-инструкцию, чтобы она работала в методе, в котором указатели использовались?
2. Как узел p в (2) может быть назначен другому временному узлу?

Большое вам спасибо.

//1 

node* delete(node* p, int k) // deleting k key from p tree 
{ 
    if(k < p->key) 
    p->left = remove(p->left,k); 
} 

//2 

void delete(int key, node*& p) { 
// recursive call while key is less and assign a new left child. 
    if(k < p->key) { 
    //?? 

    } 
} 

Answer 1

node *getNode(int key, node *haystack){ 
    if(!haystack) 
     return NULL; 
    if(haystack->val == key) 
     return haystack; 
    if(haystack->val < key) 
     return getNode(key, haystack->left); 
    return getNode(key, haystack->right); 
} 

void getNode(int key, node *haystack, node *&result){ 
    if(!haystack){ 
     result = NULL; 
     return; 
    } 
    if(haystack->val == key){ 
     result = haystack; 
     return; 
    } 
    if(haystack->val < key){ 
     return getNode(key, haystack->left, result); 
    } 
    return getNode(key, haystack->left, result); 
} 

В конечном итоге они почти одинаковы. Однако, если вы действительно хотите удалить, есть еще немного работы, поскольку вам нужно установить указатель удаленного узла на удаленный узел на NULL, если удаленный узел является листом, или вам нужно добавить дочерние элементы удаленных узлов узел к дереву (или удалить их тоже).

Answer 2

Я предполагаю, что вы хотите передать ссылку, чтобы вы могли обнулить указатель?

что-то, как это должно работать:

void delete_node(int key, node*&p) 
{ 
    if (key < p->key) { 
     delete_node(key, p->left); 
     delete(p); 
     p = nullptr; 
    } 
} 

Но это немного озорной. Он ограничивает количество случаев, в которых может быть вызвана ваша функция, и добавляет некоторые потенциально удивительное поведение в том смысле, что изменяет входной аргумент. Это также означает, что член вашего узла left обнуляется без необходимости, когда узлы удаляются рекурсивно (поскольку текущий узел сам будет удален в любом случае).