Исправление проблем с вызовом указателя в рекурсии

Question

Так что я работаю над BST, собирая инструменты удаления.

Кажется, что моя кодовая последовательность работает правильно - сохраните, не обновляя родительский или корневой каталог и установив указатель, который отправил его на адрес удаленного узла, в NULL.

Я передаю указатель на указатель в моих функциях Erase и RemoveNode, чтобы напрямую воздействовать на левые, правые или корневые члены данных, которые фактически приводят к рекурсивному вызову. Проходя по коду, он устанавливает * N в NULL в функции удаления, но это не отражается в данных вызывающего объекта. Я неправильно использую метод указатель-на-указатель? Если да, есть ли способ рекурсивно удалить и изменить предыдущий узел, если ссылка уничтожена?

Структура узла:

struct tNode
{
    tNode(int n)
    {
        data = n; 
        left = NULL; 
        right = NULL;
    }

    //Works, cleans all linked objects. 
    //Must remember to null links when removing wanted nodes
    ~tNode(void)
    {
        //cout << "Deleting " << data << endl;
        delete left;
        delete right;
    }

    // Data members
    int data;
    tNode* left;
    tNode* right;
};

Функция ластика для рекурсии по дереву:

    void BinSearchTree::Erase(int n, tNode** N)
    {
        tNode* node = *N;
        if (root)
        {
            if (node->data > n) // post order, to avoid moving many times over
            {
                if (node->left)
                {
                    Erase(n, &node->left);
                }
            }
            else
            {
                if (node->right)
                {
                    Erase(n, &node->right);
                }
            }

            if (node->data == n)
            {
                RemoveNode(&node);
            }
        }
    }

И функция RemoveNode для обработки фактического удаления:

void BinSearchTree::RemoveNode(tNode** N)
{
    tNode* node = *N;
    if (!node->left && !node->right) // is leaf
    {
        delete node; // remove node
        size--;
        *N = NULL; // null pointer for above node/structure
    }
    else if (!node->left) // right child
    {
        tNode* temp = node->right; // to strip out copied node when finished
        node->data = node->right->data; // copy right node into current node
        node->right = node->right->right;
        node->left = node->right->left;

        temp->right = NULL; // NULL because node destructor is recursive
        temp->left = NULL; // ^^
        delete temp;
        size--;
    }
    else if (!node->right) // left child
    {
        tNode* temp = node->left; // to strip out copied node when finished
        node->data = node->left->data; // copy left node into current node
        node->right = node->left->right;
        node->left = node->left->left;

        temp->right = NULL; // NULL because node destructor is recursive
        temp->left = NULL; // ^^
        delete temp;
        size--;
    }
    else // 2 children
    {
        tNode* temp = node->right; // find ideal child -> left-most right child
        tNode* parent = NULL; // keep track of owner of ideal child
        while (temp->left)
        {
            parent = temp;
            temp = temp->left;
        }

        node->data = temp->data; // copy ideal child to root
        if (parent)
        {
            parent->left = temp->right; // case that left-most child has right child of it's own
        }
        RemoveNode(&temp);
        size--;
    }
}

Answer 1

Я думаю, что вижу это.Когда вы звоните RemoveNode() из Erase(), вы передаете ему значение &node.Вместо этого введите N.

Вот что происходит: строка tNode* node = *N; создает локальную переменную в стеке.A копия из *N.И хотя эта переменная имеет то же значение, что и * N (сначала), она хранится в другом месте в памяти: node находится в стеке, а *N где-то в куче.

Итак, так как вы передаете &node в RemoveNode(), node - это то, что изменяется.Не *N - это где-то еще.Но если вы проходите мимо, вы меняете то, что хотите.

Надеюсь, это поможет!

PS: Если это не ясно, дайте мне знать!Писать о двойных указателях может быть сложнее, чем их использовать ...

Answer 2

Избавьте себя от использования двойных указателей и просто используйте ссылку на указатель.Они имеют ту же семантику обычных указателей, но назначение их фактически изменит переданный указатель.

void BinSearchTree::Erase(int item, tNode*& node);

Кроме того, используйте выразительные имена и сохраните имена переменных из одной буквы для циклов.