Project# 5 Binary Search Tree

Learning Objectives • Using Recursion in Implementing Binary Search Tree ADT Methods “To iterate is human, to recurse divine.”[L. Peter Deutsch] Definition 1. A path in a binary search tree is a sequence of unique nodes with edges between them. Definition 2. The diameter is the longest path between any two nodes in a tree. In this project, you will augment the binary search abstract data type implementation that we discussed in class. You will add four methods to its public interface along with their recursive auxiliary methods. Add signatures of public methods and their Javadoc documentation to the BSTreeAPI interface. 1. Implement a copy constructor: /** * This method creates a binary search tree with the same * structure and contents as the specified binary search tree. * @param tree a binary search tree */ public BSTree(BSTree tree) /** * An auxiliary method of the copy constructor that inserts the * data from the specified node into this tree and recursively * inserts the data of the left and right subtrees of this node * as the tree is traversed pre-order. * @param originalSubreeRoot a root of a subtree in the * original tree. */ private void copyTree(Node originalSubtreeRoot) Duncan 1 Fall 2015 Binary Search Tree ADT CSc 1351: Programming Project# 5 2. Implement this method, along with its auxiliary method, so that it deletes all leaf nodes of the tree as illustrated in figure 1. /** * Delete all leaf nodes of this tree and decrement the size of * the tree. Does nothing if the tree is empty. */ public void trim() /** * A recursive auxiliary method for the trim method. * @param subtreeRoot a node at which a subtree is rooted */ private trim(Node subtreeRoot) 9 5 10 2 1 6 7 8 4 3 A binary search tree with 10 nodes before it is trimmed, The binary search tree with 6 nodes after it was trimmed. 9 5 2 6 4 7 Figure 1: A Binary Search Tree Before and After Trimming Duncan 2 Fall 2015 Binary Search Tree ADT CSc 1351: Programming Project# 5 3. Implement this method, along with its auxiliary method, so that it generates all the paths in the tree. /** * Gives an array list containing all the root-to-leaf paths of * the tree. Each path is represented as n1-n2-n3...nk, where * each ni is a data value in the node along the path and n1 is * the root node, nk is a leaf node. * @return an array list of strings containing all the root-to-leaf * paths. */ public Array getPaths() /** * A recursive auxiliary method for the getPath method. * @param node a node along the root-to-leaf path * @param pStr a string representing a path * @param paths an array list whose elements are the * root-to-leaf paths in the tree in the format ^ n1-n2-n3...nk, where n1 is the root and nk a leaf. */ private void genPaths(Node node, String pStr, ArrayList paths) Duncan 3 Fall 2015 Binary Search Tree ADT CSc 1351: Programming Project# 5 4. Implement this method, along with its auxiliary methods, so that it determines the diameter of the tree as illustrated in figure 2. /** * Gives the diameter of this tree. * @return the diameter of this tree. */ public int diameter() /** * A recursive auxiliary method of the diameter method that * gives the diameter of the subtree rooted at the specified node. * @param node in the tree * @return the diameter of the subtree rooted at the specified node */ private int diameter(Node node) /** * Computes the maximum path of the subtree rooted at the specified node. * @param node the root of a subtree * @return the number of nodes along the longest path of the subtree * rooted at the specified node. */ private int maxPath(Node node) 9 5 10 2 1 6 7 8 6 3 7 2 1 5 4 9 4 3 8 10 A binary search tree with 10 nodes and diameter = 7 whose maximum path does not go through its root A binary search tree with 10 nodes and diameter = 7 whose maximum path goes through its root Figure 2: The Diameter of a Binary Search Tree Duncan 4 Fall 2015 Binary Search Tree ADT CSc 1351: Programming Project# 5 The BSTreeDemo Class Rewrite the BSTreeDemo class in the code in the lecture notes so that the main method performs the followings tasks: 1. Create a binary search tree, tree1, and insert these integers in it in this order: 6, 2, 1, 4, 3, 5, 7, 8, 12, 13, 10, 9 and 11. 2. Using the method that you added to the BSTree ADT public interface, generate all the paths in tree1 and print them. 3. Create another binary search tree, tree2, and insert these integers in it in the order listed below: 13, 14, 15, 7, 2, 1, 6, 4, 3, 5, 8, 10, 9, 11 and 12. 4. Using the method that you added to the BSTree ADT public interface, generate all the root-to-leaf paths in tree2 and print them. 5. Using the diameter method that you added to the public interface of the BSTree ADT, determine and print the diameters of both trees. 6. Using the copy constructor, create another tree, tree3, that is a copy of tree2. 7. Using the method that you added to the BSTree ADT public interface, generate all the root-to-leaf paths in tree3 and print them. Also, calculate its diameter and size using methods in the ADT. 8. Finally, trim tree3 and generate its root-to-leaf paths and display them. Also, calculate and display its new diameter and size using methods in the ADT. Duncan 5 Fall 2015 Binary Search Tree ADT CSc 1351: Programming Project# 5 The output should appear in the format shown below. Listing 1: Sample Run 1 The root -to - leaf paths in tree1 are : 2 [6 - 2 - 1 , 6 - 2 - 4 - 3 , 6 - 2 - 4 - 5 , 6 - 7 - 8 - 12 - 10 - 9 , ←֓ 6 - 7 - 8 - 12 - 10 - 11 , 6 - 7 - 8 - 12 - 13] 3 4 The root -to - leaf paths in tree2 are : 5 [13 - 7 - 2 - 1 , 13 - 7 - 2 - 6 - 4 - 3 , 13 - 7 - 2 - 6 - 4 - 5 , ←֓ 13 - 7 - 8 - 10 - 9 , 13 - 7 - 8 - 10 - 11 - 12 , 13 - 14 - 15] 6 7 The diameters of tree1 and tree2 are 9 and 9 , respectively. 8 9 The root -to - leaf paths in tree3 are : 10 [13 - 7 - 2 - 1 , 13 - 7 - 2 - 6 - 4 - 3 , 13 - 7 - 2 - 6 - 4 - 5 , ←֓ 13 - 7 - 8 - 10 - 9 , 13 - 7 - 8 - 10 - 11 - 12 , 13 - 14 - 15] 11 The diameter of tree3 is 9 and its size is 15. 12 13 The root -to - leaf paths in tree3 are now : 14 [13 - 7 - 2 - 6 - 4 , 13 - 7 - 8 - 10 - 11 , 13 - 14] 15 The diameter of tree3 is now 7 and its size is now 9. Additional Requirements Do not change the signature of any method or rewrite methods unless indicated in this handout. Add the signatures of the public method and their Javadoc documentation to the BSTreeAPI interface. Implement both the public and private methods in the BSTree class. Methods that are defined and documented in the BSTreeAPI interface will inherit the Javadoc when overridden in the BSTree class so they need not be documented in the class. However, you should supply Javadoc documentation for each private auxiliary method that you implement in the BSTree class. Run the Javadoc utility to make sure that it generates documentation for the BSTree class and BSTreeAPI Interface with documentation for all the new methods that you added. Also, remove all auto-generated Netbeans comments. Locate your source files, BSTree.java, BSTreeException.java, BSTreeAPI and BSTreeDemo.java, and enclose them in a zip file, YOURPAWSID proj05.zip, and submit your programming project for grading using the digital dropbox set up for this purpose.