Your objective is to implement the main operations of a binary search tree from the lecture. To be clear, this entails creating a class for your tree nodes, then creating another class for your binary search tree. Create a class called Node (this is different from your Linked List Node class) that has three fields: a field called left for the left child link, a field called right for the right child link and a field called data for the int data being held. These fields should be private with public accessors and mutators (i.e. getLeft, getright, getData, setLeft, setright and setData). This Node class can either be a public class in its own file (i.e. Node.java) or a class without the public keyword in the same file as your BST class (described below). Create a public class called BST (and put it in a file called BST.java) that has the following: - Fields public field called root that points to the root of the tree. This must be public for the visualization to work. Any other fields you need - Public methods - A default constructor (i.e. a constructor that doesn't take any parameters). This will initialize root to null. insert (value) - Takes an int as input and inserts it into the logical place in the tree - You don't have to worry about duplicate values (see 'Edge Cases and Notes' for more information) - You may use either recursion or iteration here. search (value) - This method takes an int as input and returns true if the given value is in the tree, false otherwise. You don't have to return the location in the tree, just a boolean indicating whether the value is found. - If root is null, you should return false (since the value could not be found) - You may use either recursion or iteration here. delete (value) - This method takes an int as input, searches for it in the tree and deletes it according to the method described in the nodes. - If the value given is not found or if the root is null, this operation does nothing - Do NOT even attempt this method until everything else works! - You may use either recursion or iteration here. - Returns the smallest value in the tree. - If the root is null, return 1 - You may use either recursion or iteration here. max() - Returns the largest value in the tree. - If the root is null, return -1 - You may use either recursion or iteration here. inorder() - Traverses the tree according to the inorder traversal described in the notes. - Do not print values. Instead, construct a String, concatenating the node values as they are processed with either a comma or a space in between values. Return this String. - If the root is null, return an empty string (i.e. "" with nothing in between the quotes) - You must use recursion here. preorder() - Traverses the tree according to the preorder traversal described in the notes. - Do not print values. Instead, construct a String, concatenating the node values as they are processed with either a comma or a space in between values. Return this String. - If the root is null, return an empty string (i.e. " " with nothing in between the quotes) - You must use recursion here. postorder() - Traverses the tree according to the postorder traversal described in the notes. - Do not print values. Instead, construct a String, concatenating the node values as they are processed with either a comma or a space in between values. Return this String. - If the root is null, return an empty string (i.e. "" with nothing in between the quotes) - You must use recursion here. Main part: Make a separate public class called Main and put it into its own file. Put your entry point inside this class. Make sure to put Vis.class and Color.class in the same folder as your .java files if you plan on running your code on the command line (more on this below). Create an object of your BST class (call it whatever you like). You can now call whichever operations you want on your object. This will initialize your tree by giving it a set of nodes it will contain. When you are ready to see the visualize of your tree and test it in real-time, call Vis. test (nameofyourtreeobject); Here is an example (this code would appear inside your main function in your Main class): // instantiate our BST object BST tree = new BST(); // load it up with some initial values tree.insert (5); tree.insert (15); tree.insert (2); // are you on Windows? Vis.runonWindows = false; // set to true if running on Windows // test it out Vis.test(tree); The test function will take your BST object and show it on the screen (in beautiful ASCII art fashion). It will also display a menu wherein you can test out any operation you want. All the operations you must implement are able to be tested here
