Provided Files:

BinaryTreeADT. BinarySearchTreeADT

Objectives:

Creating an array-based implementation of a binary search tree using computational strategy. Using an iterator Using recursion

Lab Assignment:

In this lab you are going to implement BinaryTreeADT and BinarySearchTreeADT interfaces using a computational array strategy in order to create a BinarySearchTree.

1. Don't use an instance variable count to keep track of the number of nodes in the tree.

In computational strategy, for any element stored in position n of the array, that element's left child will be stored in position ( (2 * n ) + 1) and that elements right child will be stored in position ( (2 * n) + 2). 2. Write two constructors. One that creates an empty tree and one that creates a tree with a specified element (received by parameter) as its root.

3. Method toString should return a string representation of the tree in the level order.

4. Method iterator should return an inorder iterator.

5. Create an EmptyTreeException class. Throw this exception in getRootElement, findMin, findMax and find methods when the tree is empty.

6. Your textbook uses ArrayUnorderedList object to implement traversal methods. You can use ArrayList class from java.util package (this way you don't have to write ArrayUnorderedList class). To add element the the ArrayList use method add instead of addToRear.

7. Write an application that creates an ArrayBinarySearchTree object as displayed in Fig 1. In the applications call methods from the ArrayBinarySearchTree class to test the methods. You don't have to use GUI in your application.

4

2 .............6

.....1.. .3 ... . ...5 . .7

Fig 1.

////BinaryTreeADT.java///

package Collections139; import java.util.Iterator;

public interface BinaryTreeADT { /** * Returns a reference to the root element * * @return a reference to the root * @throws EmptyCollectionException if the tree is empty */ public T getRootElement ();

/** * Returns true if this binary tree is empty and false otherwise. * * @return true if this binary tree is empty */ public boolean isEmpty();

/** * Returns the number of elements in this binary tree. * * @return the integer number of elements in this tree */ public int size();

/** * Returns true if the binary tree contains an element that matches * the specified element and false otherwise. * * @param targetElement the element being sought in the tree * @return true if the tree contains the target element */ public boolean contains (T targetElement);

/** * Returns a reference to the specified element if it is found in * this binary tree. Throws an exception if the specified element * is not found. * * @param targetElement the element being sought in the tree * @return a reference to the specified element * @throws ElementNotFoundException if an element is not found */ public T find (T targetElement);

/** * Returns the string representation of the binary tree. * * @return a string representation of the binary tree */ public String toString();

/** * Performs an inorder traversal on this binary tree by calling an * overloaded, recursive inorder method that starts with the root. * * @return an iterator over the elements of this binary tree */ public Iterator iteratorInOrder();

/** * Performs a preorder traversal on this binary tree by calling an * overloaded, recursive preorder method that starts with the root. * * @return an iterator over the elements of this binary tree */ public Iterator iteratorPreOrder();

/** * Performs a postorder traversal on this binary tree by calling an * overloaded, recursive postorder method that starts with the root. * * @return an iterator over the elements of this binary tree */ public Iterator iteratorPostOrder();

/** * Performs a levelorder traversal on the binary tree, using a queue. * * @return an iterator over the elements of this binary tree */ public Iterator iteratorLevelOrder(); }

//BinarySearchTreeADT.java////

package Collections139;

/** * BinarySearchTreeADT defines the interface to a binary search tree. * @param */ public interface BinarySearchTreeADT extends BinaryTreeADT {

/** * Adds the specified element to the proper location in this tree. * * @param element the element to be added to this tree */ public void add(T element);

/** * Returns the smallest element in this tree without removing it. * * @return the smallest element in the tree */ public T findMin();

/** * Returns the largest element in this tree without removing it. * * @return the largest element in the tree */ public T findMax(); }

// BinaryTreeCreator.java//

import java.util.Iterator; import Collections139.*; import exceptions.*;

public class BinaryTreeCreator {

public static void main(String[] args) { ArrayBinarySearchTree tree = new ArrayBinarySearchTree();

tree.add(4); tree.add(2); tree.add(6); tree.add(1); tree.add(3); tree.add(5); tree.add(7);

System.out.println(tree.size() + "size" + " LevelOrder "); Iterator treeIterator = tree.iteratorLevelOrder(); while (treeIterator.hasNext()) { System.out.println("Element = " + treeIterator.next()); } System.out.println(" InOrder "); treeIterator = tree.iteratorInOrder();

while (treeIterator.hasNext()) { System.out.println("Element = " + treeIterator.next()); } System.out.println(" PreOrder "); treeIterator = tree.iteratorPreOrder();

while (treeIterator.hasNext()) { System.out.println("Element = " + treeIterator.next()); } System.out.println(" PostOrder "); treeIterator = tree.iteratorPostOrder();

while (treeIterator.hasNext()) { System.out.println("Element = " + treeIterator.next()); } System.out.println(tree.toString());

System.out.println("Is 5 in the tree?" + tree.contains(5)); System.out.println("Is 20 in the tree?" + tree.contains(20)); try { System.out.println(tree.find(15));

} catch (ElementNotFoundException e) { System.out.println(e.getMessage()); } System.out.println("size" + tree.size()); System.out.println("smallest" + tree.findMin()); System.out.println("max" + tree.findMax());

} }