Метод removeNode в BinarySearchTree

Question

Blockquote

Как я могу реализовать removeNode () в BinarySearchTree.h?

// DEFINITION AND IMPLEMENTATION OF BinaryNode.h

#include <memory>

template<class ItemType>
class BinaryNode
{
private:
    ItemType item;           // Data portion
    std::shared_ptr<BinaryNode<ItemType>> leftChildPtr;   // Pointer to left child
    std::shared_ptr<BinaryNode<ItemType>> rightChildPtr;  // Pointer to right child

public:
    BinaryNode() : leftChildPtr(nullptr), rightChildPtr(nullptr) {};
    BinaryNode(const ItemType& anItem) : item(anItem), leftChildPtr(nullptr), rightChildPtr(nullptr) {};
    BinaryNode(const ItemType& anItem,
        std::shared_ptr<BinaryNode<ItemType>> leftPtr,
        std::shared_ptr<BinaryNode<ItemType>> rightPtr) : item(anItem), leftChildPtr(leftPtr), rightChildPtr(rightPtr) {};

    void setItem(const ItemType& anItem) {
        item = anItem;
    };


    ItemType getItem() const {
        return item;
    };


    bool isLeaf() const {
        return ((leftChildPtr == nullptr) && (rightChildPtr == nullptr));
    };

    std::shared_ptr<BinaryNode<ItemType>> getLeftChildPtr() const {
        return leftChildPtr;
    };

    std::shared_ptr<BinaryNode<ItemType>> getRightChildPtr() const {
        return rightChildPtr;
    };

    void setLeftChildPtr(std::shared_ptr<BinaryNode<ItemType>> leftPtr) {
        leftChildPtr = leftPtr;
    };

    void setRightChildPtr(std::shared_ptr<BinaryNode<ItemType>> rightPtr) {
        rightChildPtr = rightPtr;
    };
};

//DEFINITION OF BinarySearchTree.h
#include "BinaryNode.h"
#include "BinaryNodeTree.h"

#include <memory>

template<class ItemType>
class BinarySearchTree : public BinaryNodeTree<ItemType>
{
private:
    std::shared_ptr<BinaryNode<ItemType>> rootPtr;

protected:
    //------------------------------------------------------------
    //    Protected Utility Methods Section:
    //    Recursive helper methods for the public methods.
    //------------------------------------------------------------

    auto placeNode(std::shared_ptr<BinaryNode<ItemType>> subTreePtr,
        std::shared_ptr<BinaryNode<ItemType>> newNode);
    std::shared_ptr<BinaryNode<ItemType>> removeValue(std::shared_ptr<BinaryNode<ItemType>> subTreePtr,
        const ItemType target,
        bool& isSuccessful);
    std::shared_ptr<BinaryNode<ItemType>> removeNode(std::shared_ptr<BinaryNode<ItemType>> nodePtr);

    std::shared_ptr<BinaryNode<ItemType>> removeLeftmostNode(std::shared_ptr<BinaryNode<ItemType>>subTreePtr,
        ItemType & inorderSuccessor);
    std::shared_ptr<BinaryNode<ItemType>> findNode(std::shared_ptr<BinaryNode<ItemType>> treePtr,
        const ItemType& target) const;

public:
    //------------------------------------------------------------
    // Constructor and Destructor Section.
    //------------------------------------------------------------
    BinarySearchTree();
    BinarySearchTree(const ItemType& rootItem);
    BinarySearchTree(const BinarySearchTree<ItemType>& tree);


};

//IMPLEMENTATION OF BinarySearchTree.cpp
template<class ItemType>
auto BinarySearchTree<ItemType>::placeNode(std::shared_ptr<BinaryNode<ItemType>> subTreePtr,
    std::shared_ptr<BinaryNode<ItemType>> newNode) {
    if (subTreePtr == nullptr)
        return newNode;
    else if (subTreePtr->getItem() > newNode->getItem()) {
        auto tempPtr = placeNode(subTreePtr->getLeftChildPtr(), newNode);
        subTreePtr->setLeftChildPtr(tempPtr);
    }
    else {
        auto tempPtr = placeNode(subTreePtr->getRightChildPtr(), newNode);
        subTreePtr->setRightChildPtr(tempPtr);
    }
    return subTreePtr;
}

