Chapter 19, Section 6:

Complete the implementation of a DecisionTree, introduced in Chapter 19. This will require completing a number of methods from the source code for this chapter, particularly for LinkedBinaryTree. Your initial test should be the BackPainAnalyzer output from Listing 19.6 on page 746. Show test cases for at least two other correct traversals. Develop and demonstrate another decision tree that is at least as complex.?

The required source code is attached below:

ArrayList.java:

import java.util.*;

/** * ArrayList represents an array implementation of a list. The front of * the list is kept at array index 0. This class will be extended * to create a specific kind of list. */ public abstract class ArrayList implements ListADT, Iterable { private final static int DEFAULT_CAPACITY = 100; private final static int NOT_FOUND = -1;

protected int rear; protected T[] list; protected int modCount;

/** * Creates an empty list using the default capacity. */ public ArrayList() { this(DEFAULT_CAPACITY); }

/** * Creates an empty list using the specified capacity. * * @param initialCapacity the integer value of the size of the array list */ public ArrayList(int initialCapacity) { rear = 0; list = (T[])(new Object[initialCapacity]); modCount = 0; }

/** * Creates a new array to store the contents of this list with * twice the capacity of the old one. Called by descendant classes * that add elements to the list. */ protected void expandCapacity() { // To be completed as a Programming Project }

/** * Removes and returns the last element in this list. * * @return the last element in the list * @throws EmptyCollectionException if the element is not in the list */ public T removeLast() throws EmptyCollectionException { // To be completed as a Programming Project return null; // temp }

/** * Removes and returns the first element in this list. * * @return the first element in the list * @throws EmptyCollectionException if the element is not in the list */ public T removeFirst() throws EmptyCollectionException { // To be completed as a Programming Project return null; // temp }

/** * Removes and returns the specified element. * * @param element the element to be removed and returned from the list * @return the removed elememt * @throws ElementNotFoundException if the element is not in the list */ public T remove(T element) { T result; int index = find(element);

if (index == NOT_FOUND) throw new ElementNotFoundException("ArrayList");

result = list[index]; rear--;

// shift the appropriate elements for (int scan = index; scan < rear; scan++) list[scan] = list[scan+1];

list[rear] = null; modCount++;

return result; }

/** * Returns a reference to the element at the front of this list. * The element is not removed from the list. Throws an * EmptyCollectionException if the list is empty. * * @return a reference to the first element in the list * @throws EmptyCollectionException if the list is empty */ public T first() throws EmptyCollectionException { // To be completed as a Programming Project return null; // temp }

/** * Returns a reference to the element at the rear of this list. * The element is not removed from the list. Throws an * EmptyCollectionException if the list is empty. * * @return a reference to the last element of this list * @throws EmptyCollectionException if the list is empty */ public T last() throws EmptyCollectionException { // To be completed as a Programming Project return null; // temp }

/** * Returns true if this list contains the specified element. * * @param target the target element * @return true if the target is in the list, false otherwise */ public boolean contains(T target) { return (find(target) != NOT_FOUND); }

/** * Returns the array index of the specified element, or the * constant NOT_FOUND if it is not found. * * @param target the target element * @return the index of the target element, or the * NOT_FOUND constant */ private int find(T target) { int scan = 0; int result = NOT_FOUND;

if (!isEmpty()) while (result == NOT_FOUND && scan < rear) if (target.equals(list[scan])) result = scan; else scan++;

return result; }

/** * Returns true if this list is empty and false otherwise. * * @return true if the list is empty, false otherwise */ public boolean isEmpty() { // To be completed as a Programming Project return true; // temp }

/** * Returns the number of elements currently in this list. * * @return the number of elements in the list */ public int size() { // To be completed as a Programming Project return 0; // temp }

/** * Returns a string representation of this list. * * @return the string representation of the list */ public String toString() { // To be completed as a Programming Project return ""; // temp }

/** * Returns an iterator for the elements currently in this list. * * @return an iterator for the elements in the list */ public Iterator iterator() { return new ArrayListIterator(); }

/** * ArrayListIterator iterator over the elements of an ArrayList. */ private class ArrayListIterator implements Iterator { int iteratorModCount; int current;

/** * Sets up this iterator using the specified modCount. * * @param modCount the current modification count for the ArrayList */ public ArrayListIterator() { iteratorModCount = modCount; current = 0; }

/** * Returns true if this iterator has at least one more element * to deliver in the iteration. * * @return true if this iterator has at least one more element to deliver * in the iteration * @throws ConcurrentModificationException if the collection has changed * while the iterator is in use */ public boolean hasNext() throws ConcurrentModificationException { if (iteratorModCount != modCount) throw new ConcurrentModificationException();

return (current < rear); }

/** * Returns the next element in the iteration. If there are no * more elements in this iteration, a NoSuchElementException is * thrown. * * @return the next element in the iteration * @throws NoSuchElementException if an element not found exception occurs * @throws ConcurrentModificationException if the collection has changed */ public T next() throws ConcurrentModificationException { if (!hasNext()) throw new NoSuchElementException();

current++;

return list[current - 1]; }

/** * The remove operation is not supported in this collection. * * @throws UnsupportedOperationException if the remove method is called */ public void remove() throws UnsupportedOperationException { throw new UnsupportedOperationException(); }

} }

ArrayUnorderedList.java:

/** * ArrayUnorderedList represents an array implementation of an unordered list. */ public class ArrayUnorderedList extends ArrayList implements UnorderedListADT { /** * Creates an empty list using the default capacity. */ public ArrayUnorderedList() { super(); }

/** * Creates an empty list using the specified capacity. * * @param initialCapacity the initial size of the list */ public ArrayUnorderedList(int initialCapacity) { super(initialCapacity); }

/** * Adds the specified element to the front of this list. * * @param element the element to be added to the front of the list */ public void addToFront(T element) { // To be completed as a Programming Project }

/** * Adds the specified element to the rear of this list. * * @param element the element to be added to the list */ public void addToRear(T element) { // To be completed as a Programming Project }

/** * Adds the specified element after the specified target element. * Throws an ElementNotFoundException if the target is not found. * * @param element the element to be added after the target element * @param target the target that the element is to be added after */ public void addAfter(T element, T target) { if (size() == list.length) expandCapacity();

int scan = 0;

// find the insertion point while (scan < rear && !target.equals(list[scan])) scan++;

if (scan == rear) throw new ElementNotFoundException("UnorderedList");

scan++;

// shift elements up one for (int shift = rear; shift > scan; shift--) list[shift] = list[shift - 1];

// insert element list[scan] = element; rear++; modCount++; } }

BinaryTreeADT.java: import java.util.Iterator;

/** * BinaryTreeADT defines the interface to a binary tree data structure. */ public interface BinaryTreeADT { /** * Returns a reference to the root element * * @return a reference to the root */ public T getRootElement();

/** * Returns true if this binary tree is empty and false otherwise. * * @return true if this binary tree is empty, false otherwise */ public boolean isEmpty();

/** * Returns the number of elements in this binary tree. * * @return the number of elements in the tree */ public int size();

/** * Returns true if the binary tree contains an element that matches * the specified element and false otherwise. * * @param targetElement the element being sought in the tree * @return true if the tree contains the target element */ public boolean contains(T targetElement);

/** * Returns a reference to the specified element if it is found in * this binary tree. Throws an exception if the specified element * is not found. * * @param targetElement the element being sought in the tree * @return a reference to the specified element */ public T find(T targetElement);

/** * Returns the string representation of this binary tree. * * @return a string representation of the binary tree */ public String toString();

/** * Returns an iterator over the elements of this tree. * * @return an iterator over the elements of this binary tree */ public Iterator iterator();

/** * Returns an iterator that represents an inorder traversal on this binary tree. * * @return an iterator over the elements of this binary tree */ public Iterator iteratorInOrder();

/** * Returns an iterator that represents a preorder traversal on this binary tree. * * @return an iterator over the elements of this binary tree */ public Iterator iteratorPreOrder();

/** * Returns an iterator that represents a postorder traversal on this binary tree. * * @return an iterator over the elements of this binary tree */ public Iterator iteratorPostOrder();

/** * Returns an iterator that represents a levelorder traversal on the binary tree. * * @return an iterator over the elements of this binary tree */ public Iterator iteratorLevelOrder(); }

BinaryTreeNode.java: /** * BinaryTreeNode represents a node in a binary tree with a left and * right child. */ public class BinaryTreeNode { protected T element; protected BinaryTreeNode left, right;

/** * Creates a new tree node with the specified data. * * @param obj the element that will become a part of the new tree node */ public BinaryTreeNode(T obj) { element = obj; left = null; right = null; }

/** * Creates a new tree node with the specified data. * * @param obj the element that will become a part of the new tree node * @param left the tree that will be the left subtree of this node * @param right the tree that will be the right subtree of this node */ public BinaryTreeNode(T obj, LinkedBinaryTree left, LinkedBinaryTree right) { element = obj; if (left == null) this.left = null; else this.left = left.getRootNode();

if (right == null) this.right = null; else this.right = right.getRootNode(); }

/** * Returns the number of non-null children of this node. * * @return the integer number of non-null children of this node */ public int numChildren() { int children = 0;

if (left != null) children = 1 + left.numChildren();

if (right != null) children = children + 1 + right.numChildren();

return children; }

/** * Return the element at this node. * * @return the element stored at this node */ public T getElement() { return element; }

/** * Return the right child of this node. * * @return the right child of this node */ public BinaryTreeNode getRight() { return right; }

/** * Sets the right child of this node. * * @param node the right child of this node */ public void setRight(BinaryTreeNode node) { right = node; }

/** * Return the left child of this node. * * @return the left child of the node */ public BinaryTreeNode getLeft() { return left; }

/** * Sets the left child of this node. * * @param node the left child of this node */ public void setLeft(BinaryTreeNode node) { left = node; } }

LinkedBinaryTree.java:

import java.util.*;

/**

* LinkedBinaryTree implements the BinaryTreeADT interface

*/

public class LinkedBinaryTree implements BinaryTreeADT, Iterable

{

protected BinaryTreeNode root;

protected int modCount;

/**

* Creates an empty binary tree.

*/

public LinkedBinaryTree()

{

root = null;

}

/**

* Creates a binary tree with the specified element as its root.

*

* @param element the element that will become the root of the binary tree

*/

public LinkedBinaryTree(T element)

{

root = new BinaryTreeNode(element);

}

/**

* Creates a binary tree with the specified element as its root and the

* given trees as its left child and right child

*

* @param element the element that will become the root of the binary tree

* @param left the left subtree of this tree

* @param right the right subtree of this tree

*/

public LinkedBinaryTree(T element, LinkedBinaryTree left,

LinkedBinaryTree right)

{

root = new BinaryTreeNode(element);

root.setLeft(left.root);

root.setRight(right.root);

}

/**

* Returns a reference to the element at the root

*

* @return a reference to the specified target

* @throws EmptyCollectionException if the tree is empty

*/

public T getRootElement() throws EmptyCollectionException

{

// To be completed as a Programming Project

return null; // temp

}

/**

* Returns a reference to the node at the root

*

* @return a reference to the specified node

* @throws EmptyCollectionException if the tree is empty

*/

protected BinaryTreeNode getRootNode() throws EmptyCollectionException

{

// To be completed as a Programming Project

return null; // temp

}

/**

* Returns the left subtree of the root of this tree.

*

* @return a link to the left subtree fo the tree

*/

public LinkedBinaryTree getLeft()

{

// To be completed as a Programming Project

return null; // temp

}

/**

* Returns the right subtree of the root of this tree.

*

* @return a link to the right subtree of the tree

*/

public LinkedBinaryTree getRight()

{

// To be completed as a Programming Project

return null; // temp

}

/**

* Returns true if this binary tree is empty and false otherwise.

*

* @return true if this binary tree is empty, false otherwise

*/

public boolean isEmpty()

{

return (root == null);

}

/**

* Returns the integer size of this tree.

*

* @return the integer size of the tree

*/

public int size()

{

// To be completed as a Programming Project

return 0; // temp

}

/**

* Returns the height of this tree.

*

* @return the height of the tree

*/

public int getHeight()

{

// To be completed as a Programming Project

return 0; // temp

}

/**

* Returns the height of the specified node.

*

* @param node the node from which to calculate the height

* @return the height of the tree

*/

private int height(BinaryTreeNode node)

{

// To be completed as a Programming Project

return 0; // temp

}

/**

* Returns true if this tree contains an element that matches the

* specified target element and false otherwise.

*

* @param targetElement the element being sought in this tree

* @return true if the element in is this tree, false otherwise

*/

public boolean contains(T targetElement)

{

// To be completed as a Programming Project

return true; // temp

}

/**

* Returns a reference to the specified target element if it is

* found in this binary tree. Throws a ElementNotFoundException if

* the specified target element is not found in the binary tree.

*

* @param targetElement the element being sought in this tree

* @return a reference to the specified target

* @throws ElementNotFoundException if the element is not in the tree

*/

public T find(T targetElement) throws ElementNotFoundException

{

BinaryTreeNode current = findNode(targetElement, root);

if (current == null)

throw new ElementNotFoundException("LinkedBinaryTree");

return (current.getElement());

}

/**

* Returns a reference to the specified target element if it is

* found in this binary tree.

*

* @param targetElement the element being sought in this tree

* @param next the element to begin searching from

*/

private BinaryTreeNode findNode(T targetElement,

BinaryTreeNode next)

{

if (next == null)

return null;

if (next.getElement().equals(targetElement))

return next;

BinaryTreeNode temp = findNode(targetElement, next.getLeft());

if (temp == null)

temp = findNode(targetElement, next.getRight());

return temp;

}

/**

* Returns a string representation of this binary tree showing

* the nodes in an inorder fashion.

*

* @return a string representation of this binary tree

*/

public String toString()

{

// To be completed as a Programming Project

return ""; // temp

}

/**

* Returns an iterator over the elements in this tree using the

* iteratorInOrder method

*

* @return an in order iterator over this binary tree

*/

public Iterator iterator()

{

return iteratorInOrder();

}

/**

* Performs an inorder traversal on this binary tree by calling an

* overloaded, recursive inorder method that starts with

* the root.

*

* @return an in order iterator over this binary tree

*/

public Iterator iteratorInOrder()

{

ArrayUnorderedList tempList = new ArrayUnorderedList();

inOrder(root, tempList);

return new TreeIterator(tempList.iterator());

}

/**

* Performs a recursive inorder traversal.

*

* @param node the node to be used as the root for this traversal

* @param tempList the temporary list for use in this traversal

*/

protected void inOrder(BinaryTreeNode node,

ArrayUnorderedList tempList)

{

if (node != null)

{

inOrder(node.getLeft(), tempList);

tempList.addToRear(node.getElement());

inOrder(node.getRight(), tempList);

}

}

/**

* Performs an preorder traversal on this binary tree by calling

* an overloaded, recursive preorder method that starts with

* the root.

*

* @return a pre order iterator over this tree

*/

public Iterator iteratorPreOrder()

{

// To be completed as a Programming Project

return null; // temp

}

/**

* Performs a recursive preorder traversal.

*

* @param node the node to be used as the root for this traversal

* @param tempList the temporary list for use in this traversal

*/

protected void preOrder(BinaryTreeNode node,

ArrayUnorderedList tempList)

{

// To be completed as a Programming Project

}

/**

* Performs an postorder traversal on this binary tree by calling

* an overloaded, recursive postorder method that starts

* with the root.

*

* @return a post order iterator over this tree

*/

public Iterator iteratorPostOrder()

{

// To be completed as a Programming Project

return null; // temp

}

/**

* Performs a recursive postorder traversal.

*

* @param node the node to be used as the root for this traversal

* @param tempList the temporary list for use in this traversal

*/

protected void postOrder(BinaryTreeNode node,

ArrayUnorderedList tempList)

{

// To be completed as a Programming Project

}

/**

* Performs a levelorder traversal on this binary tree, using a

* templist.

*

* @return a levelorder iterator over this binary tree

*/

public Iterator iteratorLevelOrder()

{

ArrayUnorderedList> nodes =

new ArrayUnorderedList>();

ArrayUnorderedList tempList = new ArrayUnorderedList();

BinaryTreeNode current;

nodes.addToRear(root);

while (!nodes.isEmpty())

{

current = nodes.removeFirst();

if (current != null)

{

tempList.addToRear(current.getElement());

if (current.getLeft() != null)

nodes.addToRear(current.getLeft());

if (current.getRight() != null)

nodes.addToRear(current.getRight());

}

else

tempList.addToRear(null);

}

return new TreeIterator(tempList.iterator());

}

/**

* Inner class to represent an iterator over the elements of this tree

*/

private class TreeIterator implements Iterator

{

private int expectedModCount;

private Iterator iter;

/**

* Sets up this iterator using the specified iterator.

*

* @param iter the list iterator created by a tree traversal

*/

public TreeIterator(Iterator iter)

{

this.iter = iter;

expectedModCount = modCount;

}

/**

* Returns true if this iterator has at least one more element

* to deliver in the iteration.

*

* @return true if this iterator has at least one more element to deliver

* in the iteration

* @throws ConcurrentModificationException if the collection has changed

* while the iterator is in use

*/

public boolean hasNext() throws ConcurrentModificationException

{

if (!(modCount == expectedModCount))

throw new ConcurrentModificationException();

return (iter.hasNext());

}

/**

* Returns the next element in the iteration. If there are no

* more elements in this iteration, a NoSuchElementException is

* thrown.

*

* @return the next element in the iteration

* @throws NoSuchElementException if the iterator is empty

*/

public T next() throws NoSuchElementException

{

if (hasNext())

return (iter.next());

else

throw new NoSuchElementException();

}

/**

* The remove operation is not supported.

*

* @throws UnsupportedOperationException if the remove operation is called

*/

public void remove()

{

throw new UnsupportedOperationException();

}

}

}

ListADT.java: import java.util.Iterator;

/** * ListADT defines the interface to a general list collection. Specific * types of lists will extend this interface to complete the * set of necessary operations. */ public interface ListADT extends Iterable { /** * Removes and returns the first element from this list. * * @return the first element from this list */ public T removeFirst();

/** * Removes and returns the last element from this list. * * @return the last element from this list */ public T removeLast();

/** * Removes and returns the specified element from this list. * * @param element the element to be removed from the list */ public T remove(T element);

/** * Returns a reference to the first element in this list. * * @return a reference to the first element in this list */ public T first();

/** * Returns a reference to the last element in this list. * * @return a reference to the last element in this list */ public T last();

/** * Returns true if this list contains the specified target element. * * @param target the target that is being sought in the list * @return true if the list contains this element */ public boolean contains(T target);

/** * Returns true if this list contains no elements. * * @return true if this list contains no elements */ public boolean isEmpty();

/** * Returns the number of elements in this list. * * @return the integer representation of number of elements in this list */ public int size();

/** * Returns an iterator for the elements in this list. * * @return an iterator over the elements in this list */ public Iterator iterator();

/** * Returns a string representation of this list. * * @return a string representation of this list */ public String toString(); }

UnorderedListADT.java:

/** * UnorderedListADT defines the interface to an unordered list collection. * Elements are stored in any order the user desires. */ public interface UnorderedListADT extends ListADT { /** * Adds the specified element to the front of this list. * * @param element the element to be added to the front of this list */ public void addToFront(T element);

/** * Adds the specified element to the rear of this list. * * @param element the element to be added to the rear of this list */ public void addToRear(T element);

/** * Adds the specified element after the specified target. * * @param element the element to be added after the target * @param target the target is the item that the element will be added * after */ public void addAfter(T element, T target); }

NonComparableElementException?.java: /** * NonComparableElementException represents the situation in which an attempt * is made to add an element that is not comparable to an ordered collection */ public class NonComparableElementException extends RuntimeException { /** * Sets up this exception with an appropriate message. * * @param collection the exception message to deliver */ public NonComparableElementException (String collection) { super ("The " + collection + " requires Comparable elements."); }

}

EmptyCollectionException.java:

/**

* Represents the situation in which a collection is empty.

*/

public class EmptyCollectionException extends RuntimeException

{

/**

* Sets up this exception with an appropriate message.

* @param collection the name of the collection

*/

public EmptyCollectionException (String collection)

{

super ("The " + collection + " is empty.");

}

}

ElementNotFoundException.java:

/**

* ElementNotFoundException represents the situation in which a target element

* is not present in a collection

*/

public class ElementNotFoundException extends RuntimeException

{

/**

* Sets up this exception with an appropriate message.

*/

public ElementNotFoundException (String collection)

{

super ("The target element is not in this " + collection);

}

}

DecisionTree.java:

import java.util.*;

import java.io.*;

/**

* The DecisionTree class uses the LinkedBinaryTree class to implement

* a binary decision tree. Tree elements are read from a given file and

* then the decision tree can be evaluated based on user input using the

* evaluate method.

*

* @author Java Foundations

* @version 4.0

*/

public class DecisionTree

{

private LinkedBinaryTree tree;

/**

* Builds the decision tree based on the contents of the given file

*

* @param filename the name of the input file

* @throws FileNotFoundException if the input file is not found

*/

public DecisionTree(String filename) throws FileNotFoundException

{

File inputFile = new File(filename);

Scanner scan = new Scanner(inputFile);

int numberNodes = scan.nextInt();

scan.nextLine();

int root = 0, left, right;

List> nodes = new java.util.ArrayList>();

for (int i = 0; i < numberNodes; i++)

nodes.add(i, new LinkedBinaryTree(scan.nextLine()));

while (scan.hasNext())

{

root = scan.nextInt();

left = scan.nextInt();

right = scan.nextInt();

scan.nextLine();

nodes.set(root, new LinkedBinaryTree((nodes.get(root)).getRootElement(),

nodes.get(left), nodes.get(right)));

}

tree = nodes.get(root);

}

/**

* Follows the decision tree based on user responses.

*/

public void evaluate()

{

LinkedBinaryTree current = tree;

Scanner scan = new Scanner(System.in);

while (current.size() > 1)

{

System.out.println(current.getRootElement());

if (scan.nextLine().equalsIgnoreCase("N"))

current = current.getLeft();

else

current = current.getRight();

}

System.out.println(current.getRootElement());

}

}

BackPainAnalyzer.java:

import java.io.*;

/**

* BackPainAnaylyzer demonstrates the use of a binary decision tree to

* diagnose back pain.

*/

public class BackPainAnalyzer

{

/**

* Asks questions of the user to diagnose a medical problem.

*/

public static void main(String[] args) throws FileNotFoundException

{

System.out.println("So, you're having back pain.");

DecisionTree expert = new DecisionTree("input.txt");

expert.evaluate();

}

}