二分探索木の非再帰トラバーサルの作成に取り組んでいます。ただし、いくつかの非常に奇妙なエラーが発生しています。
ここに私の横関数のコードがあります:
void BinarySearchTree<ItemType>::nrInOrderTraversal(void visit(ItemType&)) const
{
stack <int> nodeStack;
int *curPtr;
bool done = false;
while (!done)
{
if (rootPtr() != 0)
{
//Place pointer to node on stack before traversing the node's left subtree
nodeStack.push(rootPtr());
//Traverse the left subtree
rootPtr() = rootPtr()->getLeftChildPtr();
}
else //Backtrack from the empty subtree and visit the node at the top of the stack;
//however if the stack is empty, you are done.
{
if(!nodeStack.empty())
{
nodeStack.top(rootPtr());
visit(rootPtr()->getItem());
nodeStack.pop();
//Traverse the right subtree of the node just visited
rootPtr() = rootPtr()->getRightChildPtr();
}
else
done = true;
}
}
}
そして私のメインのトラバーサル部分のコード:
BinarySearchTree<string>* tree4Ptr = new BinarySearchTree<string>();
tree4Ptr->add("10");
tree4Ptr->add("20");
tree4Ptr->add("30");
tree4Ptr->add("40");
tree4Ptr->add("50");
tree4Ptr->add("60");
tree4Ptr->add("70");
tree4Ptr->add("80");
tree4Ptr->add("90");
tree4Ptr->add("100");
tree4Ptr->add("110");
tree4Ptr->add("120");
tree4Ptr->add("130");
tree4Ptr->add("140");
tree4Ptr->add("150");
tree4Ptr->add("160");
cout<<"Tree 4 nrInOrderTraversal: "<<endl;
tree4Ptr-> nrInOrderTraversal(display);
私が得ている特定のエラーは次のとおりです。
C:\Users\Maura\Documents\CSC2014\ATJprog6\BinarySearchTree.cpp|328|error: '((const BinarySearchTree<std::basic_string<char> >*)this)->BinarySearchTree<std::basic_string<char> >::rootPtr' cannot be used as a function|
C:\Users\Maura\Documents\CSC2014\ATJprog6\BinarySearchTree.cpp|331|error: '((const BinarySearchTree<std::basic_string<char> >*)this)->BinarySearchTree<std::basic_string<char> >::rootPtr' cannot be used as a function|
C:\Users\Maura\Documents\CSC2014\ATJprog6\BinarySearchTree.cpp|334|error: '((const BinarySearchTree<std::basic_string<char> >*)this)->BinarySearchTree<std::basic_string<char> >::rootPtr' cannot be used as a function|
C:\Users\Maura\Documents\CSC2014\ATJprog6\BinarySearchTree.cpp|334|error: '((const BinarySearchTree<std::basic_string<char> >*)this)->BinarySearchTree<std::basic_string<char> >::rootPtr' cannot be used as a function|
C:\Users\Maura\Documents\CSC2014\ATJprog6\BinarySearchTree.cpp|341|error: '((const BinarySearchTree<std::basic_string<char> >*)this)->BinarySearchTree<std::basic_string<char> >::rootPtr' cannot be used as a function|
C:\Users\Maura\Documents\CSC2014\ATJprog6\BinarySearchTree.cpp|342|error: '((const BinarySearchTree<std::basic_string<char> >*)this)->BinarySearchTree<std::basic_string<char> >::rootPtr' cannot be used as a function|
C:\Users\Maura\Documents\CSC2014\ATJprog6\BinarySearchTree.cpp|346|error: '((const BinarySearchTree<std::basic_string<char> >*)this)->BinarySearchTree<std::basic_string<char> >::rootPtr' cannot be used as a function|
C:\Users\Maura\Documents\CSC2014\ATJprog6\BinarySearchTree.cpp|346|error: '((const BinarySearchTree<std::basic_string<char> >*)this)->BinarySearchTree<std::basic_string<char> >::rootPtr' cannot be used as a function|
void display(string& anItem)
{
cout << "Displaying item - " << anItem << endl;
} // end display
一部の人々は rootPtr に関するヘッダー ファイルを求めていたので、ここにあります
/** Link-based implementation of the ADT binary search tree.
@file BinarySearchTree.h */
#ifndef _BINARY_SEARCH_TREE
#define _BINARY_SEARCH_TREE
#include "BinaryTreeInterface.h"
#include "BinaryNode.h"
#include "BinaryNodeTree.h"
#include "NotFoundException.h"
#include "PrecondViolatedExcep.h"
template<class ItemType>
class BinarySearchTree : public BinaryNodeTree<ItemType>
{
private:
BinaryNode<ItemType>* rootPtr;
protected:
//------------------------------------------------------------
// Protected Utility Methods Section:
// Recursive helper methods for the public methods.
//------------------------------------------------------------
// Recursively finds where the given node should be placed and
// inserts it in a leaf at that point.
BinaryNode<ItemType>* insertInorder(BinaryNode<ItemType>* subTreePtr,
BinaryNode<ItemType>* newNode);
// Removes the given target value from the tree while maintaining a
// binary search tree.
BinaryNode<ItemType>* removeValue(BinaryNode<ItemType>* subTreePtr,
const ItemType target,
bool& success);
// Removes a given node from a tree while maintaining a
// binary search tree.
BinaryNode<ItemType>* removeNode(BinaryNode<ItemType>* nodePtr);
// Removes the leftmost node in the left subtree of the node
// pointed to by nodePtr.
// Sets inorderSuccessor to the value in this node.
// Returns a pointer to the revised subtree.
BinaryNode<ItemType>* removeLeftmostNode(BinaryNode<ItemType>* subTreePtr,
ItemType& inorderSuccessor);
// Returns a pointer to the node containing the given value,
// or 0 if not found.
BinaryNode<ItemType>* findNode(BinaryNode<ItemType>* treePtr,
const ItemType& target) const;
public:
//------------------------------------------------------------
// Constructor and Destructor Section.
//------------------------------------------------------------
BinarySearchTree();
BinarySearchTree(const ItemType& rootItem);
BinarySearchTree(const BinarySearchTree<ItemType>& tree);
virtual ~BinarySearchTree();
//------------------------------------------------------------
// Public Methods Section.
//------------------------------------------------------------
bool isEmpty() const;
int getHeight() const;
int getNumberOfNodes() const;
ItemType getRootData() const throw(PrecondViolatedExcep);
void setRootData(const ItemType& newData) const throw(PrecondViolatedExcep);
bool add(const ItemType& newEntry);
bool remove(const ItemType& anEntry);
void clear();
ItemType getEntry(const ItemType& anEntry) const throw(NotFoundException);
bool contains(const ItemType& anEntry) const;
//------------------------------------------------------------
// Public Traversals Section.
//------------------------------------------------------------
void preorderTraverse(void visit(ItemType&)) const;
void inorderTraverse(void visit(ItemType&)) const;
void postorderTraverse(void visit(ItemType&)) const;
void nrInOrederTraversal(void visit (ItemType&)) const;
//------------------------------------------------------------
// Overloaded Operator Section.
//------------------------------------------------------------
BinarySearchTree<ItemType>& operator=(const BinarySearchTree<ItemType>& rightHandSide);
}; // end BinarySearchTree
#include "BinarySearchTree.cpp"
#endif