Listing 4: Binary tree header

#ifndef __BINARY_TREE2_H
#define __BINARY_TREE2_H
// binary search tree class definition using recursion

// headers
#include "absTree.h"
#include "absIterator.h"
#include "queue_List.h"
#include "stack_List.h"

// forward declarations
template <class DataType> class BinaryTreeNode;
template <class DataType> class BinaryTree;
template <class DataType> class BinaryTreeIterator_PreOrder;
template <class DataType> class BinaryTreeIterator_InOrder;
template <class DataType> class BinaryTreeIterator_PostOrder;
template <class DataType> class BinaryTreeIterator_LevelOrder;

// tree node class
template <class DataType> class BinaryTreeNode
{
public:
    // output
    friend ostream &operator<<(ostream &os, 
        const BinaryTreeNode<DataType> &btn) {
        os << btn.data;
        return(os);
    };

protected:
    // friend classes 
    friend class BinaryTree<DataType>;
    friend class BinaryTreeIterator_PreOrder<DataType>;
    friend class BinaryTreeIterator_InOrder<DataType>;
    friend class BinaryTreeIterator_PostOrder<DataType>;
    friend class BinaryTreeIterator_LevelOrder<DataType>;

    // constructors and destructor
    BinaryTreeNode(const DataType &);
    BinaryTreeNode(const BinaryTreeNode &);
    ~BinaryTreeNode();

    // assignment
    BinaryTreeNode &operator=(const BinaryTreeNode &);

    // internal data
    DataType data;
    BinaryTreeNode<DataType> *left;
    BinaryTreeNode<DataType> *right;
};

// binary search tree class
template <class DataType> class BinaryTree:
    public AbstractTree<DataType>
{
public:
    // friend classes 
    friend class BinaryTreeIterator_PreOrder<DataType>;
    friend class BinaryTreeIterator_InOrder<DataType>;
    friend class BinaryTreeIterator_PostOrder<DataType>;
    friend class BinaryTreeIterator_LevelOrder<DataType>;

    // constructors and destructor
    BinaryTree();
    BinaryTree(const BinaryTree &);
    ~BinaryTree();

    // assignment
    BinaryTree &operator=(const BinaryTree &);

    // binary tree operations
    void insert(const DataType &);
    int remove(DataType &);
    int retrieve(DataType &) const;
    int isInTree(const DataType &) const;
    int isEmpty() const;
    void clear();
    .
    .
    .

protected:
    // utility functions
    .
    .
    .

protected:
    // internal data
    BinaryTreeNode<DataType> *root;
};

// pre-order tree iterator
template <class DataType> class BinaryTreeIterator_PreOrder:
    public AbstractIterator<DataType>
{
public:
    // constructors and destructor
    BinaryTreeIterator_PreOrder(
        const BinaryTree<DataType> &);
    BinaryTreeIterator_PreOrder(
        const BinaryTreeIterator_PreOrder<DataType> &);
    ~BinaryTreeIterator_PreOrder();

    // reset interator to start
    void reset();

    // check if at end of list
    int done() const;

    // return data 
    DataType operator()();

    // advance iterator to next link
    int operator++(int);

private:
    // not allowed
    BinaryTreeIterator_PreOrder();
    BinaryTreeIterator_PreOrder &operator=(const 
        BinaryTreeIterator_PreOrder &);

protected:
    // internal data
    const BinaryTree<DataType> *tree;
    Stack_List<BinaryTreeNode<DataType> * > stack;
};

// in-order tree iterator
template <class DataType> class BinaryTreeIterator_InOrder:
    public BinaryTreeIterator_PreOrder<DataType>
{
public:
    // constructors and destructor
    BinaryTreeIterator_InOrder(
        const BinaryTree<DataType> &);
    BinaryTreeIterator_InOrder(
        const BinaryTreeIterator_InOrder<DataType> &);
    ~BinaryTreeIterator_InOrder();

    // reset interator to start
    void reset();

    // advance iterator to next link
    int operator++(int);

private:
    // not allowed
    BinaryTreeIterator_InOrder();
    BinaryTreeIterator_InOrder &operator=(const 
        BinaryTreeIterator_InOrder &);
};

// post-order tree iterator
template <class DataType> class BinaryTreeIterator_PostOrder:
    public BinaryTreeIterator_PreOrder<DataType>
{
public:
    // constructors and destructor
    BinaryTreeIterator_PostOrder(
        const BinaryTree<DataType> &);
    BinaryTreeIterator_PostOrder(
        const BinaryTreeIterator_PostOrder<DataType> &);
    ~BinaryTreeIterator_PostOrder();

    // reset interator to start
    void reset();

    // advance iterator to next link
    int operator++(int);

private:
    // not allowed
    BinaryTreeIterator_PostOrder();
    BinaryTreeIterator_PostOrder &operator=(const 
        BinaryTreeIterator_PostOrder &);

protected:
    // internal data
    Stack_List<int> vstack;
};

// level-order tree iterator
template <class DataType> class BinaryTreeIterator_LevelOrder:
    public AbstractIterator<DataType>
{
public:
    // constructors and destructor
    BinaryTreeIterator_LevelOrder(
        const BinaryTree<DataType> &);
    BinaryTreeIterator_LevelOrder(
        const BinaryTreeIterator_LevelOrder<DataType> &);
    ~BinaryTreeIterator_LevelOrder();

    // reset interator to start
    void reset();

    // check if at end of list
    int done() const;

    // return data 
    DataType operator()();

    // advance iterator to next link
    int operator++(int);

private:
    // not allowed
    BinaryTreeIterator_LevelOrder();
    BinaryTreeIterator_LevelOrder &operator=(const 
        BinaryTreeIterator_LevelOrder &);

protected:
    // internal data
    const BinaryTree<DataType> *tree;
    Queue_List<BinaryTreeNode<DataType> * > queue;
};

#endif
/* End of File */