Question
Hi everyone, I'm having a lot of trouble with a fairly simple problem. I have tried coding a recoding a height algorithm and need to
Hi everyone, I'm having a lot of trouble with a fairly simple problem. I have tried coding a recoding a height algorithm and need to write the code for the height command located in EnhancedBST.java under "public int height(E e)" .
I must create the height comand code in EnhancedBST.java by:
1. Search the tree for the "target node": that is, the node containing the target string, entered by the user.
2. Find the height of the subtree that has the "target node" as its root.
The first output example on page 2 shows how the program runs with an empty unwritten Height(E e) code section. The output example on the last page, page 4, shows how the output should appear when a user enters the following ; height Susan. It should function the same for height "Target node" of any target node in the tree to be used as the root whose height will be determined
Please help me solve the height method coding in EnhancedBST.java.
There are four java file classes of base code provided, which I will provide following the 4 page assignment instructions. There are 3 text files to add to the outer java program space to be used as test examples. load the file then height should return the height as an integer of the target node input by the user. EnhancedBST.java is the file where the height code needs to be written and where height method is located. I need to finish this by Sunday afternoon, the sooner the better, I will be working all day, but I really need help. Please help me.
There are four java files in the project: Lab25a.java, EnhancedBST.java, Tree.java, and Debug.java
There are three text files to be tested by the project: names.txt, cities.txt, and firstTen.txt
The four java files are as follows:
1) Lab25a.java:
/* * CIT242 Lab25a: Binary Search Tree */ import java.io.File; import java.io.FileNotFoundException; import java.io.IOException; import java.util.*;
public class Lab25a {
static String userInput; static EnhancedBST
/** * Output information regarding user commands. */ public static void outputHelpText() {
System.out.println(" COMMAND PARAMETER(S) DESCRIPTION"); System.out.println(" help Output this help text."); System.out.println(" contains string Test if tree contains string."); System.out.println(" height Output tree height (incomplete)."); System.out.println(" inorder Execute IN-order traversal."); System.out.println(" load filename Read input file into memory."); System.out.println(" postorder Execute POST-order traversal."); System.out.println(" preorder Execute PRE-order traversal."); System.out.println(" verbose Turn VERBOSE mode ON or OFF (optional feature)."); System.out.println(" q exit the program."); System.out.println(); } //_________________________________________________________________________ // Main method.
public static void main(String[] args) throws IOException { Scanner input = new Scanner(System.in); System.out.println("This program accepts the following inputs and performs the corresponding actions:"); outputHelpText(); do { System.out.print("Command: "); userInput = input.nextLine(); if (Debug.getVerboseMode()) { System.out.printf("userInput=%s ", userInput); } if (userInput.equalsIgnoreCase("help")) { outputHelpText(); } else if (userInput.toUpperCase().equals("VERBOSE")) { Debug.setOrClearVerboseMode(); if (Debug.getVerboseMode()) { System.out.println("Verbose mode is now ON."); } else { System.out.println("Verbose mode is now OFF."); } } else if (userInput.charAt(0) != 'q') { processCommand(userInput.split("[ ]")); }
} while (userInput.charAt(0) != 'q'); System.out.println("Exit program."); } // end main
static void processCommand(String[] commandArgs) { String command; if (commandArgs.length inputStrings = loadFromFile(commandArgs[1]); tree = new EnhancedBST(); for (int i = 0; i
}// end processCommand
/** * Read the contents of a text file into an ArrayList of String objects. * * @param fName = file name * @return */ static ArrayList
} // end class Lab25a
2) EnhancedBST.java:
/* Enhanced Binary Search Tree Class:
* The original BST class is provided in the Liang textbook.
*/
public class EnhancedBST
protected TreeNode
protected int size = 0;
/**
* Create a default binary tree
*/
public EnhancedBST() {
}
/**
* Create a binary tree from an array of objects
*/
public EnhancedBST(E[] objects) {
for (int i = 0; i
add(objects[i]);
}
}
@Override
/**
* Returns true if the element is in the tree
*/
public boolean search(E e) {
TreeNode
while (current != null) {
if (e.compareTo(current.element)
current = current.left;
} else if (e.compareTo(current.element) > 0) {
current = current.right;
} else // element matches current.element
{
return true; // Element is found
}
}
return false;
}
/**
* Returns height of node (or -1 if node not present)
*/
public int height(E e) {
int nodeHeight = -1;
// (lab exercise)
return nodeHeight;
} // (end height)
@Override
/**
* Insert element e into the binary tree Return true if the element is
* inserted successfully
*/
public boolean insert(E e) {
if (root == null) {
root = createNewNode(e); // Create a new root
} else {
// Locate the parent node
TreeNode
TreeNode
while (current != null) {
if (e.compareTo(current.element)
parent = current;
current = current.left;
} else if (e.compareTo(current.element) > 0) {
parent = current;
current = current.right;
} else {
return false; // Duplicate node not inserted
}
}
// Create the new node and attach it to the parent node
if (e.compareTo(parent.element)
parent.left = createNewNode(e);
} else {
parent.right = createNewNode(e);
}
}
size++;
return true; // Element inserted successfully
}
protected TreeNode
return new TreeNode(e);
}
@Override
/**
* Inorder traversal from the root
*/
public void inorder() {
System.out.printf("root=%10d ", System.identityHashCode(root));
inorder(root);
}
/**
* Inorder traversal from a subtree
*/
protected void inorder(TreeNode
if (root == null) {
return;
}
inorder(root.left);
System.out.println(root);
inorder(root.right);
}
@Override
/**
* Postorder traversal from the root
*/
public void postorder() {
System.out.printf("root=%10d ", System.identityHashCode(root));
postorder(root);
}
/**
* Postorder traversal from a subtree
*/
protected void postorder(TreeNode
if (root == null) {
return;
}
postorder(root.left);
postorder(root.right);
System.out.println(root);
}
@Override
/**
* Preorder traversal from the root
*/
public void preorder() {
System.out.printf("root=%10d ", System.identityHashCode(root));
preorder(root);
}
/**
* Preorder traversal from a subtree
*/
protected void preorder(TreeNode
if (root == null) {
return;
}
System.out.println(root);
preorder(root.left);
preorder(root.right);
}
/**
* This inner class is static, because it does not access any instance
* members defined in its outer class
*/
public static class TreeNode
protected E element;
protected TreeNode
protected TreeNode
public TreeNode(E e) {
element = e;
}
@Override
public String toString() {
String leftText, rightText;
if (this == null) {
return "null";
} else {
if (this.left == null) {
leftText = "null";
} else {
leftText = String.format("%d", System.identityHashCode(left));
}
if (this.right == null) {
rightText = "null";
} else {
rightText = String.format("%d", System.identityHashCode(right));
}
}
return String.format("node=%10d, element=%12s, left=%10s, right=%10s",
System.identityHashCode(this), element.toString(), leftText, rightText);
} //(end toString)
} // (end class TreeNode)
@Override
/**
* Get the number of nodes in the tree
*/
public int getSize() {
return size;
}
/**
* Returns the root of the tree
*/
public TreeNode
return root;
}
/**
* Returns a path from the root leading to the specified element
*/
public java.util.ArrayList
java.util.ArrayList
= new java.util.ArrayList();
TreeNode
while (current != null) {
list.add(current); // Add the node to the list
if (e.compareTo(current.element)
current = current.left;
} else if (e.compareTo(current.element) > 0) {
current = current.right;
} else {
break;
}
}
return list; // Return an array list of nodes
}
@Override
/**
* Delete an element from the binary tree. Return true if the element is
* deleted successfully Return false if the element is not in the tree
*/
public boolean delete(E e) {
// Locate the node to be deleted and also locate its parent node
TreeNode
TreeNode
while (current != null) {
if (e.compareTo(current.element)
parent = current;
current = current.left;
} else if (e.compareTo(current.element) > 0) {
parent = current;
current = current.right;
} else {
break; // Element is in the tree pointed at by current
}
}
if (current == null) {
return false; // Element is not in the tree
}
// Case 1: current has no left child
if (current.left == null) {
// Connect the parent with the right child of the current node
if (parent == null) {
root = current.right;
} else {
if (e.compareTo(parent.element)
parent.left = current.right;
} else {
parent.right = current.right;
}
}
} else {
// Case 2: The current node has a left child
// Locate the rightmost node in the left subtree of
// the current node and also its parent
TreeNode
TreeNode
while (rightMost.right != null) {
parentOfRightMost = rightMost;
rightMost = rightMost.right; // Keep going to the right
}
// Replace the element in current by the element in rightMost
current.element = rightMost.element;
// Eliminate rightmost node
if (parentOfRightMost.right == rightMost) {
parentOfRightMost.right = rightMost.left;
} else // Special case: parentOfRightMost == current
{
parentOfRightMost.left = rightMost.left;
}
}
size--;
return true; // Element deleted successfully
}
@Override
/**
* Obtain an iterator. Use inorder.
*/
public java.util.Iterator
return new InorderIterator();
}
// Inner class InorderIterator
private class InorderIterator implements java.util.Iterator
// Store the elements in a list
private java.util.ArrayList
= new java.util.ArrayList();
private int current = 0; // Point to the current element in list
public InorderIterator() {
inorder(); // Traverse binary tree and store elements in list
}
/**
* Inorder traversal from the root
*/
private void inorder() {
inorder(root);
}
/**
* Inorder traversal from a subtree
*/
private void inorder(TreeNode
if (root == null) {
return;
}
inorder(root.left);
list.add(root.element);
inorder(root.right);
}
@Override
/**
* More elements for traversing?
*/
public boolean hasNext() {
if (current
return true;
}
return false;
}
@Override
/**
* Get the current element and move to the next
*/
public E next() {
return list.get(current++);
}
@Override // Remove the element returned by the last next()
public void remove() {
if (current == 0) // next() has not been called yet
{
throw new IllegalStateException();
}
delete(list.get(--current));
list.clear(); // Clear the list
inorder(); // Rebuild the list
}
}
@Override
/**
* Remove all elements from the tree
*/
public void clear() {
root = null;
size = 0;
}
} //(end class EnhancedBST)
3) Tree.java:
import java.util.Collection;
public interface Tree
/** Return true if the element is in the tree */
public boolean search(E e);
/** Insert element e into the binary tree
* Return true if the element is inserted successfully */
public boolean insert(E e);
/** Delete the specified element from the tree
* Return true if the element is deleted successfully */
public boolean delete(E e);
/** Get the number of elements in the tree */
public int getSize();
/** Inorder traversal from the root*/
public default void inorder() {
}
/** Postorder traversal from the root */
public default void postorder() {
}
/** Preorder traversal from the root */
public default void preorder() {
}
@Override /** Return true if the tree is empty */
public default boolean isEmpty() {
return this.size() == 0;
}
@Override
public default boolean contains(Object e) {
return search((E)e);
}
@Override
public default boolean add(E e) {
return insert(e);
}
@Override
public default boolean remove(Object e) {
return delete((E)e);
}
@Override
public default int size() {
return getSize();
}
@Override
public default boolean containsAll(Collection> c) {
// Left as an exercise
return false;
}
@Override
public default boolean addAll(Collection extends E> c) {
// Left as an exercise
return false;
}
@Override
public default boolean removeAll(Collection> c) {
// Left as an exercise
return false;
}
@Override
public default boolean retainAll(Collection> c) {
// Left as an exercise
return false;
}
@Override
public default Object[] toArray() {
// Left as an exercise
return null;
}
@Override
public default
// Left as an exercise
return null;
}
}
4) Debug.java:
/* * Debug methods for "verbose" logging */
public class Debug { private static boolean verboseMode = false; // Debug aid (false by default) //________________________________________________________________________________________ /** * * @return the current value of the Boolean 'verboseMode' attribute. */ public static Boolean getVerboseMode() { return verboseMode; }
//________________________________________________________________________________________ /** * * @param value = new value for the Boolean 'verboseMode' attribute. */ public static void setVerboseMode(Boolean value) { verboseMode = value; }
//________________________________________________________________________________________ /** * Turn "verbose mode" ON (true) or OFF (false). */ public static void setOrClearVerboseMode() { if (verboseMode) { verboseMode = false; } else { verboseMode = true; } } }
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Test Text Files to load to program:
1. names.txt:
Jean
Susan
Kim
George
James
Jean
Tom
George
Jane
Denise
Jenny
Kathy
Jane
2. cities.txt:
Boston
Paris
Philadelphia
Miami
London
Paris
Chicago
3. firstTen.txt:
Washington
Adams
Jefferson
Madison
Monroe
Adams
Jackson
VanBuren
Harrison
Tyler
~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~
Please help me solve the following height method :
/** * Returns height of node (or -1 if node not present) */ public int height(E e) { int nodeHeight = -1; // (lab exercise) return nodeHeight; } // (end height)
Thank You for all those who try to help me with this assignment, it is only height but I always seem to write my code slightly off and it does not compile correctly.
Cheers,
Take Care and Thanks Again!
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started
