Assignment №12- The Binary Search Trees

The Binary Search Trees
Unlike all the elementary data structures that we have studied, binary search trees are nonlinear. The main advantage that they have over other data structures is that their related sorting
and search algorithms can be very efficient. In today’s laboratory session, you will add additional
functionality to the Binary Search Tree abstract data type that we have been discussing in class.
Some of the methods that you will implement are analogous to others that we discussed in class.
The BSTreeAPI Interface
Make these modifications to the BSTreeAPI interface. Add the signatures and Javadoc for two
additional traversal methods. See a description of how these methods should work from the
lecture notes.
void postorderTraverse(Function func);
void preorderTraverse(Function func);
The Generic BSTree Class
Add the following methods to the BSTree class from the lecture notes:
1. public void postorderTraverse(Function func): traverses the binary search tree in postorder and apply the specify function to the data in each node visited.
2. public void preorderTraverse(Function func): traverses the binary search tree in preorder and apply the specify function to the data in each node visited.
3. public long countEdges(): gives the number of edges in the tree.
4. public E max() throws BSTreeException: returns the left-most (smallest) value in a
binary search tree or throws an exception if the tree is empty.
5. public E min() throws BSTreeException: returns the right-most (largest) value in a binary search tree or throws an exception if the tree is empty.
6. public ArrayList< E sort(): returns an array list containing the elements of the tree
in ascending order or an empty array list if the tree is empty. (Hint: Perform an inoder
traversal of the tree and append the data to an array list.)
Assignment № 10 Page 1
7. Add methods to test whether two binary search trees are equivalent:
(a) public boolean equals(BSTree tree): wrapper for a recursive auxiliary method that
determines whether two binary search trees are equivalent.
(b) private boolean equals(Node subtree1, Node subtree2): an auxiliary recursive
method that determines whether two subtrees are equivalent.
Hint: If two tree have different sizes then they are not equal. If they have the same size,
then recursively determine whether the trees are equivalent. To recursively determine
whether two sub-trees are equivalent:
(a) If the root nodes of both sub-trees are null, then they are equivalent.
(b) If exact one root node of the sub-trees is null, then they are not equivalent.
(c) Otherwise, determine whether the data in the first subtree root node is equivalent to
the data in the second subtree root node and, recursively, whether the left sub-trees
of both sub-trees are equal and their right sub-trees are also equal.
The BSTreeDemo Class
Rewrite the BSTreeDemo program to do the following:
1. Create a binary search tree containing strings and insert the names of the following cities
into the tree in this order: Krakow, Auckland, Rome, Sydney, Barcelona, Siem Reap,
Vancouver, Vienna, Charleston and Cape Town.
2. Traverse the tree pre-order and display the names of the cities using the preoderTraverse
method.
3. Delete Charleston from the tree.
4. Traverse the tree post-order and display the names of the cities using the postoderTraverse
method.
5. Display the names of the first and last cities when those names are displayed in alphabetical order (Hint: Use the max and min methods.)
6. Call the sort method on the tree and print the array list it returns.
7. Create a second binary search tree containing strings and insert the names of the following
cities into the tree in this order: Krakow, Rome, Sydney, Auckland, Vancouver, Vienna,
Barcelona, Siem Reap, and Cape Town.
8. Traverse the second tree in-order and display the names of the cities using the inoderTraverse method.
9. Re-insert Charleston into the second tree.
Assignment № 10 Page 2
10. Use the equals method to determine whether or not the first and second binary search
trees are equal and display a message indicating so.
11. Finally, traverse both trees pre-order and display the names of the cities using the preorderTraverse method.
For each output printed, add appropriate headers or labels indicating what is being displayed.
Additional Requirements
Test your program to ensure that it works correctly. Provide any missing Javadoc comments.
Run the Javadoc utility to make sure that it generates documentation for the BStree class and the
BSTreeAPI interface. Locate the source files that you wrote and/or modified, BSTreeAPI.java,
BSTree.java and BSTreeDemo.java and enclose them in a zip file, YOURPAWSID_lab12.zip,
and submit your lab assignment for grading using the digital dropbox set up for this purpose.
The output should appear in the format shown below with with one city name printed per line
during the traversals.
Listing 1: Sample Run 1
1 Pre-Order Traversal After Insertions:
2 :::
3
4 Post-Order Traversal After Deletion of Charleston from the First Tree:
5 :::
6
7 Alphabetically, the first and last cities are ... and ....
8
9 The cities in alphabetical order are ....
10
11 In-Order Traversal After the Construction of the Second Tree:
12 :::
13
14 The first and second trees are .....
15
16 Pre-Order Traversal of the First Tree:
17 :::
18
19 Pre-Order Traversal of the Second Tree:
20 :::
Assignment № 10 Page 3