// tree.cpp - a binary search tree example

#include <stdlib.h>
#include <iostream.h>

class Treenode{
  private:
    int data;
    Treenode * left;
    Treenode * right;
  public:
    Treenode();
    Treenode(int);
    Treenode(int,Treenode *,Treenode *);
    ~Treenode();
    int getData();
    Treenode *&getLeft();
    Treenode *&getRight();
    void setData(int);
    void setLeft(Treenode *);
    void setRight(Treenode *);
};

Treenode::Treenode(){
  data = 0;
  left = right = NULL;
}

Treenode::Treenode(int d){
  data = d;
  left = right = NULL;
}

Treenode::Treenode(int d, Treenode *l, Treenode *r){
  data = d;
  left = l;
  right = r;
}

Treenode::~Treenode(){
}

int Treenode::getData(){
  return data;
}

Treenode *& Treenode::getLeft(){
  return left;
}

Treenode *& Treenode::getRight(){
  return right;
}

void Treenode::setData(int d){
  data = d;
}

void Treenode::setLeft(Treenode *l){
  left = l;
}

void Treenode::setRight(Treenode *r){
  right = r;
}

class Tree{
  private:
    Treenode *root;
  public:
    Tree();
    Tree(int);
    Tree(int,Treenode *,Treenode *);
    Tree(const Tree &);
    ~Tree();
    bool isEmpty() const;
    void insert(int);
    void preorder();
    void inorder();
    void postorder();
    Tree & operator=(const Tree &);
    void testmakeEmpty();	// remove after testing
    void testcopy(Tree *);	// remove after testing
  private:
    void makeEmpty(Treenode *&);
    void insertData(int,Treenode *&);
    void visit(Treenode *);
    void InOrder(Treenode *);
    void PreOrder(Treenode *);
    void PostOrder(Treenode *);
    void copyTree(Treenode *,Treenode *&) const;
};

// remove this after testing
void Tree::testmakeEmpty(){
  makeEmpty(root);
}

Tree::Tree(){
  root = NULL;
}

Tree::Tree(int data){
  root = new Treenode(data,NULL,NULL);
}

Tree::Tree(int data,Treenode *l,Treenode *r){
  root = new Treenode(data,l,r);
}

Tree::Tree(const Tree &t){
  copyTree(t.root,root);
}

Tree::~Tree(){
  makeEmpty(root);
}

// deletes all nodes in tree t
void Tree::makeEmpty(Treenode *& t){
  if (t != NULL){
    makeEmpty(t->getLeft());
    makeEmpty(t->getRight());
    delete(t);
    t = NULL;
  }
}

// remove this after testing
void Tree::testcopy(Tree *newtree){
  copyTree(this->root,newtree->root);
}

void Tree::copyTree(Treenode *oldnode,Treenode * &newnode) const{
  if(oldnode != NULL){
    newnode = new Treenode(oldnode->getData(),NULL,NULL);
    copyTree(oldnode->getLeft(),newnode->getLeft());
    copyTree(oldnode->getRight(),newnode->getRight());
  }
  else
    newnode = NULL;
}

bool Tree::isEmpty() const{
  return (root == NULL);
}

// overloaded assignment operator
Tree & Tree::operator=(const Tree & t){
  if(this != &t){
    makeEmpty(root);
    copyTree(t.root,root);
  }
  return *this;
}

// public helper to insert item into tree
void Tree::insert(int data){
  insertData(data,root);
}

// private function does insertion
void Tree::insertData(int data, Treenode * &t){
  if(t == NULL)
    t = new Treenode(data,NULL,NULL);
  else if(data <= t->getData())
    insertData(data,t->getLeft());
  else
    insertData(data,t->getRight());
}

// public helper for PreOrder()
void Tree::preorder(){
  PreOrder(root);
  cout << endl;
}

// private function that does preorder traversal of tree 
void Tree::PreOrder(Treenode *t){
  if(t != NULL){
    visit(t);
    PreOrder(t->getLeft());
    PreOrder(t->getRight());
  }
}

//  public helper for InOrder traversal
void Tree::inorder(){
  InOrder(root);
  cout << endl;
}

// private inorder tree traversal
void Tree::InOrder(Treenode *p){
  if(p != NULL){
    InOrder(p->getLeft());
    visit(p);
    InOrder(p->getRight());
  }
}

// public helper for PostOrder traversal
void Tree::postorder(){
  PostOrder(root);
  cout << endl;
}

// private postorder tree traversal
void Tree::PostOrder(Treenode *t){
  if(t != NULL){
    PostOrder(t->getLeft());
    PostOrder(t->getRight());
    visit(t);
  }
}

// prints out parent node of subtree
void Tree::visit(Treenode *t){
  cout << t->getData() << " ";
}

int main(){
  Tree *t = new Tree;
  Tree *r = new Tree;
  Tree *v = new Tree;

  t->insert(-3);
  t->insert(1);
  t->insert(5);
  t->insert(-8);
  t->preorder();
  t->inorder();
  t->postorder();

  cout << "Testing copy" << endl;
  cout << "t = ";
  t->inorder();
  t->testcopy(r);
  cout << "r = ";
  r->inorder();

  cout << "Testing makeEmpty" << endl;
  t->testcopy(v);
  cout << "v = ";
  v->inorder();
  t->testmakeEmpty();
  cout << "t = ";
  t->inorder();
  cout << "v = ";
  v->inorder();

  return 0;
}