Java: The given code: import java.util.*; public class ArrayIterator<T> implemen
ID: 3833308 • Letter: J
Question
Java:
The given code:
import java.util.*;
public class ArrayIterator<T> implements Iterator<T>
{
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;
}
}
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();
}
}
import java.util.Scanner;
public class BackPainExpert
{
private LinkedBinaryTree<String> 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<String> n2, n3, n4, n5, n6, n7, n8, n9,
n10, n11, n12, n13;
n8 = new LinkedBinaryTree<String>(e8);
n9 = new LinkedBinaryTree<String>(e9);
n4 = new LinkedBinaryTree<String>(e4, n8, n9);
n10 = new LinkedBinaryTree<String>(e10);
n11 = new LinkedBinaryTree<String>(e11);
n5 = new LinkedBinaryTree<String>(e5, n10, n11);
n12 = new LinkedBinaryTree<String>(e12);
n13 = new LinkedBinaryTree<String>(e13);
n6 = new LinkedBinaryTree<String>(e6, n12, n13);
n7 = new LinkedBinaryTree<String>(e7);
n2 = new LinkedBinaryTree<String>(e2, n4, n5);
n3 = new LinkedBinaryTree<String>(e3, n6, n7);
tree = new LinkedBinaryTree<String>(e1, n2, n3);
}
//-----------------------------------------------------------------
// Follows the diagnosis tree based on user responses.
//-----------------------------------------------------------------
public void diagnose()
{
Scanner scan = new Scanner(System.in);
BinaryTree<String> 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());
}
}
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();
}
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) { }
}
public class ElementNotFoundException extends RuntimeException
{
//------------------------------------------------------------------
// Sets up this exception with an appropriate message.
//------------------------------------------------------------------
public ElementNotFoundException (String message)
{
super (message);
}
}
public class EmptyCollectionException extends RuntimeException
{
//------------------------------------------------------------------
// Sets up this exception with an appropriate message.
//------------------------------------------------------------------
public EmptyCollectionException (String message)
{
super (message);
}
}
import java.util.Iterator;
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;
}
public Iterator<T> iterator() {
return new ArrayIterator<T>();
}
}
Asked Questions:
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().
Part 2 - Decision Tree
Create a decision tree for a topic of your choice. Examples: How to choose a college major? How to select a car? How to determine what to eat for dinner? You must have at least 14 questions that you could potentially ask the user. You will need to add a few missing methods to get your program to work correctly.
My code:
Part 1 : Below are the methods in Linked Binary tree and Binary Node class
height method in LinkedBinaryTree
/**
* This method returns hieght of linked binary tree Takes node of type
* BTNode<T> as parameter
*
* @param node
* @return int
*/
public int getHeight(BTNode<T> node) {
if (node == null) {
return 0;
} else {
int leftHeight = getHeight(node.left);
int rightHeight = getHeight(node.right);
// return maximum of left and right subtrees
if (leftHeight > rightHeight) {
return (leftHeight + 1);
} else {
return (rightHeight + 1);
}
}
}
Methods in BTNode.java
// -----------------------------------------------------------------
// The following methods are left as programming projects.
// -----------------------------------------------------------------
public void preorder(ArrayIterator<T> iter) {
iter.add(element);
if (left != null)
left.preorder(iter);
if (right != null)
right.preorder(iter);
}
public void postorder(ArrayIterator<T> iter) {
if (left != null)
left.preorder(iter);
if (right != null)
right.preorder(iter);
iter.add(element);
}
Part 2: There are two classes one with methods and 2nd to run both
DesicionTree.java
package chegg.work;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
class DecisionTree {
/* ------------------------------- */
/* */
/* FIELDS */
/* */
/* ------------------------------- */
/* NESTED CLASS */
private class BinTree {
/* FIELDS */
private int nodeID;
private String questOrAns = null;
private BinTree yesBranch = null;
private BinTree noBranch = null;
/* CONSTRUCTOR */
public BinTree(int newNodeID, String newQuestAns) {
nodeID = newNodeID;
questOrAns = newQuestAns;
}
}
/* OTHER FIELDS */
static BufferedReader keyboardInput = new BufferedReader(new InputStreamReader(System.in));
BinTree rootNode = null;
/* ------------------------------------ */
/* */
/* CONSTRUCTORS */
/* */
/* ------------------------------------ */
/* Default Constructor */
public DecisionTree() {
}
/* ----------------------------------------------- */
/* */
/* TREE BUILDING METHODS */
/* */
/* ----------------------------------------------- */
/* CREATE ROOT NODE */
public void createRoot(int newNodeID, String newQuestAns) {
rootNode = new BinTree(newNodeID, newQuestAns);
System.out.println("Created root node " + newNodeID);
}
/* ADD YES NODE */
public void addYesNode(int existingNodeID, int newNodeID, String newQuestAns) {
// If no root node do nothing
if (rootNode == null) {
System.out.println("ERROR: No root node!");
return;
}
// Search tree
if (searchTreeAndAddYesNode(rootNode, existingNodeID, newNodeID, newQuestAns)) {
System.out.println("Added node " + newNodeID + " onto "yes" branch of node " + existingNodeID);
} else
System.out.println("Node " + existingNodeID + " not found");
}
/* SEARCH TREE AND ADD YES NODE */
private boolean searchTreeAndAddYesNode(BinTree currentNode, int existingNodeID, int newNodeID,
String newQuestAns) {
if (currentNode.nodeID == existingNodeID) {
// Found node
if (currentNode.yesBranch == null)
currentNode.yesBranch = new BinTree(newNodeID, newQuestAns);
else {
System.out.println("WARNING: Overwriting previous node " + "(id = " + currentNode.yesBranch.nodeID
+ ") linked to yes branch of node " + existingNodeID);
currentNode.yesBranch = new BinTree(newNodeID, newQuestAns);
}
return (true);
} else {
// Try yes branch if it exists
if (currentNode.yesBranch != null) {
if (searchTreeAndAddYesNode(currentNode.yesBranch, existingNodeID, newNodeID, newQuestAns)) {
return (true);
} else {
// Try no branch if it exists
if (currentNode.noBranch != null) {
return (searchTreeAndAddYesNode(currentNode.noBranch, existingNodeID, newNodeID, newQuestAns));
} else
return (false); // Not found here
}
}
return (false); // Not found here
}
}
/* ADD NO NODE */
public void addNoNode(int existingNodeID, int newNodeID, String newQuestAns) {
// If no root node do nothing
if (rootNode == null) {
System.out.println("ERROR: No root node!");
return;
}
// Search tree
if (searchTreeAndAddNoNode(rootNode, existingNodeID, newNodeID, newQuestAns)) {
System.out.println("Added node " + newNodeID + " onto "no" branch of node " + existingNodeID);
} else
System.out.println("Node " + existingNodeID + " not found");
}
/* SEARCH TREE AND ADD NO NODE */
private boolean searchTreeAndAddNoNode(BinTree currentNode, int existingNodeID, int newNodeID, String newQuestAns) {
if (currentNode.nodeID == existingNodeID) {
// Found node
if (currentNode.noBranch == null)
currentNode.noBranch = new BinTree(newNodeID, newQuestAns);
else {
System.out.println("WARNING: Overwriting previous node " + "(id = " + currentNode.noBranch.nodeID
+ ") linked to yes branch of node " + existingNodeID);
currentNode.noBranch = new BinTree(newNodeID, newQuestAns);
}
return (true);
} else {
// Try yes branch if it exists
if (currentNode.yesBranch != null) {
if (searchTreeAndAddNoNode(currentNode.yesBranch, existingNodeID, newNodeID, newQuestAns)) {
return (true);
} else {
// Try no branch if it exists
if (currentNode.noBranch != null) {
return (searchTreeAndAddNoNode(currentNode.noBranch, existingNodeID, newNodeID, newQuestAns));
} else
return (false); // Not found here
}
} else
return (false); // Not found here
}
}
/* --------------------------------------------- */
/* */
/* TREE QUERY METHODS */
/* */
/* --------------------------------------------- */
public void queryBinTree() throws IOException {
queryBinTree(rootNode);
}
private void queryBinTree(BinTree currentNode) throws IOException {
// Test for leaf node (answer) and missing branches
if (currentNode.yesBranch == null) {
if (currentNode.noBranch == null)
System.out.println(currentNode.questOrAns);
else
System.out.println("Error: Missing "Yes" branch at "" + currentNode.questOrAns + "" question");
return;
}
if (currentNode.noBranch == null) {
System.out.println("Error: Missing "No" branch at "" + currentNode.questOrAns + "" question");
return;
}
// Question
askQuestion(currentNode);
}
private void askQuestion(BinTree currentNode) throws IOException {
System.out.println(currentNode.questOrAns + " (enter "Yes" or "No")");
String answer = keyboardInput.readLine();
if (answer.equals("Yes"))
queryBinTree(currentNode.yesBranch);
else {
if (answer.equals("No"))
queryBinTree(currentNode.noBranch);
else {
System.out.println("ERROR: Must answer "Yes" or "No"");
askQuestion(currentNode);
}
}
}
/* ----------------------------------------------- */
/* */
/* TREE OUTPUT METHODS */
/* */
/* ----------------------------------------------- */
/* OUTPUT BIN TREE */
public void outputBinTree() {
outputBinTree("1", rootNode);
}
private void outputBinTree(String tag, BinTree currentNode) {
// Check for empty node
if (currentNode == null)
return;
// Output
System.out.println(
"[" + tag + "] nodeID = " + currentNode.nodeID + ", question/answer = " + currentNode.questOrAns);
// Go down yes branch
outputBinTree(tag + ".1", currentNode.yesBranch);
// Go down no branch
outputBinTree(tag + ".2", currentNode.noBranch);
}
}
DesicionTreeApp.java
package chegg.work;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
class DecisionTreeApp {
/* ------------------------------- */
/* */
/* FIELDS */
/* */
/* ------------------------------- */
static BufferedReader keyboardInput = new BufferedReader(new InputStreamReader(System.in));
static DecisionTree newTree;
/* --------------------------------- */
/* */
/* METHODS */
/* */
/* --------------------------------- */
/* MAIN */
public static void main(String[] args) throws IOException {
// Create instance of class DecisionTree
newTree = new DecisionTree();
// Generate tree
generateTree();
// Output tree
System.out.println(" OUTPUT DECISION TREE");
System.out.println("====================");
newTree.outputBinTree();
// Query tree
queryTree();
}
/* GENERATE TREE */
/* Add questions of your choice here */
static void generateTree() {
System.out.println(" GENERATE DECISION TREE");
System.out.println("======================");
newTree.createRoot(1, "Does animal eat meat?");
newTree.addYesNode(1, 2, "Does animal have stripes?");
newTree.addNoNode(1, 3, "Does animal have stripes?");
newTree.addYesNode(2, 4, "Animal is a Tiger");
newTree.addNoNode(2, 5, "Animal is a Leopard");
newTree.addYesNode(3, 6, "Animal is a Zebra");
newTree.addNoNode(3, 7, "Animal is a Horse");
}
/* QUERY TREE */
static void queryTree() throws IOException {
System.out.println(" QUERY DECISION TREE");
System.out.println("===================");
newTree.queryBinTree();
// Option to exit
optionToExit();
}
/* OPTION TO EXIT PROGRAM */
static void optionToExit() throws IOException {
System.out.println("Exit? (enter "Yes" or "No")");
String answer = keyboardInput.readLine();
if (answer.equals("Yes"))
return;
else {
if (answer.equals("No"))
queryTree();
else {
System.out.println("ERROR: Must answer "Yes" or "No"");
optionToExit();
}
}
}
My code is not working. Please help me organize my code and ad some code if it is necessary.
Explanation / Answer
i hope this might work ... made some changes in your code...
import java.util.*;
public class ArrayIterator<T> implements Iterator<T>
{
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;
}
}
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();
}
}
import java.util.Scanner;
public class BackPainExpert
{
private LinkedBinaryTree<String> 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<String> n2, n3, n4, n5, n6, n7, n8, n9,
n10, n11, n12, n13;
n8 = new LinkedBinaryTree<String>(e8);
n9 = new LinkedBinaryTree<String>(e9);
n4 = new LinkedBinaryTree<String>(e4, n8, n9);
n10 = new LinkedBinaryTree<String>(e10);
n11 = new LinkedBinaryTree<String>(e11);
n5 = new LinkedBinaryTree<String>(e5, n10, n11);
n12 = new LinkedBinaryTree<String>(e12);
n13 = new LinkedBinaryTree<String>(e13);
n6 = new LinkedBinaryTree<String>(e6, n12, n13);
n7 = new LinkedBinaryTree<String>(e7);
n2 = new LinkedBinaryTree<String>(e2, n4, n5);
n3 = new LinkedBinaryTree<String>(e3, n6, n7);
tree = new LinkedBinaryTree<String>(e1, n2, n3);
}
//-----------------------------------------------------------------
// Follows the diagnosis tree based on user responses.
//-----------------------------------------------------------------
public void diagnose()
{
Scanner scan = new Scanner(System.in);
BinaryTree<String> 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());
}
}
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();
}
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) { }
}
public class ElementNotFoundException extends RuntimeException
{
//------------------------------------------------------------------
// Sets up this exception with an appropriate message.
//------------------------------------------------------------------
public ElementNotFoundException (String message)
{
super (message);
}
}
public class EmptyCollectionException extends RuntimeException
{
//------------------------------------------------------------------
// Sets up this exception with an appropriate message.
//------------------------------------------------------------------
public EmptyCollectionException (String message)
{
super (message);
}
}
import java.util.Iterator;
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;
}
public Iterator<T> iterator() {
return new ArrayIterator<T>();
}
}
Asked Questions:
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().
Part 2 - Decision Tree
Create a decision tree for a topic of your choice. Examples: How to choose a college major? How to select a car? How to determine what to eat for dinner? You must have at least 14 questions that you could potentially ask the user. You will need to add a few missing methods to get your program to work correctly.
My code:
Part 1 : Below are the methods in Linked Binary tree and Binary Node class
height method in LinkedBinaryTree
/**
* This method returns hieght of linked binary tree Takes node of type
* BTNode<T> as parameter
*
* @param node
* @return int
*/
public int getHeight(BTNode<T> node) {
if (node == null) {
return 0;
} else {
int leftHeight = getHeight(node.left);
int rightHeight = getHeight(node.right);
// return maximum of left and right subtrees
if (leftHeight> rightHeight) {
return (leftHeight + 1);
} else {
return (rightHeight + 1);
}
}
}
Methods in BTNode.java
// -----------------------------------------------------------------
// The following methods are left as programming projects.
// -----------------------------------------------------------------
public void preorder(ArrayIterator<T> iter) {
iter.add(element);
if (left != null)
left.preorder(iter);
if (right != null)
right.preorder(iter);
}
public void postorder(ArrayIterator<T> iter) {
if (left != null)
left.preorder(iter);
if (right != null)
right.preorder(iter);
iter.add(element);
}
Part 2: There are two classes one with methods and 2nd to run both
DesicionTree.java
package chegg.work;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
class DecisionTree {
/* ------------------------------- */
/* */
/* FIELDS */
/* */
/* ------------------------------- */
/* NESTED CLASS */
private class BinTree {
/* FIELDS */
private int nodeID;
private String questOrAns = null;
private BinTree yesBranch = null;
private BinTree noBranch = null;
/* CONSTRUCTOR */
public BinTree(int newNodeID, String newQuestAns) {
nodeID = newNodeID;
questOrAns = newQuestAns;
}
}
/* OTHER FIELDS */
static BufferedReader keyboardInput = new BufferedReader(new InputStreamReader(System.in));
BinTree rootNode = null;
/* ------------------------------------ */
/* */
/* CONSTRUCTORS */
/* */
/* ------------------------------------ */
/* Default Constructor */
public DecisionTree() {
}
/* ----------------------------------------------- */
/* */
/* TREE BUILDING METHODS */
/* */
/* ----------------------------------------------- */
/* CREATE ROOT NODE */
public void createRoot(int newNodeID, String newQuestAns) {
rootNode = new BinTree(newNodeID, newQuestAns);
System.out.println("Created root node " + newNodeID);
}
/* ADD YES NODE */
public void addYesNode(int existingNodeID, int newNodeID, String newQuestAns) {
// If no root node do nothing
if (rootNode == null) {
System.out.println("ERROR: No root node!");
return;
}
// Search tree
if (searchTreeAndAddYesNode(rootNode, existingNodeID, newNodeID, newQuestAns)) {
System.out.println("Added node " + newNodeID + " onto "yes" branch of node " + existingNodeID);
} else
System.out.println("Node " + existingNodeID + " not found");
}
/* SEARCH TREE AND ADD YES NODE */
private boolean searchTreeAndAddYesNode(BinTree currentNode, int existingNodeID, int newNodeID,
String newQuestAns) {
if (currentNode.nodeID == existingNodeID) {
// Found node
if (currentNode.yesBranch == null)
currentNode.yesBranch = new BinTree(newNodeID, newQuestAns);
else {
System.out.println("WARNING: Overwriting previous node " + "(id = " + currentNode.yesBranch.nodeID
+ ") linked to yes branch of node " + existingNodeID);
currentNode.yesBranch = new BinTree(newNodeID, newQuestAns);
}
return (true);
} else {
// Try yes branch if it exists
if (currentNode.yesBranch != null) {
if (searchTreeAndAddYesNode(currentNode.yesBranch, existingNodeID, newNodeID, newQuestAns)) {
return (true);
} else {
// Try no branch if it exists
if (currentNode.noBranch != null) {
return (searchTreeAndAddYesNode(currentNode.noBranch, existingNodeID, newNodeID, newQuestAns));
} else
return (false); // Not found here
}
}
return (false); // Not found here
}
}
/* ADD NO NODE */
public void addNoNode(int existingNodeID, int newNodeID, String newQuestAns) {
// If no root node do nothing
if (rootNode == null) {
System.out.println("ERROR: No root node!");
return;
}
// Search tree
if (searchTreeAndAddNoNode(rootNode, existingNodeID, newNodeID, newQuestAns)) {
System.out.println("Added node " + newNodeID + " onto "no" branch of node " + existingNodeID);
} else
System.out.println("Node " + existingNodeID + " not found");
}
/* SEARCH TREE AND ADD NO NODE */
private boolean searchTreeAndAddNoNode(BinTree currentNode, int existingNodeID, int newNodeID, String newQuestAns) {
if (currentNode.nodeID == existingNodeID) {
// Found node
if (currentNode.noBranch == null)
currentNode.noBranch = new BinTree(newNodeID, newQuestAns);
else {
System.out.println("WARNING: Overwriting previous node " + "(id = " + currentNode.noBranch.nodeID
+ ") linked to yes branch of node " + existingNodeID);
currentNode.noBranch = new BinTree(newNodeID, newQuestAns);
}
return (true);
} else {
// Try yes branch if it exists
if (currentNode.yesBranch != null) {
if (searchTreeAndAddNoNode(currentNode.yesBranch, existingNodeID, newNodeID, newQuestAns)) {
return (true);
} else {
// Try no branch if it exists
if (currentNode.noBranch != null) {
return (searchTreeAndAddNoNode(currentNode.noBranch, existingNodeID, newNodeID, newQuestAns));
} else
return (false); // Not found here
}
} else
return (false); // Not found here
}
}
/* --------------------------------------------- */
/* */
/* TREE QUERY METHODS */
/* */
/* --------------------------------------------- */
public void queryBinTree() throws IOException {
queryBinTree(rootNode);
}
private void queryBinTree(BinTree currentNode) throws IOException {
// Test for leaf node (answer) and missing branches
if (currentNode.yesBranch == null) {
if (currentNode.noBranch == null)
System.out.println(currentNode.questOrAns);
else
System.out.println("Error: Missing "Yes" branch at "" + currentNode.questOrAns + "" question");
return;
}
if (currentNode.noBranch == null) {
System.out.println("Error: Missing "No" branch at "" + currentNode.questOrAns + "" question");
return;
}
// Question
askQuestion(currentNode);
}
private void askQuestion(BinTree currentNode) throws IOException {
System.out.println(currentNode.questOrAns + " (enter "Yes" or "No")");
String answer = keyboardInput.readLine();
if (answer.equals("Yes"))
queryBinTree(currentNode.yesBranch);
else {
if (answer.equals("No"))
queryBinTree(currentNode.noBranch);
else {
System.out.println("ERROR: Must answer "Yes" or "No"");
askQuestion(currentNode);
}
}
}
/* ----------------------------------------------- */
/* */
/* TREE OUTPUT METHODS */
/* */
/* ----------------------------------------------- */
/* OUTPUT BIN TREE */
public void outputBinTree() {
outputBinTree("1", rootNode);
}
private void outputBinTree(String tag, BinTree currentNode) {
// Check for empty node
if (currentNode == null)
return;
// Output
System.out.println(
"[" + tag + "] nodeID = " + currentNode.nodeID + ", question/answer = " + currentNode.questOrAns);
// Go down yes branch
outputBinTree(tag + ".1", currentNode.yesBranch);
// Go down no branch
outputBinTree(tag + ".2", currentNode.noBranch);
}
}
DesicionTreeApp.java
package chegg.work;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
class DecisionTreeApp {
/* ------------------------------- */
/* */
/* FIELDS */
/* */
/* ------------------------------- */
static BufferedReader keyboardInput = new BufferedReader(new InputStreamReader(System.in));
static DecisionTree newTree;
/* --------------------------------- */
/* */
/* METHODS */
/* */
/* --------------------------------- */
/* MAIN */
public static void main(String[] args) throws IOException {
// Create instance of class DecisionTree
newTree = new DecisionTree();
// Generate tree
generateTree();
// Output tree
System.out.println(" OUTPUT DECISION TREE");
System.out.println("====================");
newTree.outputBinTree();
// Query tree
queryTree();
}
/* GENERATE TREE */
/* Add questions of your choice here */
static void generateTree() {
System.out.println(" GENERATE DECISION TREE");
System.out.println("======================");
newTree.createRoot(1, "Does animal eat meat?");
newTree.addYesNode(1, 2, "Does animal have stripes?");
newTree.addNoNode(1, 3, "Does animal have stripes?");
newTree.addYesNode(2, 4, "Animal is a Tiger");
newTree.addNoNode(2, 5, "Animal is a Leopard");
newTree.addYesNode(3, 6, "Animal is a Zebra");
newTree.addNoNode(3, 7, "Animal is a Horse");
}
/* QUERY TREE */
static void queryTree() throws IOException {
System.out.println(" QUERY DECISION TREE");
System.out.println("===================");
newTree.queryBinTree();
// Option to exit
optionToExit();
}
/* OPTION TO EXIT PROGRAM */
static void optionToExit() throws IOException {
System.out.println("Exit? (enter "Yes" or "No")");
String answer = keyboardInput.readLine();
if (answer.equals("Yes"))
return;
else {
if (answer.equals("No"))
queryTree();
else {
System.out.println("ERROR: Must answer "Yes" or "No"");
optionToExit();
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.