Проблемы с указателями

Question

У меня есть дерево бинарного поиска, и я реализовал код узла вставки следующим образом:

BSTNode * BST::Insert(const std::string & v){
    BSTNode * node = new BSTNode(v);
    if (root == NULL){
        root = node;
    } else if (root->value.compare(v) > 0) {
        Insert(root->left, node);
        //recursive insert the method
    } else if (root->value.compare(v) < 0) {
        Insert(root->right, node);
    } else {
        delete node;
        return NULL;
    }
    size++;
    return node;
}

За этим следует метод рекурсивной вставки в моем заголовочном файле (он имеет частный доступ):

void Insert(BSTNode* current, BSTNode* node){
    if (current == NULL){
        current = node;
    } else if (current->value == node->value){
        delete node;
    } else if (current->value < node->value) {
        Insert(current->left, node);
    } else if (current->value > node->value){//if (parent->value < node->value) {
        Insert(current->right, node);
    }
}

Когда рекурсивная функция устанавливает указатель, а затем возвращает его, изменения, которые я внес в указатель, НЕ сохраняются.

Answer 1

Проблема в том, что current является локальной переменной с копией значения указателя.Это не та переменная, которую вы передаете. Если вы хотите изменить указатель на месте, ваш метод должен принять либо указатель на указатель, либо ссылку на указатель.Самый простой способ сделать это - просто изменить current на ссылку на указатель.Результирующий код будет выглядеть так:

void Insert(BSTNode* &current, BSTNode* node){
    if (current == NULL){
        current = node;
    } else if (current->value == node->value){
        delete node;
    } else if (current->value < node->value) {
        Insert(current->left, node);
    } else if (current->value > node->value){//if (parent->value < node->value) {
        Insert(current->right, node);
    }
}

В общем, вы должны иметь в виду, что указатели - это просто значения, которые указывают вам место в памяти чего-либо.Так что они на самом деле просто цифры.И когда они передаются в функцию, если нет ссылки, они передаются по значению.Таким образом, ваша функция просто видит число, а не переменную, которая содержит число.

Answer 2

void Insert(BSTNode*& current, BSTNode* node)

- правильный прототип для данной функции.Больше ничего не нужно менять.Причина, по которой это необходимо, хорошо описана Китом.

Я также добавил бы, что в общем случае вам следует опасаться условного удаления указателей, переданных в качестве аргументов функции - вы накладываете бремя на кодвне этой функции, чтобы определить, является ли адрес памяти, на который он ссылается, действительным или нет.Вместо этого рассмотрите использование Boost's shared_ptr.