Блог

Главная - Вопросы по программированию - Удаление странного узла в дереве двоичного поиска

Удаление странного узла в дереве двоичного поиска

#c #data-structures

#c #структуры данных

Вопрос:

Я выпишу по британскому летнему времени, который содержит некоторые данные, и я пытаюсь реализовать функцию для удаления одного элемента из по британскому летнему времени.

В настоящее время моя recursiveDelete() функция выглядит следующим образом, и она работает! В зависимости от вашего определения работ. Вместе с ним появляются некоторые другие узлы.

 template <typename ItemType, typename KeyType>
BNode<ItemType>* BinarySearchTree<ItemType, KeyType>::recDeleteNode(KeyType key, BNode<ItemType> *subtree)
{
    if (subtree == nullptr) 
    {
        return subtree;
    }
    else if (subtree->getItem() > key)
    {
        subtree->setLeft(recDeleteNode(key, subtree->getLeft()));
    }
    else if (subtree->getItem() < key)
    {
        subtree->setRight(recDeleteNode(key, subtree->getRight()));
    }
    else 
    {
        if (subtree->getLeft() == nullptr amp;amp; subtree->getRight() == nullptr)
        {
            delete subtree;
            subtree = nullptr;
        }
        else if (subtree->getLeft() == nullptr)
        {
            BNode<ItemType> *temp = subtree;
            subtree = subtree->getRight();
            delete temp;
        }
        else if (subtree->getRight() == nullptr)
        {
            BNode<ItemType> *temp = subtree;
            subtree = subtree->getRight();
            delete temp;
        }
        else
        {
            BNode<ItemType> *temp = minValueNode(subtree->getRight());
            temp->setLeft(subtree->getLeft());
            temp = subtree;
            subtree = subtree->getRight();
            delete temp;
        }
    }

    return subtree;
}

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

Я некоторое время смотрел на это, но я не вижу, что могло бы заставить его вытащить другие узлы вместе с ним.

Комментарии:

1. Кажется, вы реализуете метод BinarySearchTree класса, но, похоже, вы ничего не делаете с this объектом; вы работаете только с поддеревом. Тогда почему это метод класса? В любом случае, ответ Дэвида Шварца кажется правильным.

2. Поскольку он рекурсивный, в этом случае вызывается родительская функция delete(KeyType key) , которая запускает рекурсивный вызов в корне. Это продолжается по дереву в контексте каждого поддерева. Это прославленный поиск, маскирующийся под функцию удаления.

Ответ №1:

     else if (subtree->getRight() == nullptr)
    {
        BNode<ItemType> *temp = subtree;
        subtree = subtree->getRight(); // this is nullptr
        delete temp;
    }

Это getRight должно быть getLeft .

Метки: