// stutree.cpp - implementation file for tree.h
// Tree Assignment
// Justin McCreary
// Instructor: Mrs. Ames
// 11/13/08

#include <iostream>
using namespace std;

// ------------------- Public Gradetree members ----------------------
//
// These can be called from clients.
// Each has a corresponding recursive private member
// 
// -------------------------------------------------------------------

// default constructor
Gradetree::Gradetree ()
{
root = NULL;
}

// copy constructor - for deep copies
Gradetree::Gradetree (const Gradetree& othergradetree)
{
	root = copytree (othergradetree.root);
}

// destructor
Gradetree::~Gradetree ()
{
	destroytree (root);
}

// overload assignment for deep copies
void Gradetree::operator= (const Gradetree& othergradetree)
{
	root = copytree (othergradetree.root);
}

// visit inorder and display grades
void Gradetree::Inorder ()
{
	Inorder (root);
}

// visit preorder and display grades
void Gradetree::Preorder ()
{
	Preorder (root);
}

// visit postorder and display grades
void Gradetree::Postorder ()
{
	Postorder (root);
}

// display a sideways "picture" of the tree
void Gradetree::TreePicture ()
{
	Treepicture (root, 1);
}

// add a new grade to the tree
void Gradetree::Insert (int newgrade)
{
	Insert (root, newgrade);
}

// delete one occurrence of a grade from the tree
void Gradetree::Delete (int delgrade)
{
        Delete (root, delgrade);
}

// sum all of the grades
int Gradetree::SumGrades()
{
	SumGrades(root);
}

// adds the total number of grades
int Gradetree::NumGrades()
{
	NumGrades(root);
}

// returns the average grade
float Gradetree::AvgGrade()
{
	if(root==NULL)
                return 0;
        else
               return (1.0*SumGrades()/NumGrades());
}

// returns the number of nodes in the current tree
int Gradetree::NodeCount()
{
	NodeCount(root);
}

// returns the number of leaves in the current tree
int Gradetree::LeafCount()
{
	LeafCount(root);
}

// returns the number of nodes in the current tree which are not leaves
int Gradetree::NonLeafCount()
{
	NonLeafCount(root);
}

// returns true if the two trees are the same, else return false
bool Gradetree::SimilarTrees(Gradetree othertree)
{
	SimilarTrees(root, othertree.root);
}

// reutrns the height of the tree
int Gradetree::Height()
{
	Height(root);
}

// ------------------- Private Gradetree members ----------------------
// 
// These are used by the public members.
// They are necessary to facilitate the recursion.
//
// --------------------------------------------------------------------

// used by copy constructor and operator=
Treenode* Gradetree::copytree (Treenode* t)
{
    Treenode* tmp = NULL;  // for building copy of t

    if (t != NULL)
    {
	tmp = new Treenode;
	tmp->grade = t->grade;
	tmp->count = t->count;
	tmp->left = copytree (t->left);
	tmp->right = copytree (t->right);
    }

    return tmp;
}

// used by destructor
void Gradetree::destroytree (Treenode* t)
{
    if (t != NULL)
    {
	destroytree (t->left);
	destroytree (t->right);
	delete t;
    }
}

void Gradetree::Inorder (Treenode* t)
{
    if (t != NULL)
    {
	Inorder (t->left);
	cout << t->grade << " ";
	Inorder (t->right);
    }
}

void Gradetree::Preorder (Treenode* t)
{
    if (t != NULL)
    {
	cout << t->grade << " ";
	Preorder (t->left);
	Preorder (t->right);
    }
}

void Gradetree::Postorder (Treenode* t)
{
    if (t != NULL)
    {
	Postorder (t->left);
	Postorder (t->right);
	cout << t->grade << " ";
    }
}

void Gradetree::Treepicture (Treenode* t, int level)  // start w/ level == 1
{
    if (t != NULL)
    {
	Treepicture (t->right, level+1);
	for (int i = 1; i < level; i++)  // spacing to "drop" to correct level
		cout << "     ";
	cout << t->grade << "\n";
	Treepicture (t->left, level+1);
    }
}

