In this lab you will work with a single partner to extend a binary search tree data structure and make tree traversals. Besides learning traversals, I hope that you will also become acquainted with:
· Binary search tree construction
· Sting class and String operations
· Parameter passing methods
To prepare for this lab, before the lab you must:
· Read the text chapters that describe linked binary trees, tree traversals and search trees
· Also bring the text book to the lab
· Read this lab description
· Study the LinkedBinaryTree class in DoubleBinarySearchTreeTraversal.java.
· Answer the questions in pre-lab assignment in a text file called traversals.txt and submit your answers to cs232, preLab2 where secGlab is for students participating in groups and secIlab is for students participating in individual labs.
If you are performing the lab individually you are to perform all the lab by yourself and submit the lab before the due date including the pre-lab assignments.
The instructor will divide the class into pairs, and the partners will have the whole lab time to code and debug binary tree traversals in DoubleBinarySearchTreeTraversal.java
In particular the pairs will code binary tree traversals that:
· preorder, inorder, postorder prints
· return and construct preorder, inorder, postorder strings
· reverse preorder, inorder, postorder prints
This introduction assumes that you understand a binary tree data structure, chapter 6 in Goodrich and Tamassia (especially sections 6.3.4, and 6.4). Binary search tree nodes contain elements that are comparable. Comparables are objects that can be ordered with “greater or equal to relation,” ≥, for example integers or reals. The binary search tree (BST) in this lab contains doubles. The contained elements are called keys in the text (section 9.1) and in the code for the lab, so in this lab the keys are doubles. The keys are not arbitrarily positioned in the BST rather, if node, v, stores key, k, then:
· Keys stored at nodes in the left subtree are less than or equal to k.
· Keys stored at nodes in the right subtree are greater than k.
So if a BST is constructed by inserting first 5, followed by 1, 7, 8, the tree will look like:
5
/ \
1 7
\
8
The BST is dependent on the order of insertion, so if the BST is constructed by first inserting 7, followed by 1, 5 , 8, the tree will look like:
7
/ \
1 8
\
5
A BST can be searched for a possible key value, k’. A recursive algorithm for searching:
BSTSearch(node v, key k’)
if v.key = = k’ then return v
else if v.key > k’ then
if v has left then BSTSearch(v.left, k’)
else return “key not found”
else // v.key < k’
if v has right then BSTSearch(v.right, k’)
else return “key not found”
is used by initially calling on the root. Try the algorithm on the above trees.
Inserting a key, k’, into a BST is done by performing a search on k’, but
If key value, k’, is not found then make a node with key, k’.
Else if a node is found with key value, k’, then search again in the left subtree.
A recursive algorithm for inserting:
BSTInsert(node v, key k’)
if v.key = = k’ then BSTInsert(v.left, k’)
else if v.key > k’ then
if v has left then BSTInsert(v.left, k’)
else make w = v.left with key k’
return w
else // v.key < k’
if v has right then BSTInsert(v.right, k’)
else make w = v.right with key k’
return w
is also initially called on the root.
I recommend that you read the introduction to binary search tree in the text, section 9.1. Do not worry about the term entry. Also do not worry about the “empty externals” mentioned in the text. The text prefers to use “empty external” as place holders, so that an unsuccessful search terminates at an external. During insertion the key is placed in the external, and the external is expanded so that it becomes an internal node. The lab code does not use empty externals; rather a failed search returns the nodes that terminated the search because of the null child.
Before the lab study DoubleBinarySearchTreeTraversal.java. The file contains completed classes:
InvalidPositionException
BoundaryViolationException
BoundaryViolationException
EmptyTreeException
NonEmptyTreeException
BTNode implements BTPosition
LinkedBinaryTree implements BinaryTree
DoubleComparator implements Comparator
DoubleBinarySearchTree extends
LinkedBinaryTree
and interfaces:
Position
BTPosition extends
Position
Tree
BinaryTree extends
Tree
Comparator
BinarySearchTreeTraversal
Also the file contains the incomplete class:
DoubleBinarySearchTreeTraversal extends
DoubleBinarySearchTree implements BinarySearchTreeTraversal
You and your partner are to finish DoubleBinarySearchTreeTraversal by implementing BinarySearchTreeTraversal interface specifying traversals. The main method is partially code so that it will read inputs from either a file, specified by the argument, or the keyboard and constructs the BST. You are to test your traversal implementation in the main method.
Before the lab you should study the completed classes:
BTNode implements BTPosition
LinkedBinaryTree implements BinaryTree
so that you are well acquainted with the methods. They are primarily reproduction of the code in the text. BTNode does not contain a reference to parent because recursive algorithms do not require a reference to a parent. Why is this? There is a subtlety in LinkedBinaryTree, the Position root in LinkedBinaryTree is not a BTPosition rather the element contained by root, root.element() is a BTPosition. So I have the added the method rootPosition to LinkedBinaryTree, which returns root.element().
Note that BTNode element’s is an Object class so it can not hold primitive variables directly, rather we put the double in a “wrapper class,” Double. But we can not use the comparisons, = =, <, > etc. directly on the Double class, so we use a DoubleComparator class (implementing Comparator interface) to make the comparisons. The DoubleBinarySearchTree needs DoubleComparator for searching and inserting.
Final notice all the “null checking” and “work arounds” required in DoubleBinarySearchTree’s methods treeSearch, find, and insert because the tree does not use empty externals.
During the lab you are to finish DoubleBinarySearchTreeTraversal
by implementing the tree traversals specified in the BinarySearchTreeTraversal interface.
Implement and debug the traversals in the order specified in BinarySearchTreeTraversal one at a time. The first
three traversals should be easier; they only use System.out.print(..). Be sure
to check your results; you should use more then the input files in1.txt
and in2.txt to debug your traversals.
The second three traversals, the
traversals that return Strings, are tricky. They are difficult because String
objects do not morph; rather modifying a String
returns a new String
reference. Why is this a problem for recursive
methods?
The traversals using a string are
difficult because the java string methods create a new string object, so the
recursive program lose track of the original string reference. The solution is for each recursive call to
have its own string object. The string
object must be created earlier then you might think. Create an empty string at
the top of the method.
The final three traversals perform
the traversal in reverse, meaning go right first then left. They should
be easy.
When time is called submit the completed files, DoubleBinarySearchTreeTraversal.java. It should compile and run properly.
Now submit the edited DoubleBinarySearchTreeTraversal.java to cs2321, Lab2 where secGlab is for students participating in groups and secIlab is for students participating in individual labs.
After finishing the lab you must individually complete a short survey to receive full credit for the lab, links to the surveys are found on the course home page.