// stutree.h - header file for grade tree class

struct Treenode {               // A node in the tree
	int grade;              // grade itself
	int count;              // number of times this grade earned
	Treenode*  left;        // ptr to left subtree
	Treenode*  right;       // ptr to right subtree
};

class Gradetree {
public:
	// default constructor
		  Gradetree ();
	// copy constructor - for deep copies
		  Gradetree (const Gradetree& othergradetree);
	// destructor
		  ~Gradetree ();
	// overload assignment for deep copies
	void operator= (const Gradetree& othergradetree);
	// visit inorder and display grades
	void Inorder ();
	// visit preorder and display grades
	void Preorder ();
	// visit postorder and display grades
	void Postorder ();
	// display a sideways "picture" of the tree
	void TreePicture ();
	// add a new grade to the tree
	void Insert (int newgrade);
	// delete one occurrence of a grade from the tree (assumes grade exists)
	void Delete (int delgrade);

	// returns the sum of the grades in the tree.	
	int SumGrades();

	// count the number of nodes in the tree
	int NumGrades();	

	// The average of the grades
	float AvgGrade();

	// Number of Nodes
	int NodeCount();

	// The number of leaf nodes
	int LeafCount();
	
	// The number of non leaf nodes
	int NonLeafCount();

	// See if two tres have the same shape
	bool SimilarTrees(Gradetree othertree);

	// What is the height of the tree.
	int Height();
	
private:
	Treenode* copytree (Treenode* t);  // used by copy constructor and operator=
	void destroytree (Treenode* t);    // used by destructor

	// remainder of functions are recursive equivalents for public members
	void Inorder (Treenode* t);
	void Preorder (Treenode* t);
	void Postorder (Treenode* t);
	void Treepicture (Treenode* t, int level);
	void Insert (Treenode* &t, int newgrade);
	void Delete (Treenode* &t, int delgrade);
	
	int SumGrades(Treenode* t);
	int NumGrades(Treenode* t);
	int NodeCount(Treenode* t);
	int LeafCount(Treenode* t);
	int NonLeafCount(Treenode* t);
	bool SimilarTrees(Treenode* t, Treenode* othertree);
	int Height(Treenode* t);

	// Finally, the private data!
	Treenode* root;
};

#include "stutree.cpp"