// 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);
	// count the number of nodes in the tree
	int SumGrades();
	// returns the sum of the grades in the tree
	int NumGrades();
	// returns the total number of grades in the tree
	float AvgGrade();
	// uses SumGrades and Numgrades; not recursive
	int NodeCount();
	// reurns the number of nodes in the tree
	int LeafCount();
	// returns the number of leaves in the tree
	int NonLeafCount();
	// returns the number of nodes in the tree that are not leaves
	bool SimilarTrees(Gradetree othertree);
	// returns true if this tree and the other tree have the same shape
	int Height();
	// returns the height of the tree
	
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"