Listing 6: Code for inorder iterator

// inorder iterator constructors and destructor
template <class DataType>
BinaryTreeIterator_InOrder<DataType>::BinaryTreeIterator_InOrder(
    const BinaryTreeIterator_InOrder<DataType> &iter): 
    BinaryTreeIterator_PreOrder<DataType>(iter)
{
}

template <class DataType>
BinaryTreeIterator_InOrder<DataType>::BinaryTreeIterator_InOrder(
    const BinaryTree<DataType> &bt): 
    BinaryTreeIterator_PreOrder<DataType>(bt)
{
    reset();
}

template <class DataType>
BinaryTreeIterator_InOrder<DataType>::~BinaryTreeIterator_InOrder()
{
}

// reset iterator to beginning
template <class DataType>
void BinaryTreeIterator_InOrder<DataType>::reset()
{
    stack.clear();
    for (BinaryTreeNode<DataType> *pn = tree->root; 
        pn != NULL; pn = pn->left)
    {
        stack.push(pn);
    }
    return;
}

// increment to next data item in list
template <class DataType>
int BinaryTreeIterator_InOrder<DataType>::operator++(int)
{
    // is iterator done
    if (stack.isEmpty()) return(NOTOK);

    // get next node from stack
    BinaryTreeNode<DataType> *btn;
    MustBeTrue(stack.pop(btn) == OK);

    // insert right node left links into stack
    if (btn->right != NULL)
    {
        for (BinaryTreeNode<DataType> *pn = btn->right;
            pn != NULL; pn = pn->left)
        {
            stack.push(pn);
        }
    }
    return(OK);
}
/* End of File */