Listing 7: Code for level-order iterator

// levelorder iterator constructors and destructor
template <class DataType>
BinaryTreeIterator_LevelOrder<DataType>::
    BinaryTreeIterator_LevelOrder(
        const BinaryTreeIterator_LevelOrder<DataType> &iter):
        tree(iter.tree), queue(iter.queue)
{
}

template <class DataType>
BinaryTreeIterator_LevelOrder<DataType>::
    BinaryTreeIterator_LevelOrder(
        const BinaryTree<DataType> &bt): 
        tree(&bt), queue()
{
    reset();
}

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

// reset iterator to beginning
template <class DataType>
void BinaryTreeIterator_LevelOrder<DataType>::reset()
{
    queue.clear();
    queue.enqueue(tree->root);
    return;
}

// is list empty
template <class DataType>
int BinaryTreeIterator_LevelOrder<DataType>::done() const
{
    return(queue.isEmpty());
}

// return current data
template <class DataType>
DataType BinaryTreeIterator_LevelOrder<DataType>::operator()()
{
    BinaryTreeNode<DataType> *btn;
    MustBeTrue(queue.front(btn) == OK);
    return(btn->data);
}

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

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

    // queue up left and right nodes, if any.
    if (btn->left != NULL)
        queue.enqueue(btn->left);
    if (btn->right != NULL)
        queue.enqueue(btn->right);
    return(OK);
}
/* End of File */