/* File: bintree.H      Copyright glh 8/15/94 */
#ifndef BINTREEH
#define BINTREEH
#include <iostream.h>
#include <assert.h>

typedef enum {false, true} Boolean;
typedef enum {left, right} Child;

// forward references for template classes
template <class Type> class BinaryTree;
template <class Type> class BST;

template<class T>
class Bnode {
  friend class BinaryTree<T>;
  friend class BST<T>;
  friend ostream& operator<<(ostream&, const BinaryTree<T>&);
  protected:
    T data;
    Bnode<T>* parent;
    Bnode<T>* lchild;
    Bnode<T>* rchild;
  public:
    Bnode() {} 
    Bnode(const T& elm) : data(elm), parent(0), lchild(0), rchild(0) {}
    friend ostream& operator<<(ostream& os, const Bnode<T>& v);
};

template<class T>
class BinaryTree {
  protected:
    Bnode<T>* root; 
  public:
    BinaryTree() : root(0) {}
    BinaryTree(const T& elm);
    inline ~BinaryTree();
    inline Bnode<T>* Root();
    inline Bnode<T>* LeftChild(Bnode<T>* nd);
    inline Bnode<T>* RightChild(Bnode<T>* nd);
    Boolean InsertLeaf(Bnode<T>* leaf, Bnode<T>* prnt, Child lr);
    inline Boolean Empty();
    void DeleteSubtree(Bnode<T>*);
    void MakeEmpty();
    void InorderSubtreePrint(ostream& os, Bnode<T>*) const;
    friend ostream& operator<<(ostream& os, const BinaryTree<T>& tree);
};

template<class T>
inline BinaryTree<T>::~BinaryTree() {MakeEmpty();}

template<class T>
inline Bnode<T>* BinaryTree<T>::LeftChild(Bnode<T>* nd)
{return nd->lchild;}

template<class T>
inline Bnode<T>* BinaryTree<T>::RightChild(Bnode<T>* nd)
{return nd->rchild;}

template<class T>
inline Bnode<T>* BinaryTree<T>::Root() {return root;}

template<class T>
inline Boolean BinaryTree<T>::Empty() {return root == 0 ? true : false;}

#endif