template<class ItemType>
std::shared_ptr<BinaryNode<ItemType>> BinarySearchTree<ItemType>::removeValue(std::shared_ptr<BinaryNode<ItemType>> subTreePtr,
    const ItemType target, bool & isSuccessful)
{
    std::shared_ptr<BinaryNode<ItemType>> tempPtr;
    if (subTreePtr == nullptr)
    {
        isSuccessful = false;

    }
    else if (subTreePtr->getItem() == target)
    {
        subTreePtr = removeNode(subTreePtr);
        isSuccessful = true;

    }
    else if (subTreePtr->getItem() > target)
    {
        tempPtr = removeValue(subTreePtr->getLeftChildPtr(), target, isSuccessful);
        //std::shared_ptr<BinaryNode<ItemType>> tempPtr = removeValue(subTreePtr->getLeftChildPtr(), target, isSuccessful);
        subTreePtr->setLeftChildPtr(tempPtr);

    }
    else
    {
        tempPtr = removeValue(subTreePtr->getRightChildPtr(), target, isSuccessful);
        //std::shared_ptr<BinaryNode<ItemType>> tempPtr = removeValue(subTreePtr->getRightChildPtr(), target, isSuccessful);
        subTreePtr->setRightChildPtr(tempPtr);

    }
    return subTreePtr;

}
template <class ItemType>
std::shared_ptr<BinaryNode<ItemType>> BinarySearchTree<ItemType>::removeNode(std::shared_ptr<BinaryNode<ItemType>> nodePtr) {
    if (nodePtr->isLeaf()) {
        nodePtr = nullptr;
        return nodePtr;
    }
    else if ((nodePtr->getLeftChildPtr() != nullptr) || (nodePtr->getRightChildPtr() != nullptr)) {
        std::shared_ptr<BinaryNode<ItemType>> nodeToConnectPtr;
        if (nodePtr->getLeftChildPtr() != nullptr) {
           nodeToConnectPtr = nodePtr->getLeftChildPtr();
        }
        else {
         nodeToConnectPtr = nodePtr->getRightChildPtr();
         }
         return nodeToConnectPtr;
        }
    else
    {
            std::shared_ptr<BinaryNode<ItemType>> tempPtr = removeLeftmostNode(nodePtr->getRightChildPtr(), nodePtr->getItem());
            nodePtr->setRightChildPtr(tempPtr);
            nodePtr->setItem(nodePtr->getItem());
            return nodePtr;
    }
 }
template <class ItemType>
bool BinarySearchTree <ItemType>::remove(const ItemType& target) {
    bool isSuccessful = false;
    rootPtr = removeValue(rootPtr, target, isSuccessful);
    return isSuccessful;
}

template<class ItemType>
std::shared_ptr<BinaryNode<ItemType>> BinarySearchTree<ItemType>::removeLeftmostNode(std::shared_ptr<BinaryNode<ItemType>> subTreePtr, ItemType& inorderSuccessor)
{
    if (subTreePtr->getLeftChildPtr() == nullptr)
    {
        inorderSuccessor = subTreePtr->getItem();
        return removeNode(subTreePtr);
    }
    else
    {
        std::shared_ptr<BinaryNode<ItemType>>tempPtr = removeLeftmostNode(subTreePtr->getLeftChildPtr(), inorderSuccessor);
        subTreePtr->setLeftChildPtr(tempPtr);
        return subTreePtr;
    }
    return subTreePtr;
}

template <class ItemType>
std::shared_ptr<BinaryNode<ItemType>>BinarySearchTree<ItemType>::findNode(std::shared_ptr<BinaryNode<ItemType>> treePtr,
    const ItemType& target) const{
    if (treePtr == nullptr)
        return nullptr;
    else if (treePtr->getItem() == target)
        return treePtr;
    else if (treePtr->getItem() > target)
        return findNode(treePtr->getLeftChildPtr(), target);
    else
        return findNode(treePtr->getRightChildPtr(), target);
}

template <class ItemType>
BinarySearchTree<ItemType>::BinarySearchTree() {

}

template <class ItemType>
BinarySearchTree<ItemType>::BinarySearchTree(const ItemType& rootItem)
{
    rootPtr.reset(new BinaryNode<ItemType>(rootItem));
}

template <class ItemType>
BinarySearchTree<ItemType>::BinarySearchTree(const BinarySearchTree<ItemType>& tree)
//:BinaryNodeTree(const BinaryNodeTree<ItemType>& tree)
{
    rootPtr = BinaryNodeTree<ItemType>::copyTree(tree.rootPtr);

}

Это дает мне ошибки типа "неверная инициализация неконстантныхссылка типа "когда я вызываю функцию removeLeftmostNode () в BinarySearchTree для удаления функции () в BinarySearchTree. Это строка, которая дает мне ошибку: std :: shared_ptr> tempPtr = removeLeftmostNode (nodePtr-> getRightChildPtr (), nodePtr-> getItem ());Я думаю, что это потому, что я пытаюсь вызвать ссылочную функцию для не-ссылочной функции. Проблема здесь в том, что я не знаю, как решить эту проблему без редактирования файла заголовка. Мне просто нужна эта функция для правильной работы.

Answer 1

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

ItemType item = nodePtr->getItem();
std::shared_ptr<BinaryNode<ItemType>> tempPtr =
    removeLeftmostNode(nodePtr->getRightChildPtr(), item);

Это должно позаботиться о отображаемом сообщении об ошибке.