Part 1 - Tree Height

Add a method to the LinkedBinaryTree class that returns the height of a tree. Like many tree methods, this will require a fairly simple method in LinkedBinaryTree and another method in BTNode that does most of the work. First, check to see if the root is null. If it is, then the tree is obviously empty and return 0. If it is not null, return root.height().

ArrayIterator.java

//******************************************************************** // ArrayIterator.java Java Foundations // // Represents an iterator over the elements of a collection. //********************************************************************

import java.util.*;

public class ArrayIterator implements Iterator { private int DEFAULT_CAPACITY = 10; private int count; // the number of elements in the iterator private int current; // the current position in the iteration private T[] items; // the iterator's storage for elements

//----------------------------------------------------------------- // Sets up this iterator. //----------------------------------------------------------------- public ArrayIterator() { items = (T[]) (new Object[DEFAULT_CAPACITY]); count = 0; current = 0; }

//----------------------------------------------------------------- // Adds the specified item to this iterator. //----------------------------------------------------------------- public void add (T item) { if (count == items.length) expandCapacity();

items[count] = item; count++; }

//----------------------------------------------------------------- // Returns true if this iterator has at least one more element to // deliver in the iteration. //----------------------------------------------------------------- public boolean hasNext() { return (current < count); }

//----------------------------------------------------------------- // Returns the next element in the iteration. If there are no more // elements in this iteration, a NoSuchElementException is thrown. //----------------------------------------------------------------- public T next() { if (! hasNext()) throw new NoSuchElementException();

current++;

return items[current - 1]; }

//----------------------------------------------------------------- // The remove operation is not supported in this collection. //----------------------------------------------------------------- public void remove() throws UnsupportedOperationException { throw new UnsupportedOperationException(); }

//----------------------------------------------------------------- // Exapands the capacity of the storage array //----------------------------------------------------------------- private void expandCapacity() { T[] larger = (T []) (new Object[items.length*2]);

int location = 0; for (T element : items) larger[location++] = element;

items = larger; } }

BackPainAnalyzer.java

//********************************************************************

// BackPainAnalyzer.java Java Foundations // // Demonstrates the use of a binary tree. //********************************************************************

public class BackPainAnalyzer { //----------------------------------------------------------------- // Asks questions of the user to diagnose a medical problem. //----------------------------------------------------------------- public static void main (String[] args) { BackPainExpert expert = new BackPainExpert(); expert.diagnose(); } }

BackPainExpert.java

//******************************************************************** // BackPainExpert.java Java Foundations // // Represents a simple expert system for back pain diagnosis. //********************************************************************

import java.util.Scanner;

public class BackPainExpert { private LinkedBinaryTree tree;

//----------------------------------------------------------------- // Sets up the diagnosis question tree. //----------------------------------------------------------------- public BackPainExpert() { String e1 = "Did the pain occur after a blow or jolt?"; String e2 = "Do you have a fever?"; String e3 = "Do you have difficulty controlling your arms or legs?"; String e4 = "Do you have persistent morning stiffness?"; String e5 = "Do you have a sore throat or runny nose?"; String e6 = "Do you have pain or numbness in one arm or leg?"; String e7 = "Emergency! You may have damaged your spinal cord."; String e8 = "See doctor if pain persists."; String e9 = "You may have an inflammation of the joints."; String e10 = "See doctor to address symptoms."; String e11 = "You may have a respiratory infection."; String e12 = "You may have a sprain or strain."; String e13 = "You may have a muscle or nerve injury.";

LinkedBinaryTree n2, n3, n4, n5, n6, n7, n8, n9, n10, n11, n12, n13;

n8 = new LinkedBinaryTree(e8); n9 = new LinkedBinaryTree(e9); n4 = new LinkedBinaryTree(e4, n8, n9);

n10 = new LinkedBinaryTree(e10); n11 = new LinkedBinaryTree(e11); n5 = new LinkedBinaryTree(e5, n10, n11);

n12 = new LinkedBinaryTree(e12); n13 = new LinkedBinaryTree(e13); n6 = new LinkedBinaryTree(e6, n12, n13);

n7 = new LinkedBinaryTree(e7);

n2 = new LinkedBinaryTree(e2, n4, n5); n3 = new LinkedBinaryTree(e3, n6, n7);

tree = new LinkedBinaryTree(e1, n2, n3); }

//----------------------------------------------------------------- // Follows the diagnosis tree based on user responses. //----------------------------------------------------------------- public void diagnose() { Scanner scan = new Scanner(System.in); BinaryTree current = tree;

System.out.println ("So, you're having back pain."); 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()); } }

BinaryTree.java

//******************************************************************* // BinaryTree.java Java Foundations // // Defines the interface to a binary tree collection. //*******************************************************************

import java.util.Iterator;

public interface BinaryTree extends Iterable { // Returns the element stored in the root of the tree. public T getRootElement();

// Returns the left subtree of the root. public BinaryTree getLeft();

// Returns the right subtree of the root. public BinaryTree 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();

}

BTNode.java

//******************************************************************* // 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. //*******************************************************************

public class BTNode { protected T element; protected BTNode 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 getLeft() { return left; }

//----------------------------------------------------------------- // Sets the left child of this node. //----------------------------------------------------------------- public void setLeft (BTNode left) { this.left = left; }

//----------------------------------------------------------------- // Returns the right subtree of this node. //----------------------------------------------------------------- public BTNode getRight() { return right; }

//----------------------------------------------------------------- // Sets the right child of this node. //----------------------------------------------------------------- public void setRight (BTNode 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 find (T target) { BTNode 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 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 iter) { } // public void postorder (ArrayIterator iter) { } }

ElementNotFoundException.java

//******************************************************************** // ElementNotFoundException.java Java Foundations // // 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 message) { super (message); } }

EmptyCollectionException.java

//******************************************************************** // EmptyCollectionException.java Java Foundations // // Represents the situation in which a collection is empty. //********************************************************************

public class EmptyCollectionException extends RuntimeException { //------------------------------------------------------------------ // Sets up this exception with an appropriate message. //------------------------------------------------------------------ public EmptyCollectionException (String message) { super (message); } }

LinkedBinaryTree.java

//******************************************************************* // LinkedBinaryTree.java Java Foundations // // Implements a binary tree using a linked representation. //*******************************************************************

import java.util.Iterator;

public class LinkedBinaryTree implements BinaryTree { protected BTNode 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(element); }

//----------------------------------------------------------------- // Creates a binary tree with the two specified subtrees. //----------------------------------------------------------------- public LinkedBinaryTree (T element, LinkedBinaryTree left, LinkedBinaryTree right) { root = new BTNode(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 getLeft() { if (root == null) throw new EmptyCollectionException ("Get left operation " + "failed. The tree is empty.");

LinkedBinaryTree result = new LinkedBinaryTree(); 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 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; }

public Iterator iterator() { return new ArrayIterator(); }

}