Exercise 1 Text Tree In this assignment you will create a tree that can store se

Question

Exercise 1 Text Tree In this assignment you will create a tree that can store sentences. Each node stores a single word and may have O to N child nodes. The root node is empty and does not store any value. The add.) method accepts a single sentence as String and breaks it up into words at each space. These words are then inserted into the tree such that they define a path starting at level 2. There is no limit to the number of levels a tree can have. In more detail: The method add(..) splits the sentence up by space into N words. These words are then inserted into the tree consisting of potentially existing nodes and newly created nodes. That is, the algorithm will match a node's value at level 1 to word 0, then match a child of the existing node to word 1, etc. until no match is found. At this point, new nodes are created as a descendant path for each following word in the sentence. a word in this case consists of any characters other than space and may include symbols

Explanation / Answer

2. The Tree interface declares the basic methods for using a tree, along with a single iterator method. The iterator does not state which iteration order is required. Remember that a tree can be traversed pre-order, post-order, in-order or level-order. This example code permits only one of these traversal orders, determined by the class implementing the tree interface.

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

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;

private static class TreeNode<T extends Comparable<T>>
{
/**
* Data object reference.
*/
public T val;

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

public TreeNode(T val, TreeNode<T> left, TreeNode<T> right)
{
this.val = val;
this.left = left;
this.right = right;
}

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) ;
}
}
}

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
*/
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.
* @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() ;
}
}

Related Questions

Navigate

• Browse (All)
• Browse E
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.