块引用
如何在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（）函数时，这给了我诸如“类型的非常量引用的无效初始化”之类的错误。这是给我错误的行：std :: shared_ptr> tempPtr = removeLeftmostNode（nodePtr-> getRightChildPtr（），nodePtr-> getItem（））;
我认为这是因为我试图将引用函数调用为非引用函数。这里的问题是我不知道如何在不编辑头文件的情况下解决此问题。我只需要此功能即可正常工作。
最佳答案
removeLeftmostNode将引用作为第二个参数，但是getItem()返回一个临时值。临时不能绑定到非常量引用。您可以通过引入变量来保存此行来修复该行：
ItemType item = nodePtr->getItem();
std::shared_ptr<BinaryNode<ItemType>> tempPtr =
removeLeftmostNode(nodePtr->getRightChildPtr(), item);
这应该照顾到您显示的错误消息。