Project 2 -- Binary Search Trees
Assigned: Thursday, March 8th
Due: Thursday, March 29th 
Extended to : Tuesday, April 3rd 

• test1.cc and test1.out (Updated 4/2)
• test2.cc and test2.out (Updated 4/2)
• test3.cc and test3.out (Updated 4/2)
• test4.cc and test4.out (Updated 4/2)
• test5.cc and test5.out (Updated 4/2)
• test6.cc and test6.out (Updated 4/2)
• main.cc and main.out
• main2.cc and main2.out
• main3.cc and main3.out
• main4.cc and main4.out
• main5.cc and main5.out
• expr.txt -- read in by main7.cc and test6.cc

A few helpful class files:

 templated queue class
 templated stack class
 templated string class

and some files they rely on:

 templated node class
 templated link class




I.    Implement a templated TreeNode class, as specified below.

II.   Implement a templated BinSTree class, as specified below.

III. Write a main program that reads an expression and creates the
    expression tree.  Print a vertical representation using
    PrintVTree and print the infix and postfix form of the expression.
  
    Include in this program a function:


	TreeNode<char> *BuildExpTree(char * &exp);

	that builds an expression tree from the prefix expression
	contained in the NULL-terminated string exp.  Assume the
	operands are single-letter identifiers in the range a to z
	and the operators are selected from the characters '+', '-',
	'*', and '/';





The TreeNode class
------------------

Specification:

Data members:

	private:  left and right, pointers to the children of the node
	public:  data field, templated type

Methods:

	constructor: single constructor that permits the specification
		     of a data value, or a data value and left child,
		     or a data value and left child and right child


	access methods for the pointer fields


make BinSTree a friend class so it can access the pointer fields

Tree Traversal Functions
------------------------

Also include the following as templated functions (visit is a function 
parameter).  (You may find it easiest to create these functions independent 
of the TreeNode class.  That is, in a separate file that you include when
you wish to use these functions.)

	void InOrderVisit(TreeNode *t, void visit(T& item));
	void PreOrderVisit(TreeNode *t, void visit(T& item));
	void PostOrderVisit(TreeNode *t, void visit(T& item));
	void LevelScan(TreeNode *t, void visit(T& item));
		which traverses the tree level by level and visits
		each node (also known  as breadth first scan)



The BinSTree class
-------------------

protected:


pointers to the tree root (TreeNode *root) and the
most recently accessed node (TreeNode *current), and
and an integer indicating its size (int size).


	TreeNode *GetTreeNode(T item, TreeNode *lptr = NULL,
		TreeNode *rptr = NULL);
		which that takes a data value and zero or more
		TreeNode pointers, and allocates and initializes a TreeNode.
		If sufficient memory is unavailable, the program should 
		terminate after giving an error message.

	void FreeTreeNode(TreeNode *p);
		which deallocates the corresponding nodes's memory 
		by calling the C++ function delete .  

	TreeNode *CopyTree(TreeNode *t)
		which creates a duplicate of tree t and returns
	 	a new root

	void DeleteTree (TreeNode *t)
		which dealloates the memory occupied by a tree

	TreeNode *FindNode(const T& item, TreeNode* &parent) 
		const;
		which locates a node with a data item and its parent
		in a tree (used by Find and Delete)

public:


	void PrintTree(TreeNode *t, int level)
		which creates a picture of the tree rotated
		counterclockwise 90 degrees

	void PrintVTree(TreeNode *t, int dataWidth, int screenWidth)
		which prints an upright representation of
		the tree (works for small trees) (makes use of
		the levelscan)

	void CountLeaf(TreeNode *t, int &count)
		which records the total number of leaves
	 	int the tree in count

	int Depth(TreeNode *t)
		which computes the depth of a binary tree rooted at t


	a default constructor

	a copy constructor

	a destructor

	overload the assignment operator


	int Find(T& item);
		which leaves current pointing at the node
		matching the data item -- returns true (1) if
		found and false (0) otherwise

	void Insert(const T& item);
		which adds the new data item at the "correct'
		point in the search tree

	void Delete(const T& item);
		which removes a node with a given key from the tree.
		If not found, just return.  Otherwise, remove node
		and reconfigure tree to maintain order properties.


	void ClearTree(void);
		which deallocates all the nodes in "this" tree, but 
		not the tree itself

	int TreeEmpty(void) const;
		returns 1 if empty, 0 otherwise

	int TreeSize(void) const;
		returns the number of nodes in the tree

	void Update(constT& item);
		which, if a current node is defined, compares the current 
	        node's value with the data value and if they are equal,
		performs an update to the node.  If the current node
		is undefined or the data items do not match, the new
		data value is inserted into the tree

	TreeNode *GetRoot(void) const;
		which returns a pointer to the root of the tree