CPSC 220 Fall 2006
HW 10: A Binary Search Tree Class

• A BST is a special case of a binary tree, so first write a generic BinaryTree class. Your class should provide the following methods:
  • BinaryTree() -- creates an empty binary tree
  • BinaryTree(T item) -- creates a binary tree with item in the root node and empty left and right subtrees.
  • BinaryTree(T item, BinaryTree left, BinaryTree right) -- creates a binary tree with item in the root node and with left and right as the left and right subtrees, respectively.
  • Iterator iteratorPreOrder() -- returns an Iterator that performs a preorder traversal of the tree's nodes.
  • Iterator iteratorInOrder() -- returns an Iterator that performs an inorder traversal of the tree's nodes.
  • Iterator iteratorPostOrder() -- returns an Iterator that performs a postorder traversal of the tree's nodes.
  Note that this is just three constructors and three iterators -- so far all you can do is make a tree and get all of its elements. As we discussed in class, it's hard to do much more without knowing something about the structure of the tree. Write a little test program to test these methods.

• Write a generic BST class that extends BinaryTree. BST should have the following interface:
  • boolean contains(T item) -- returns true if the given item is in the tree, false otherwise.
  • void insert(T item) -- inserts the given item into the tree.
  Write a program to thoroughly test these methods. Note that you can use the traversals to see if the tree is getting built correctly.

  IMPORTANT: Base your code on the the BinaryTree and BinarySearchTree classes and interfaces in L&C. Part of this assignment is understanding and extending that code.

  What to turn in

  Turn in hardcopy of your BTNode, BinaryTree and BST classes and corresponding interfaces plus the program you use to test your BST. E-mail your programs and writeups to me with cpsc220 prog1 in the subject.