CompSci-61B Lab 9a
Trees

Instructor: Prof. Robert Burns
Trees are linked list implementation with multiple links in the same direction. For example, a binary tree node could have a left_child pointer, a right_child pointer, and perhaps a parent pointer. Because we have paths that split into two or more branches, tree traversal is not as straightforward as linked list. There are three general patterns: preorder, inorder, postorder. They are variants of Depth First Search (which you will learn later) and vary in when they process the actual node. You should read the textbook's treatment on the three traversal modes for this lab. You will also implement a binary search tree for this lab. Binary search tree is a linked data structure that allows us to search for a specific value in (log n) time (Why does binary search in linked list take linear time?). However, binary search trees can be efficient if elements are inserted in certain orders (such as?). There exist huge libraries full of books describing just how to balance a binary search tree but we will ignore this issue for now and focus on just the basic functionalities.

EXERCISE 1: A Bacteria Family Tree (15 points)
Write BFT.java in package compsci61b.testing. Bacteria reproduce by splitting into different parts. Hence, every bacterium has at most one parent and every parent(just pretend it still exists) can have as many children as it is bacterially possible. In this lab, we will record the family pedigree of bacteria using a tree. Create a constructor that takes String name as argument that specifies the founder of the family. Our bacteria family tree should support the following methods:
  1. public boolean addChild(String parent_name, String child_name);
  2. public void print();

addChild should add a new bacterium called child_name to the bacterium parent_name in the tree. Duplicate names are allowed, you may choose whichever bacterium you find first to be the parent. Return false iff the bacterium parent_name does not exist in our family.

The method print should print the family of bacteria in the following format: the child of a bacterium should be printed immediately after the bacterium, pushing apart the bacterium's siblings. Also, the children must be further indented in the final display than the parent. For example (you do not need symbols, just the indentations and names),

Your bacteria family tree should contain an inner class called "Bacterium" that holds a String, the bacterium name, a pointer to the parent bacterium(null if this bacterium arose out of primordial goo), a list of pointers to the children bacteria(empty is this bacterium is not very fertile). It might be help to define private methods to help with the tree traversal. You may use any of the data structures you have already created for this lab. Remember to test your bacteria family tree thoroughly; compile, jar as lab9a.jar, and run. But do not submit yet.

EXERCISE 2: Binary Search Tree (25 points)
A binary search tree has the special property that the left sub-tree is always smaller than(or equal to) than the root node and the right sub-tree is always greater than the root node. This allows us to search for values very quickly (how quick?)
Create a new file BST.java in package compsci61b. Extend Iterable and support the < T extends Comparable<? super T>> generic typing. You should declare a private inner class TreeNode in your BST. You MUST include a parent pointer, a left child, a right child pointer, and a datum pointer for your TreeNode and adjust them accordingly in the program. You may use any data structures you have created so far. Your BST must support the following methods:
  1. public void add(T val);
  2. public boolean remove(T val);
  3. public boolean contains(T val);
  4. public String toString();
  5. public boolean isEmpty();
  6. public List< T> getRange(T lower, T upper);
  7. public Iterator iterator();
Your add method should add the entry into our BST; duplicate values are allowed. Your remove and contains method should return false iff the value does not exist in the tree. Your toString method should return a string representation of the tree in sorted order. Your getRange method should return all values in your tree between lower and upper inclusive in java.util.List; return all copies of repeating values and return the empty list if lower > upper. Your Iterator should return each element of the tree in whichever order you like. HINT: You may find a stack to be very useful for implementing the tree iterator. Or you can take advantage of the parent pointer.

Furthermore, your add, remove, and contains must run in time O(log n). You may assume that the tree is bushy. Your iterator should return the next element in O(1) time and your getRange should run in time O(log n + m) where m is the size of the list returned.

Algorithm for removal: when you remove an element, you should replace it with the largest element smaller than it or the smallest element larger than it (where would you find these?).

Be sure to test your binary search tree thoroughly, jar as lab9a.jar and submit as lab9a.