Question

In java, create class BNode(T), which implements the interface TreeNode(T)

interface methods:

void setRight(TreeNode(T) right) - sets right side of node, where right is the node to the right of this node

void setRight(TreeNode(T) left) - sets left side of node, where left is the node to the left of this node

TreeNode getRight() - gets the right node

TreeNode getLeft() - gets the left node

T getData() - gets the data within the node

THEN, create class BT(E), which implements the Tree(E) interface, which has the following methods. Use comparator:

void clear() - clears tree of all elements

boolean contains(E e) - true if the whole tree contains given element

E first() - returns lowest tree element

E last() - returns highest tree element

boolean add(E element) - inserts element into tree

boolean empty() - checks if whole tree is empty

int size() - returns number of tree elements

E lower(E e) - returns element directly lower than given element

E higher(E e) - returns element directly higher than given element

Answer 1

/**
* General interface for trees.
*/

import java.util.*;

public interface Tree<E>
{
/**
* Store an object in the tree. The object must conform to type Comparable
* in order to be inserted in the correct location. Multiple objects representing the
* same value can be added.
*
* @param obj reference to Comparable object to add.
*/
void add(E obj);

/**
* Determine whether the tree contains an object with the same value as the
* argument.
*
* @param obj reference to Comparable object whose value will be searched for.
* @return true if the value is found.
*/
boolean contains(E obj);

/**
* Remove an object with a matching value from the tree. If multiple
* matches are possible, only the first matching object is removed.
*
* @param obj Remove an object with a matching value from the tree.
*/
void remove(E obj);

/**
* Return a new tree iterator object.
*
* @return new iterator object.
*/
Iterator<E> iterator();
}

/**
* A simple generic binary tree class to demonstrate the basic principles
* of implementing a tree data structure. This should not be taken as a production

*/

import java.util.Stack;
import java.util.Iterator;

