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 node
pthe data stored in any node in the left subtree of
pis smaller than the data stored in
p, and the data stored in any node in the right subtree of
pis 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, which returns an iterator that iterates over all elements in the tree in descending order. Hint: see the
LinkedBinaryTree. You can copy its code to this method, and change it to use your
private inorderDescending(BinaryTreeNode, which performs a recursive inorder traversal in descending order. Hint: this is nearly identical to the
node, ArrayUnorderedList tempList)
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
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.
BinarySearchTreeListby calling method
buildBalancedthat 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
buildBalancedRecthat you need to write. This is a recursive algorithm that receives 4 parameters: an array
tempArrof integers, two integer values
end, and a
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
middle = (start+end)/2). Add
bstListand then make two recursive calls: One to store the elements
bstListand the other to store the elements
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 method
iteratorInOrderDescendingon the second tree. Verify that the values stored in the tree are printed in decreasing order of value.