// stutree.cpp - implementation file for tree.h

#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);
}

int Gradetree::SumGrades()
{
	SumGrades(root);
}

int Gradetree::NumGrades()
{
	NumGrades(root);
}

float Gradetree::AvgGrade()
{
	return SumGrades(root)*1.0/NumGrades(root);
}

int Gradetree::NodeCount()
{
	NodeCount(root);
}

int Gradetree::LeafCount()
{
	LeafCount(root);
}

int Gradetree::NonLeafCount()
{
	NonLeafCount(root);
}

bool Gradetree::SimilarTrees(Gradetree othertree)
{
	SimilarTrees(root, othertree.root);
}

int Gradetree::Height()
{
	Height(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);
}


// ------------------- 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 << " ";
    }
}

int Gradetree::SumGrades(Treenode* t)
{
    if(t != NULL)
    {
	return SumGrades(t -> left) + SumGrades(t -> right) + t->grade*t->count;
    }

    else
	return 0;
}

int Gradetree::NumGrades(Treenode* t)
{
    if(t != NULL)
    {
	return NumGrades(t -> left) + NumGrades(t -> right) + t->count;
    }

    else
	return 0;
}

int Gradetree::NodeCount(Treenode* t)
{
    if(t != NULL)
    {
        return NodeCount(t -> left) + NodeCount(t -> right) + 1;
    }
    
    else
        return 0;
}

int Gradetree::LeafCount(Treenode* t)
{
    if(t == NULL)
    	return 0;
    else if( t->left == NULL && t->right == NULL)
	return 1;
    else
	return LeafCount(t -> left) + LeafCount(t -> right);
}

int Gradetree::NonLeafCount(Treenode* t)
{
    if(t == NULL)
	return 0;
    else if(t->left == NULL && t->right == NULL)
	return 0;
    else
	return NonLeafCount(t -> left) + NonLeafCount(t -> right) + 1;
}

bool Gradetree::SimilarTrees(Treenode* t, Treenode* othertree)
{
    if (t == NULL && othertree == NULL)
	return true;   
    else if(t == NULL || othertree == NULL)
	return false;
    else if(t->right == NULL && othertree->right != NULL)
	return false;
    else if(t->right != NULL && othertree->right == NULL)
	return false;
    else if(t->left == NULL && othertree->left != NULL) 
        return false;
    else if(t->left != NULL && othertree->left == NULL)    
        return false;  
    else
	return SimilarTrees(t->right, othertree->right) && SimilarTrees(t->left, othertree->left);
}


int Gradetree::Height(Treenode* t)
{
	int n = 0, m = 0;

    if( t != NULL)
   {
	if(t->right == NULL && t->left == NULL)
	    return 1;
	else
	{
	    n = Height(t->right) + 1;
	    m = Height(t->left) + 1;
	}

	if(n >= m)
	    return n;
	else
	    return m;
    }
    else
	return 0;
}

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
	    }
	}
}