在程序中,我想为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 !=