void Gradetree::Insert (Treenode* &t, int newgrade)
{
    if (t == NULL)  // this is spot where grade belongs
    {
	t = new Treenode;
	t->grade = newgrade;
	t->count = 1;
	t->left = NULL;
	t->right = NULL;
    }
    else  if (newgrade > t->grade)
	Insert (t->right, newgrade);
    else  if (newgrade < t->grade)
	Insert (t->left, newgrade);
    else
	t->count++;
}

void Gradetree::Delete (Treenode* &t, int delgrade) 
{
    if (t == NULL) // grade is not in tree - abort!
        return;
    else if (delgrade < t->grade)
	Delete (t->left, delgrade);
    else if (delgrade > t->grade)
	Delete (t->right, delgrade);
    else  // match found
	if (t->count > 1)  // just subtract if >1 of this grade
	    t->count--;
	else               // need to delete grade node
	{
	    Treenode* temp = t;  // note t is actually parent link to node!
	    if (t->left == NULL && t->right == NULL)  // case 1: delete leaf
	    {
		t = NULL;
		delete temp;
	    }
	    else if (t->left == NULL)  // case 2: no left child, connect to right
	    {
		t = t->right;
		delete temp;
	    }
	    else if (t->right == NULL)  // case 2: no right child, connect to left
	    {
		t = t->left;
		delete temp;
	    }
	    else // yikes - it's a case 3 node!
	    {
		temp = t->left;                // once to left ...
		while (temp->right != NULL)    // ... all the way down right
		    temp = temp->right;    //     to immediate pred.
	        t->grade = temp->grade;        // copy pred to this node
		Delete (t->left, temp->grade); // now delete pred
	    }
	}
}

int Gradetree::SumGrades(Treenode* t)
{	
	if(t !=NULL)
	{
		// Adds the grades as well as the number of the same grades to get sum
		return (t->grade*t->count) + SumGrades(t->left) + SumGrades(t->right);
	}
	else
	{
		return 0;
	}
}

int Gradetree::NumGrades(Treenode* t)
{
        if(t !=NULL)
        {          
		// Adds together the number of grades      
      		return t->count + NumGrades(t->left) + NumGrades(t->right);
	}
	else
	{	//Returns 0 if null
		return 0;
	}
}


int Gradetree::NodeCount(Treenode* t)
{
        if(t !=NULL)
        {       // counts the number of nodes in a tree
                return 1 + NodeCount(t->left) + NodeCount(t->right);
        }
        else
        {       //returns 0 if null
                return 0;
	}
}

int Gradetree::LeafCount(Treenode* t) 
{                   
        int num;
        if(t ==NULL)
        {                                                                             
                 return 0;  
        }   
        else if(t->left == NULL && t->right == NULL) 
        {                
                return 1;
	}
	else
	{	// counts the number of leaf nodes in the tree
		return LeafCount(t->left) + LeafCount(t->right);
	}
}               

int Gradetree::NonLeafCount(Treenode* t)
{       
	int num;
        if(t ==NULL)
        {
                 return 0;
        }
        else if(t->left != NULL || t->right != NULL)
        {       // counts the number of nodes not leaves
                return 1 + NonLeafCount(t->right) + NonLeafCount(t->left);
        }
        else
        {   
                return 0;
        }
                
}               
               
bool Gradetree::SimilarTrees(Treenode* t, Treenode* othertree)
{	
	//checks to see if two trees are similar in shape
	if(t==NULL && othertree==NULL)
                return true;
        else if(t==NULL && othertree!=NULL)
                return false;
        else if(t!=NULL && othertree==NULL)
                return false;
        else if(t->left==NULL && othertree->left!=NULL)
                return false;
        else if(t->left!=NULL && othertree->left==NULL)
                return false;
        else if(t->right==NULL && othertree->right!=NULL)
                return false;
        else if(t->right!=NULL && othertree->right==NULL)
                return false;
        else
                return SimilarTrees(t->left, othertree->left) && SimilarTrees(t->right, othertree->right);

}

int Gradetree::Height(Treenode* t)
{
	if(t==NULL)
                return 0;
        else
        {	
                int hr = Height(t->right);
                int hl = Height(t->left);
		//counts the number of levels in the tree
                if(hl > hr)
                        return 1 + hl;
                else
                        return 1 + hr;
        }

}