c++ - BinarySearchTree 中的 removeNode 方法

Question

Blockquote

如何在 BinarySearchTree.h 中实现 removeNode()？

// 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);

}

当我将 BinarySearchTree 中的 removeLeftmostNode() 函数调用到 BinarySearchTree 中的 removeNode() 函数时，出现“类型的非 const 引用的无效初始化”之类的错误。这是给我错误的行: std::shared_ptr> tempPtr = removeLeftmostNode(nodePtr->getRightChildPtr(), nodePtr->getItem()); 我认为这是因为我试图将引用函数调用到非引用函数。这里的问题是我不知道如何在不编辑头文件的情况下解决这个问题。我只需要此功能即可正常工作。

Answer 1

removeLeftmostNode 将引用作为其第二个参数，但 getItem() 返回一个临时值。临时不能绑定(bind)到非常量引用。您可以通过引入一个变量来保存该项目来修复此行:

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

这应该会处理您显示的错误消息。