Assignment Three

This assignment is to write a BinarySearchTree class that has methods to insert nodes into a Binary Search Tree, remove nodes from a Binary Search Tree and draw a Binary Search Tree. In addition the toString() method of the class should output a String of the nodes in inorder. The program to test your BinarySearchTree class is DrawBinarySearchTree.java. If you want you can start with the file BinarySearchTreeSkeleton.java. That file must have some private methods added, the BinaryTreeInorderItr class must be modified and the draw method must be implemented. The x and y coordinates of each node are assigned as follows:

· The diameter field is the diameter of the ovals that are draw for each node.

· The font size for drawing the name (number) of each node should be diameter also

· The x coordinate is the inorder sequence number of the node multiplied by a factor (for example 2*diameter works OK).

· The y coordinate is the depth of the node multiplied by a factor (for example 4*diameter works OK). A method to calculate the depth of a BinaryTreeNode should be used to do this.

Draw the filled ovals at the (x, y) coordinates of each node. The lines from a node to each of its children must be drawn also. Just connect the ovals to do this. A way to do this is to do an inorder iteration of the tree to calculate the (x, y) coordinates of each node and then do another iteration (possibly a preorder iteration) and draw the ovals and lines to the children. The drawing should look something like this:

This assignment is due on Thursday June 6^th OR Monday June 10^th, I will decide after Exam I. There will be a quiz at the beginning of class. Hand in a copy of the BinarySearchTree.java file and the javadoc file BinarySearchTree.html. Just have the BinarySearchTree.java file on your disk. Late assignments will not be accepted.