/**
* Objects stored in a tree must conform to Comparable so that their values can
* be compared. The type parameter is constained to conform to Comparable to
* enforce this.
*/
public class BinaryTree<E extends Comparable<E>> implements Tree<E>
{
/**
* A tree is a hierarchical structure of TreeNode objects. root references
* the first node on the tree.
*/
private TreeNode<E> root;

/**
* Helper class used to implement tree nodes. As this is a private helper
* class it is acceptable to have public instance variables. Instances of
* this class are never made available to client code of the tree.
*/
private static class TreeNode<T extends Comparable<T>>
{
/**
* Data object reference.
*/
public T val;

/**
* Left and right child nodes.
*/
public TreeNode<T> left,right;

/**
* Constructor for TreeNode.
*
*@param val data object reference
*@param left left child node reference or null
*@param right right child node reference or null
*/
public TreeNode(T val, TreeNode<T> left, TreeNode<T> right)
{
this.val = val;
this.left = left;
this.right = right;
}

/**
* Insert an object into the tree.
*
* @param obj object to insert into tree.
*/
public void insert(T obj)
{
if (val.compareTo(obj) < 0)
{
if (right != null)
{
right.insert(obj) ;
}
else
{
right = new TreeNode<T>(obj,null,null) ;
}
}
else
{
if (left != null)
{
left.insert(obj) ;
}
else
{
left = new TreeNode<T>(obj,null,null) ;
}
}
}

/**
* Find an object in the tree. Objects are compared using the compareTo method, so
* must conform to type Comparable.
* Two objects are equal if they represent the same value.
*
* @param obj Object representing value to find in tree.
* @return reference to matching node or null.
*/
public TreeNode<T> find(T obj)
{
int temp = val.compareTo(obj) ;
if (temp == 0)
{
return this ;
}
if (temp < 0)
{
return (right == null) ? null : right.find(obj) ;
}
return (left == null) ? null : left.find(obj) ;
}

/**
* Remove the node referencing an object representing the same value as the argument object.
* This recursive method essentially restructures the tree as necessary and returns a
* reference to the new root. The algorithm is straightforward apart from the case
* where the node to be removed has two children. In that case the left-most leaf node
* of the right child is moved up the tree to replace the removed node. Hand work some
* examples to see how this works.
*
* @param obj Object representing value to remove from tree.
* @param t Root node of the sub-tree currently being examined (possibly null).
* @return reference to the (possibly new) root node of the sub-tree being examined or
* null if no node.
*/
private TreeNode<T> remove(T obj, TreeNode<T> t)
{
if (t == null)
{
return t;
}
if (obj.compareTo(t.val) < 0)
{
t.left = remove(obj,t.left);
}
else
if (obj.compareTo(t.val) > 0 )
{
t.right = remove(obj, t.right);
}
else
if (t.left != null && t.right != null)
{
t.val = findMin(t.right).val;
t.right = remove(t.val,t.right);
}
else
{
t = (t.left != null) ? t.left : t.right;
}
return t;
}

/**
* Helper method to find the left most leaf node in a sub-tree.
*
* @param t TreeNode to be examined.
* @return reference to left most leaf node or null.
*/
private TreeNode<T> findMin(TreeNode<T> t)
{
if(t == null)
{
return null;
}
else
if(t.left == null)
{
return t;
}
return findMin(t.left);
}
}

/**
* Construct an empty tree.
*/
public BinaryTree()
{
root = null ;
}

/**
* Store an object in the tree. The object must conform to type Comparable
* in order to be inserted in the correct location. Multiple objects representing the
* same value can be added.
*
* @param obj reference to Comparable object to add.
*/
public void add(E obj)
{
if (root == null)
{
root = new TreeNode<E>(obj,null,null) ;
}
else
{
root.insert(obj) ;
}
}

/**
* Determine whether the tree contains an object with the same value as the
* argument.
*
* @param obj reference to Comparable object whose value will be searched for.
* @return true if the value is found.
*/
public boolean contains(E obj)
{
if (root == null)
{
return false ;
}
else
{
return (root.find(obj) != null) ;
}
}

/**
* Remove an object with a matching value from the tree. If multiple
* matches are possible, only the first matching object is removed.
*
* @param obj Remove an object with a matching value from the tree.
*/
public void remove(E obj)
{
if (root != null)
{
root = root.remove(obj,root) ;
}
}

/**
* Simple pre-order iterator class. An iterator object will sequence through
* the tree contents in ascending order.
* A stack is used to keep track of where the iteration has reached in the tree.
* Note that if new items are added or removed during an iteration, there is no
* guarantee that the iteration will continue correctly.
*/
private class PreOrderIterator implements Iterator<E>
{
private Stack<TreeNode<E>> nodes = new Stack<TreeNode<E>>() ;

/**
* Construct a new iterator for the current tree object.
*/
public PreOrderIterator()
{
pushLeft(root) ;
}

/**
* Get next obnject in sequence.
*
* @return next object in sequence or null if the end of the sequence has
* been reached.
*/
public E next()
{
if (nodes.isEmpty())
{
return null ;
}
TreeNode<E> node = nodes.pop() ;
pushLeft(node.right) ;
return node.val ;
}

/**
* Determine if there is another object in the iteration sequence.
*
* @return true if another object is available in the sequence.
*/
public boolean hasNext()
{
return !nodes.isEmpty() ;
}

/**
* The remove operation is not supported by this iterator. This illustrates
* that a method required by an implemented interface can be written to not
* support the operation but should throw an exception if called.
* UnsupportedOperationException is a subclass of RuntimeException and is
* not required to be caught at runtime, so the remove method does not
* have a throws declaration. Calling methods do not have to use a try/catch
* block pair.
*
* @throws UnsupportedOperationException if method is called.
*/
public void remove()
{
throw new UnsupportedOperationException();
}

/**
* Helper method used to push node objects onto the stack to keep
* track of the iteration.
*/
private void pushLeft(TreeNode<E> node)
{
while (node != null)
{
nodes.push(node) ;
node = node.left ;
}
}
}

/**
* Return a new tree iterator object.
*
* @return new iterator object.
*/
public Iterator<E> iterator()
{
return new PreOrderIterator() ;
}
}

/*
* JUnit test class for BinaryTree class
*/

import junit.framework.* ;
import java.util.Iterator;

public class BinaryTreeTest extends TestCase
{
private Tree<Integer> empty ;
private Tree<Integer> one ;
private Tree<Integer> several ;

public void setUp()
{
empty = new BinaryTree<Integer>() ;
one = new BinaryTree<Integer>() ;
one.add(0) ;
several = new BinaryTree<Integer>() ;
several.add(5) ;
several.add(2) ;
several.add(1) ;
several.add(9) ;
several.add(8) ;
several.add(10) ;
}

public void testEmptyContainsZeroItems()
{
assertTreeEmpty(empty);
}

public void testOneContainsOneItem()
{
assertTrue("One should contain 0",one.contains(0)) ;
assertIterationValid(one,new int[]{0});
}

public void testSeveralContainsSixItems()
{
assertContains(several,new int[]{1,2,5,8,9,10}) ;
assertIterationValid(several,new int[]{1,2,5,8,9,10});
}

public void testSeveralDoesNotContain()
{
assertDoesNotContain(several,new int[]{-1,0,3,4,6,7,11}) ;
}

public void testRemoveFromEmpty()
{
empty.remove(0);
assertTreeEmpty(empty);
}

public void testRemoveFromOne()
{
one.remove(0) ;
assertTrue("0 not removed from one",!one.contains(0)) ;
assertTreeEmpty(one);
}

public void testRemoveByLeaf()
{
assertRemoveAll(several,new int[]{5,2,1,8,10,9,5});
}

public void testRemoveByRoot()
{
assertRemoveAll(several,new int[]{5,8,9,10,2,1});
}

public void testDuplicates()
{
empty.add(1) ;
empty.add(1) ;
empty.add(1) ;
assertIterationValid(empty,new int[] {1,1,1});
assertTrue("Should contain 1",empty.contains(1)) ;
empty.remove(1) ;
assertTrue("Should still contain 1",empty.contains(1)) ;
assertIterationValid(empty,new int[] {1,1});
empty.remove(1) ;
assertTrue("Should still contain 1",empty.contains(1)) ;
assertIterationValid(empty,new int[] {1});
empty.remove(1) ;
assertTrue("Should not contain 1",!empty.contains(1)) ;
assertTreeEmpty(empty);
}

private void assertTreeEmpty(Tree<Integer> tree)
{
Iterator<Integer> iterator = tree.iterator() ;
assertTrue("Tree not empty",!iterator.hasNext()) ;
}

private void assertRemoveAll(Tree<Integer> tree, int[] elements)
{
for (int i = 0 ; i < elements.length ; i++)
{
tree.remove(elements[i]);
assertFalse(elements[i] + " Still in tree after being removed",
tree.contains(elements[i])) ;
}
assertTreeEmpty(tree);
}

private void assertContains(Tree<Integer> tree, int[] elements)
{
for (int i = 0 ; i < elements.length ; i++)
{
assertTrue(elements[i] + " not in tree",
tree.contains(elements[i])) ;
}
}

private void assertDoesNotContain(Tree<Integer> tree, int[] elements)
{
for (int i = 0 ; i < elements.length ; i++)
{
assertFalse(elements[i] + " unexpectedly found in tree",
tree.contains(elements[i])) ;
}
}

private void assertIterationValid(Tree<Integer> tree, int[] elements)
{
Iterator<Integer> iterator = tree.iterator() ;
for (int i = 0 ; i < elements.length ; i++)
{
assertEquals(elements[i] + " missing from tree",
new Integer(elements[i]),iterator.next()) ;
}
assertFalse("Not reached end of iteration",iterator.hasNext());
}

public static Test suite()
{
return new TestSuite(BinaryTreeTest.class) ;
}

public static void main (String[] args)
{
junit.textui.TestRunner.run(suite()) ;
}
}