Project: "Create an implementation of a binary tree using the recursive approach introduced in the chapter. In this approach, each node is a binary tree. Thus a binary tree contains a reference to the element stored at its root as well as references to its left and right subtrees. You may also want to include a reference to its parent."
Question: In the chapter they give a binary tree implementation (code shown below) and I'm not sure what this project wants me to do differently then the implementation in the book. All I can see is to fill in a few missing details like a few methods and also adding a parent reference. I know as a final project though this isn't what it's asking.
Binary Tree Class:
`
//*******************************************************************
// BinaryTree.java Java Foundations
//
// Defines the interface to a binary tree collection.
//*******************************************************************
package javafoundations;
import java.util.Iterator;
public interface BinaryTree<T> extends Iterable<T>
{
// Returns the element stored in the root of the tree.
public T getRootElement();
// Returns the left subtree of the root.
public BinaryTree<T> getLeft();
// Returns the right subtree of the root.
public BinaryTree<T> getRight();
// Returns true if the binary tree contains an element that
// matches the specified element and false otherwise.
public boolean contains (T target);
// Returns a reference to the element in the tree matching
// the specified target.
public T find (T target);
// Returns true if the binary tree contains no elements, and
// false otherwise.
public boolean isEmpty();
// Returns the number of elements in this binary tree.
public int size();
// Returns the string representation of the binary tree.
public String toString();
// Returns a preorder traversal on the binary tree.
public Iterator<T> preorder();
// Returns an inorder traversal on the binary tree.
public Iterator<T> inorder();
// Returns a postorder traversal on the binary tree.
public Iterator<T> postorder();
// Performs a level-order traversal on the binary tree.
public Iterator<T> levelorder();
}
`
LinkedBinaryTree class:
`
//*******************************************************************
// LinkedBinaryTree.java Java Foundations
//
// Implements a binary tree using a linked representation.
//*******************************************************************
package javafoundations;
import java.util.Iterator;
import javafoundations.*;
import javafoundations.exceptions.*;
public class LinkedBinaryTree<T> implements BinaryTree<T>
{
protected BTNode<T> root;
//-----------------------------------------------------------------
// Creates an empty binary tree.
//-----------------------------------------------------------------
public LinkedBinaryTree()
{
root = null;
}
//-----------------------------------------------------------------
// Creates a binary tree with the specified element as its root.
//-----------------------------------------------------------------
public LinkedBinaryTree (T element)
{
root = new BTNode<T>(element);
}
//-----------------------------------------------------------------
// Creates a binary tree with the two specified subtrees.
//-----------------------------------------------------------------
public LinkedBinaryTree (T element, LinkedBinaryTree<T> left,
LinkedBinaryTree<T> right)
{
root = new BTNode<T>(element);
root.setLeft(left.root);
root.setRight(right.root);
}
//-----------------------------------------------------------------
// Returns the element stored in the root of the tree. Throws an
// EmptyCollectionException if the tree is empty.
//-----------------------------------------------------------------
public T getRootElement()
{
if (root == null)
throw new EmptyCollectionException
("Get root operation " + "failed. The tree is empty.");
return root.getElement();
}
//-----------------------------------------------------------------
// Returns the left subtree of the root of this tree.
//-----------------------------------------------------------------
public LinkedBinaryTree<T> getLeft()
{
if (root == null)
throw new EmptyCollectionException
("Get left operation " + "failed. The tree is empty.");
LinkedBinaryTree<T> result = new LinkedBinaryTree<T>();
result.root = root.getLeft();
return result;
}
//-----------------------------------------------------------------
// Returns the element in this binary tree that matches the
// specified target. Throws a ElementNotFoundException if the
// target is not found.
//-----------------------------------------------------------------
public T find (T target)
{
BTNode<T> node = null;
if (root != null)
node = root.find(target);
if (node == null)
throw new ElementNotFoundException
("Find operation failed. " + "No such element in tree.");
return node.getElement();
}
//-----------------------------------------------------------------
// Returns the number of elements in this binary tree.
//-----------------------------------------------------------------
public int size()
{
int result = 0;
if (root != null)
result = root.count();
return result;
}
//-----------------------------------------------------------------
// Populates and returns an iterator containing the elements in
// this binary tree using an inorder traversal.
//-----------------------------------------------------------------
public Iterator<T> inorder()
{
ArrayIterator<T> iter = new ArrayIterator<T>();
if (root != null)
root.inorder (iter);
return iter;
}
//-----------------------------------------------------------------
// Populates and returns an iterator containing the elements in
// this binary tree using a levelorder traversal.
//-----------------------------------------------------------------
public Iterator<T> levelorder()
{
LinkedQueue<BTNode<T>> queue = new LinkedQueue<BTNode<T>>();
ArrayIterator<T> iter = new ArrayIterator<T>();
if (root != null)
{
queue.enqueue(root);
while (!queue.isEmpty())
{
BTNode<T> current = queue.dequeue();
iter.add (current.getElement());
if (current.getLeft() != null)
queue.enqueue(current.getLeft());
if (current.getRight() != null)
queue.enqueue(current.getRight());
}
}
return iter;
}
//-----------------------------------------------------------------
// Satisfies the Iterable interface using an inorder traversal.
//-----------------------------------------------------------------
public Iterator<T> iterator()
{
return inorder();
}
//-----------------------------------------------------------------
// The following methods are left as programming projects.
//-----------------------------------------------------------------
// public LinkedBinaryTree<T> getRight() { }
// public boolean contains (T target) { }
// public boolean isEmpty() { }
// public String toString() { }
// public Iterator<T> preorder() { }
// public Iterator<T> postorder() { }
}
`
BTNode class:
`
//*******************************************************************
// BTNode.java Java Foundations
//
// Represents a node in a binary tree with a left and right child.
// Therefore this class also represents the root of a subtree.
//*******************************************************************
package javafoundations;
public class BTNode<T>
{
protected T element;
protected BTNode<T> left, right;
//-----------------------------------------------------------------
// Creates a new tree node with the specified data.
//-----------------------------------------------------------------
public BTNode (T element)
{
this.element = element;
left = right = null;
}
//-----------------------------------------------------------------
// Returns the element stored in this node.
//-----------------------------------------------------------------
public T getElement()
{
return element;
}
//-----------------------------------------------------------------
// Sets the element stored in this node.
//-----------------------------------------------------------------
public void setElement (T element)
{
this.element = element;
}
//-----------------------------------------------------------------
// Returns the left subtree of this node.
//-----------------------------------------------------------------
public BTNode<T> getLeft()
{
return left;
}
//-----------------------------------------------------------------
// Sets the left child of this node.
//-----------------------------------------------------------------
public void setLeft (BTNode<T> left)
{
this.left = left;
}
//-----------------------------------------------------------------
// Returns the right subtree of this node.
//-----------------------------------------------------------------
public BTNode<T> getRight()
{
return right;
}
//-----------------------------------------------------------------
// Sets the right child of this node.
//-----------------------------------------------------------------
public void setRight (BTNode<T> right)
{
this.right = right;
}
//-----------------------------------------------------------------
// Returns the element in this subtree that matches the
// specified target. Returns null if the target is not found.
//-----------------------------------------------------------------
public BTNode<T> find (T target)
{
BTNode<T> result = null;
if (element.equals(target))
result = this;
else
{
if (left != null)
result = left.find(target);
if (result == null && right != null)
result = right.find(target);
}
return result;
}
//-----------------------------------------------------------------
// Returns the number of nodes in this subtree.
//-----------------------------------------------------------------
public int count()
{
int result = 1;
if (left != null)
result += left.count();
if (right != null)
result += right.count();
return result;
}
//-----------------------------------------------------------------
// Performs an inorder traversal on this subtree, updating the
// specified iterator.
//-----------------------------------------------------------------
public void inorder (ArrayIterator<T> iter)
{
if (left != null)
left.inorder (iter);
iter.add (element);
if (right != null)
right.inorder (iter);
}
//-----------------------------------------------------------------
// The following methods are left as programming projects.
//-----------------------------------------------------------------
// public void preorder(ArrayIterator<T> iter) { }
// public void postorder(ArrayIterator<T> iter) { }
}
`
