/* File: bintree.C      Copyright glh 8/15/94 */
#include "bintree.H"

template<class T>
ostream& operator<<(ostream& os, const Bnode<T>& v)
{
  os << v.data;
  return os;
}

template<class T>
BinaryTree<T>::BinaryTree(const T& elm) 
{
  root = new Bnode<T>(elm);
  assert(root != 0);
  root->parent = 0;
}

template<class T>
Boolean BinaryTree<T>::InsertLeaf(Bnode<T>* leaf, Bnode<T>* prnt, Child lr)
{
  if (prnt == 0)  // inserting root
    if (root != 0)
      return false;
    else
      root = leaf;
  else {
    leaf->parent = prnt;
    if (lr == left) { // inserting a left child
      if (prnt->lchild == 0)
        prnt->lchild = leaf;
      else 
        return false;
    }
    else {  // inserting a right child
      if (prnt->rchild == 0)
        prnt->rchild = leaf;
      else
        return false;
    }
  }
  return true;
}

template<class T>
void BinaryTree<T>::DeleteSubtree(Bnode<T>* v)
{ 
  if (v->lchild != 0)
    DeleteSubtree(v->lchild);
  if (v->rchild != 0)
    DeleteSubtree(v->rchild);
  delete v;
}

template<class T>
void BinaryTree<T>::MakeEmpty()
{ 
  if (root != 0)
    DeleteSubtree(root);
  root = 0;
}

template<class T>
void BinaryTree<T>::InorderSubtreePrint(ostream& os, Bnode<T>* v) const
{
  if (v != 0) {
    if (v->lchild != 0)
      InorderSubtreePrint(os, v->lchild);
    os << *v << ", ";
    if (v->rchild != 0)
      InorderSubtreePrint(os, v->rchild);
  }
}

template<class T>
ostream& operator<<(ostream& os, const BinaryTree<T>& tree)
{
  os << "(";
  if (tree.root != 0) {
    tree.InorderSubtreePrint(os, tree.root);
    os << "\b)";
  }
  else
    os << ")";
  return os;
}