Upon completion of this lab, you should be able to understand inorder traversals of a Binary Search Tree and observe how Binary Search Trees look when they are built in different ways.
A binary search tree is a binary tree with the following property: For each internal nodep the data stored in any node in the left subtree
of p is smaller than the data stored in p, and the
data stored in any node in the right subtree of p is larger than
the data stored in p. See the lecture notes on binary search trees.
Recall that an inorder traversal of a Binary Tree does the (recursive) traversal like this: traverse left subtree, visit root, traverse right subtree. For a Binary Search Tree, this results in the tree items being visited in ascending order. To visit the items in descending order, we switch the left and right traversals in the recursive algorithm.
Let us call the method that performs the
right, root, left variation of inorder traversal
iteratorInOrderDescending. You need to create class
IterableBinarySearchTreeList, where you will implement the
following two methods:
public Iterator iteratorInOrderDescending() , which
returns an iterator that iterates over all elements in the tree in
descending order. Hint: see the iteratorInOrder method
in LinkedBinaryTree. You can copy its code to this
method, and change it to use your inorderDescending method.
private inorderDescending(BinaryTreeNode node,
ArrayUnorderedList tempList) , which performs a recursive
inorder traversal in descending order. Hint: this is nearly identical
to the inorder method
in LinkedBinaryTree. Here, instead of going left to
right, we want to go right to left.
Download the files BuildBSTList.java
and iteratorLevelOrder.txt and
put the code of the iteratorLevelOrder method into your
LinkedBinaryTree.java from Lab 10 (this is the only
method you did not complete in Lab 10). Note that it requires several
classes to compile; we provide most of them here.
BuildBSTList.java is an (incomplete) program that creates
an ArrayOrderedList storing the integers from 1 to 10, and
then builds a BinarySearchTreeList by just taking the items
from the ordered list (in increasing order) and adding them one by one
to the binary search tree. What do you expect that the binary search tree
will look like?
This will be confirmed when you complete the program and run it; it
will print the content of the nodes of the tree in level-order.
You should look at the output produced by the program and draw on a
piece of paper the corresponding tree.
BinarySearchTreeList by calling
method buildBalanced that tries to build a tree where
either both subtrees of an internal node have the same height or
they differ in height by at most 1. (This tree is called a balanced tree.)
The heart of this method is
method buildBalancedRec that you need to write. This is
a recursive algorithm that receives 4 parameters: an array tempArr
of integers, two integer values start and end, and
a BinarySearchTreeList object bstList. The algorithm
works as follows:
start > end. The algorithm does not need
to do anything in this case.
start <= end. In this situation
the values in tempArr[start],..,tmpArr[end] need to be stored in bstList.
To do this, fist comput the postion of the middle element in the subarray tempArr[start],..,tempArr[end]
(middle = (start+end)/2). Add tempArr[mid] to bstList
and then make two recursive calls: One to store the elements tempArr[start],..,tempArr[mid-1]
into bstList and the other to store the elements tempArr[mid+1],..,tempArr[end]
into bstList.
Run your completed program and note the difference in the level-order representation of the first tree created (by just adding the items in order) and the second tree created (by adding the items so that the tree is as balanced as possible). Draw a picture of the two trees from the level-order representation, and show it to the TA.
The program will finally call your methoditeratorInOrderDescending on the second
tree. Verify that the values stored in the tree are printed in decreasing order of
value.
Note. In OWL instead of drawing the above 2 trees, write in level order the
nodes of each tree, like this: