在程序中,我想为ADT二进制搜索树实现一个STL迭代器 . 迭代器应该使用按顺序遍历迭代二进制搜索树中的每个节点一次 . 我想使用LinkedStack,LinkedList或LinkedQueue来帮助跟踪节点 . 目前我正在尝试使用LinkedStack .
到目前为止,我的代码存在缺陷,我知道,在编译和运行测试时,我会遇到语法错误和错误 . 我不知道该做什么或修复什么 .
BinarySearchTreeIterator.h
#ifndef _BINARY_SEARCH_TREE_ITERATOR
#define _BINARY_SEARCH_TREE_ITERATOR
#include <iterator>
#include "LinkedStack.h"
template<class ItemType>
class LinkedList;
template <class ItemType>
class BinarySearchTreeIterator : public std::iterator<std::input_iterator_tag, int>
{
private:
const BinarySearchTree<ItemType>* tree;
const LinkedStack<ItemType> traversal;
public:
BinarySearchTreeIterator(const BinarySearchTree<ItemType>* someTree,
BinaryNode<ItemType>* itemPtr);
void fill_stack(BinaryNode<ItemType> treePtr);
const ItemType operator*();
BinarySearchTreeIterator<ItemType> operator ++();
bool operator == (const BinarySearchTreeIterator<ItemType>& rightHandSide) const;
bool operator != (const BinarySearchTreeIterator<ItemType>& rightHandSide) const;
}; // end BinarySearchTreeIterator
#endif
BinarySearchTreeIterator.cpp
#include "BinarySearchTreeIterator.h"
template <class ItemType>
BinarySearchTreeIterator<ItemType>::BinarySearchTreeIterator(const BinarySearchTree<ItemType>* someTree, BinaryNode<ItemType>* itemPtr)
{
tree = someTree;
fill_stack(itemPtr);
} // end constructor
template <class ItemType>
void fill_stack(BinaryNode<ItemType> treePtr)
{
if(treePtr != nullptr)
{
fill_stack(treePtr->getLeftChildPtr());
traversal.push(treePtr);
fill_stack(treePtr->getRightChildPtr());
}
} // end fill_stack
template <class ItemType>
const ItemType BinarySearchTreeIterator<ItemType>::operator*()
{
return traversal.peek();
} // end operator *
template <class ItemType>
BinarySearchTreeIterator<ItemType> BinarySearchTreeIterator<ItemType>::operator++()
{
traversal->pop();
return *this;
} // end operator ++
template <class ItemType>
bool BinarySearchTreeIterator<ItemType>::operator==(const BinarySearchTreeIterator<ItemType>& rightHandSide) const
{
bool isSameObj = traversal.isEmpty() && rightHandSide.traversal.isEmpty();
if(!isSameObj)
{
isSameObj = traversal.peek() == rightHandSide.traversal.peek();
}
return isSameObj && (tree == rightHandSide.tree);
} // end operator ==
template <class ItemType>
bool BinarySearchTreeIterator<ItemType>::operator!=(const BinarySearchTreeIterator<ItemType>& rightHandSide) const
{
return !operator==(rightHandSide);
} // end operator !=