Binary Search Tree (BSTree) --------------------------- Description: ------------ In Node.java and BSTree.java you are given skeleton code for a binary search tree, where each node contains a string. Nodes to the left are less and to the right greater. In addition you are given a program Test.java that allows you to "test out" a binary search tree, and also draw a schema of that tree (the structure but not content). What needs to be done: ---------------------- Implement the methods in the file BSTree.java and test these - insert, to insert a string into the tree - find, to a node that contains a given string - height, deliver the height of the tree - preorder, inorder, postorder traversals of the tree - breadth first and depth first search (bfs & dfs) Sketch some of the trees (data12.txt) that you build by hand so that you are familiar with: - insertion into a binary search tree - deletion from a binary search tree - the traversals - the height of the tree - the shape of the tree Getting started: ---------------- 1. Make a directory to work in and then copy across all files in this directory (including this one). 2. Compile all the java files - javac *.java 3. Run the Test program - java Test - java Test data12.txt - java Test animals.txt - java Test heartSutra.txt - java Test data2415.txt 4. Modify BSTree.java, implementing the methods - insert, find, height, preorder, inorder, postorder, bfs, dfs What you should learn: ---------------------- You will become familiar with "non-linear" data structures and the close binding of data structures and the algorithms that work upon them. You will also sharpen up skills required for intricate programming (small and detailed) NOTE: ----- (1) You can read in data into the binary search tree on the command line Data is in the files *.txt (2) There is a "feature" in that the first time you draw a tree you need to bring the cursor back into the command line window. Patrick Prosser