/*----------------------------------------------------------------------------
FILE NAME:     tree.cpp
               BASIC DEFINITIONS FOR CLASS bTree AND MORE
               ECE 1320 Winter 2003

AUTHOR:        Stefano Basagni

CREATED:       February/March 2003

DESCRIPTION:   Example of a simple C++ program to test functions on 
               trees.

---
Copyright (C) 2003 Stefano Basagni

This program is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License
as published by the Free Software Foundation; either version 2
of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

To receive a copy of the GNU General Public License write to
the Free Software Foundation, Inc., 59 Temple Place - Suite
330, Boston, MA 02111-1307, USA.

Stefano Basagni can be contacted at basagni@ece.neu.edu.

----------------------------------------------------------------------------*/
// INCLUDE SECTION
#include <iostream>
#include <iomanip>
#include <cmath>
#include <string>
#include <ctime>
#include <cstdlib>
#include <algo.h>

using namespace std;

// CONSTANT SECTION
const int MAXINT = 65536;

// CLASSES DEFS
// Def. of a tree node
class tNode {
public:
  tNode();
  tNode( int eVal, tNode* lVal = NULL, tNode* rVal = NULL ) {
    elem = eVal; 
    l = lVal;
    r = rVal;
  }
  int getElem() const { return elem; }
  void setElem( int eVal ) { elem = eVal; }
  tNode* getLeft() { return l; }
  void setLeft( tNode* lVal = NULL ) { l = lVal; }
  tNode* getRight() { return r   ; }
  void setRight( tNode* rVal = NULL ) { r = rVal; }

private:
  int elem;
  tNode* l;
  tNode* r;
};

// Def. of a binary tree: Interfaces (methods)
class bTree {
public:
  bTree() { init(); }
  bTree( int n );

  tNode* getRoot() { return root; }
  void setRoot( tNode* r ) { root = r; }
  void printTree( tNode *t, int inc, int space );
  bool isEmpty() const { return root == NULL; }
  int getsize() const { return size; }
  void insert( const int e );
  void preOrder( tNode* t );
  void inOrder( tNode* t );
  void postOrder( tNode* t );
  bool isIn( tNode* t, const int e );
  int depth( tNode* t );
  int countE( tNode* t, const int e );

private:
  tNode* root;
  int size;
  void init() {
    root = NULL;
    size = 0;
  }
};

// Def. of a binary tree: Implementations
// Create a tree with n (random) nodes
// Here from 1 to 100 inclusive
bTree::bTree( int n ) {
  srand( time( 0 ) );
  init();
  for( int a = 0; a < n; a++ )
    insert( 1 + rand() % 100 );
}

// Print the tree
void bTree::printTree( tNode* t, int inc, int space ) {
  while ( t != NULL ) {
    printTree( t -> getRight(), inc, space + inc );
    for( int i = 0; i < space; i++ )
		cout << " ";
    cout << t -> getElem() << endl;
    t = t -> getLeft();
    space += inc;
  }
}

// Insert a new node as the new root and place the old root
// randomly as either the right or the left child
void bTree::insert( const int e ) {
  int rn =  rand();
  tNode* temp = new tNode( e );
  if ( rn % 2 == 0 ) 
	 temp -> setLeft( root );
  else 
	 temp -> setRight( root ); 
  root = temp;
  size++;
}

// VISITS
void bTree::preOrder( tNode* t ) {
  if ( t != NULL ) {
    cout << ( t -> getElem() ) << " ";
    preOrder( t -> getLeft() );
    preOrder( t -> getRight() );
  }
  else 
    cout << "# ";
} 

void bTree::inOrder( tNode* t ) {
  if ( t != NULL ) {
    inOrder( t -> getLeft() );
    cout << t -> getElem() << " ";
    inOrder( t -> getRight() );
  }
} 

void bTree::postOrder( tNode* t ) {
  if ( t != NULL ) {
    postOrder( t -> getLeft() );
    postOrder( t -> getRight() );
    cout << t -> getElem() << " ";
  }
} 

// Check whether a node with a given element is in the tree
bool bTree::isIn( tNode* t, const int e ) {
  if ( t == NULL )
	 return false;
  else {
    if ( t -> getElem() == e )
      return true;
    else
      return ( isIn( t -> getLeft(), e ) 
            || isIn( t -> getRight(), e ) );
  }
}

// Compute the depth of the tree
int bTree::depth( tNode* t ) {
  if ( t == NULL ) 
    return 0;
  else 
    return max( depth( t -> getLeft() ), 
					 depth( t -> getRight() ) ) + 1 ;
}

// Count the number of nodes whose element is e
int bTree::countE( tNode* t, const int e ) {
  if ( t == NULL ) 
    return 0;
  else 
    if ( t -> getElem() == e )
      return 1 + countE( t -> getLeft(), e ) + 
		  countE( t -> getRight(), e );
    else
      return countE( t -> getLeft(), e ) + 
		  countE( t -> getRight(), e );
}

// PROTOTYPES FOR HMW FUNCTIONS


//---------------------------------------------------------------------
// MAIN
int main() {

  int nn = 10;

  // Creating an empty list
  bTree bt;

  // Checking isEmpty
  if ( bt.isEmpty() )
    cout << "The tree just created is empty." << endl;

  // Creating a list with nn elements
  bTree tt( nn );

  // Testing print list
  tt.printTree( tt.getRoot(), 3, 0 );

  return 0;

}
  
//---------------------------------------------------------------------
// FUNCTION DEFS
//---------------------------------------------------------------------
//