Question: Programing Assignment The main classes to be worked on/modified in this assignment are BinaryTree and BinaryNode, and BinarySearchTree. Modifying BinaryTree with Parent References Step 1.
Programing Assignment
The main classes to be worked on/modified in this assignment are BinaryTree and BinaryNode, and BinarySearchTree.
Modifying BinaryTree with Parent References
Step 1.
In the class BinaryNode, add a private variable that will hold the parent reference.
Step 2.
Add a new constructor that has four arguments: data, left, right, and parent.
Step 3.
Modify the constructor that takes three arguments to use the new constructor.
Step 4.
write and fully implement three new methods in BinaryNode:
public BinaryNode
Checkpoint: Compile BinarySearchTree, BinaryNode and BinaryTree.All tests in TestBinaryTree and TestBST should pass.
Step 5. Make a duplicate of the method copy() in BinaryNode and add an argument BinaryNode
Step 6. In the duplicate, set the parent of newRoot to be p.
Step 7. In the original, set the parent of of newRoot to be null. (We will assume that if the originalversion of the copy method is being called, it is the top of the tree being copied and the parent should be null.The second version of copy will be used for all other nodes in the copy.)
Step 8. In both the original and the duplicate, change the two recursive calls to copy() so that they pass newRoot as the parameter.
Checkpoint: BinaryNode should compile successfully.
Checkpoint: Compile BinaryNode and BinaryTree.All tests in TestBinaryTree and TestBasicAccess should still pass.
The modification of BinaryNode is finished.The next goal is to modify BinaryTree appropriately.Any time a new binary tree is created, parent references for children may need to be set.
Step 9. Anywhere in BinaryTree that a left or right child is set, set a parent reference in an appropriate fashion.
Checkpoint: Compile BinaryNode and BinaryTree.All tests in TestBinaryTree and TestBasicAccess should still pass.
Threading the BinaryTree
Step 10. In the class BinaryNode, add a private variable that will hold the thread reference.
Step 11. Add a new constructor that has five arguments: data, left, right, parent, and thread.
Step 12. Modify the constructor that takes four arguments to use the new constructor.
Step 13. write and fully implement three new methods in BinaryNode:
public BinaryNode
Checkpoint: Compile BinarySearchTree, BinaryNode, and BinaryTree.All tests in TestBinaryTree and TestBST should still pass.
Step 14. write and complete the method linkSubtreeThreadOut() in BinaryNode.Refer to the preassignment exercises.
Step 15. In both of the copy() methods in BinaryNode make a call to linkSubtreeThreadOut to thread the left subtree to the root.
Step 16. write and complete the method getLeftmostInSubtree() in BinaryNode.Refer to the preassignment exercises.
Step 17. In the both copy() methods in BinaryNode add code that will thread the root to the leftmost node in the right subtree.
Checkpoint: Compile BinarySearchTree, BinaryNode, and BinaryTree.All tests in TestBinaryTree and TestBST should still pass.
The modification of BinaryNode is finished.The next goal is to modify BinaryTree appropriately.Any time a new binary tree is created, threads for children may need to be set.
Step 18. Anywhere in BinaryTree that a left child is set, set a thread reference for the subtree in an appropriate fashion.
Step 19. Similarly, anywhere in BinaryTree that a right child is set, set a thread reference from the root to the leftmost node in the subtree in an appropriate fashion.
Checkpoint: Compile BinarySearchTree, BinaryNode, and BinaryTree.All tests in TestBinaryTree and TestBST should still pass.
It is now time to see if the threads work.The in-order iterator will be changed to use the threads.
Implementing an In-Order Iterator with Threads
Step 20. In the class BinaryTree,write a copy of the private inner class InorderIterator.Comment out the original.
Step 21. Remove the variable nodeStack.Now that threading is available, the stack will not be needed.
Step 22. Refer to the pre-assignment exercises and write a private method in InorderIterator that will move the current node to the first node to be printed in an in-order traversal.
Step 23. Call the new method in the constructor just after setting the currentNode to the root.(Make sure the root is not null before doing so though.)
Step 24. Complete the hasNext() method.
Step 25. Complete the next() method.It should be much simpler now.It just needs to remember the value to return and then move the current reference. Don't forget to throw NoSuchElementException when there are no more elements to be iterated over.
Checkpoint: Compile BinaryNode and BinaryTree.All tests in TestBinaryTree should still pass.
This is the first real test of the threading.To debug the code, it may be helpful to print whenever a node is created (along with the data) and to print whenever a thread is set.When finished, comment out the print statements.They may be useful again in the next section.
Now it is time to make sure that BinarySearchTree respects parent references and threads.
Threading the BinarySearchTree
Step 26. Anywhere in the add() method of BinarySearchTree that a left or right child is set, parent references and threads must be adjusted.Refer to the pre-assignment exercises.
Checkpoint: Compile BinarySearchTree.All the tests except for remove should pass.
Step 27. Anywhere in the removeNode() method of BinarySearchTree that a left or right child is set or the root is changed, parent references and threads must be adjusted.Refer to the pre-assignment exercises.(Of all the methods that collaberate to perform the remove, the only method that affects the structure of the tree is removeNode, so it is the only one where references might need to change.)
Checkpoint: Compile BinarySearchTree.All the tests in TestBST should pass.
Getting Identifiers from a Java Program
The application Identifiers exists but needs to be completed. The purpose of this application is to identify possible java identifiers in a java code input. For the sake of this assignment, we consider an identifier any string that does not contain:
-spaces
-#, @, !, {, or }
and is followed by the following symbols:
+ (plus), - (minus),*(multiply), / (devided) and ; (semicolumn)
Of course, these are not all the rules, but we will limit the complexity of this application to that!!!
Step 28. Copy Small.java and X.java to the default directory where you will be running your code. These files will ve used as input to the application Identifiers.
Checkpoint: The application should run. Enter X.java for the file name. The program will open the file for reading then quit.
Step 29. In the method getPossibleIds() in Identifierswrite a loop to read lines from the file.
Step 30. In the loop, read a line usingScanner and then use the line to write a StringTokenizer.
Step 31. write another loop that uses the StringTokenizer to get tokens (strings) and place them in the binary search tree.(For the delimeters string include any character that would mark the end of a token.For example, in the code x+=y*eff;each of the symbols +, * and ; mark the end of an identifier. )
Step 32. In the main, use an in-order iterator to print out the values in the binary search tree.
Final checkpoint: The application should run. Enter X.java for the file name.The list of identifiers should bea b c d e ef g.
Run the application again. Enter Small.java for the file name.This is a very short working java application.The list of possible identifiers should be in alphabetical order and should correctly include the identifiers in the program.
Test the application on other Java files.
Items to submit
Submit the whole Eclipse project, containing all the classes as java files listed in the beginning of the document, as well as the input files (including the ones you might have created to test). Do not forget to comment your code and submit a README, if you need to document something other than what is explained in this document. Include also any necessary additional files so that the code compile and runs properly.
*****************************************************************************
Given File with this homework:
package TreePackage;
/**
* An implementation of the ADT Binary Node.
*
*/
class BinaryNode
private T data;
private BinaryNode
private BinaryNode
// ADD PRIVATE VARIABLEs TO HOLD A PRARENT REFERENCE
// AND A THREAD REFERENCE HERE
public BinaryNode() {
this(null); // Call next constructor
} // end default constructor
public BinaryNode(T dataPortion) {
this(dataPortion, null, null); // Call next constructor
} // end constructor
public BinaryNode(T dataPortion, BinaryNode
BinaryNode
// MODIFY THIS CONSTRUCTOR
data = dataPortion;
leftChild = newLeftChild;
rightChild = newRightChild;
} // end constructor
// ADD TWO MORE CONSTRUCTORS
/**
* Retrieves the data portion of this node.
*
* @return The object in the data portion of the node.
*/
public T getData() {
return data;
} // end getData
/**
* Sets the data portion of this node.
*
* @param newData The data object.
*/
public void setData(T newData) {
data = newData;
} // end setData
/**
* Retrieves the left child of this node.
*
* @return The node that is this node's left child.
*/
public BinaryNode
return leftChild;
} // end getLeftChild
/**
* Sets this node's left child to a given node.
*
* @param newLeftChild A node that will be the left child.
*/
public void setLeftChild(BinaryNode
leftChild = newLeftChild;
} // end setLeftChild
/**
* Detects whether this node has a left child.
*
* @return True if the node has a left child.
*/
public boolean hasLeftChild() {
return leftChild != null;
} // end hasLeftChild
/**
* Retrieves the right child of this node.
*
* @return The node that is this node's right child.
*/
public BinaryNode
return rightChild;
} // end getRightChild
/**
* Sets this nodes's right child to a given node.
*
* @param newRightChild A node that will be the right child.
*/
public void setRightChild(BinaryNode
rightChild = newRightChild;
} // end setRightChild
/**
* Detects whether this node has a right child.
*
* @return True if the node has a right child.
*/
public boolean hasRightChild() {
return rightChild != null;
} // end hasRightChild
/**
* Detects whether this node is a leaf.
*
* @return True if the node is a leaf.
*/
public boolean isLeaf() {
return (leftChild == null) && (rightChild == null);
} // end isLeaf
/**
* Computes the height of the subtree rooted at this node.
*
* @return The height of the subtree rooted at this node.
*/
public int getHeight() {
return getHeight(this); // Call private getHeight
} // end getHeight
private int getHeight(BinaryNode
int height = 0;
if (node != null) {
height = 1 + Math.max(getHeight(node.getLeftChild()),
getHeight(node.getRightChild()));
}
return height;
} // end getHeight
/**
* Counts the nodes in the subtree rooted at this node.
*
* @return The number of nodes in the subtree rooted at this node.
*/
public int getNumberOfNodes() {
int leftNumber = 0;
int rightNumber = 0;
if (leftChild != null) {
leftNumber = leftChild.getNumberOfNodes();
}
if (rightChild != null) {
rightNumber = rightChild.getNumberOfNodes();
}
return 1 + leftNumber + rightNumber;
} // end getNumberOfNodes
/**
* Copies the subtree rooted at this node.
*
* @return The root of a copy of the subtree rooted at this node.
*/
public BinaryNode
BinaryNode
if (leftChild != null) {
newRoot.setLeftChild(leftChild.copy());
}
if (rightChild != null) {
newRoot.setRightChild(rightChild.copy());
}
return newRoot;
} // end copy
// ADD IN ANOTHER COPY THAT TAKES A PARENT REFERENCE
// ADD IN ACCESSORS FOR THE PARENT REFERENCE
// AND THREAD REFERENCE
} // end BinaryNode
**********************************************************************************************
package TreePackage;
/** An implementation of the ADT Binary Search Tree.
*
*/
public class BinarySearchTree
extends BinaryTree
implements SearchTreeInterface
{
public BinarySearchTree()
{
super();
} // end default constructor
public BinarySearchTree(T rootEntry)
{
super();
setRootNode(new BinaryNode
} // end constructor
public void setTree(T rootData) // disable setTree (see Segment 25.6)
{
throw new UnsupportedOperationException();
} // end setTree
public void setTree(T rootData, BinaryTreeInterface
BinaryTreeInterface
{
throw new UnsupportedOperationException();
} // end setTree
public T getEntry(T entry)
{
return findEntry(getRootNode(), entry);
} // end getEntry
private T findEntry(BinaryNode
{
T result = null;
if (rootNode != null)
{
T rootEntry = rootNode.getData();
if (entry.equals(rootEntry))
result = (T) rootEntry;
else if (entry.compareTo(rootEntry) < 0)
result = findEntry(rootNode.getLeftChild(), entry);
else
result = findEntry(rootNode.getRightChild(), entry);
} // end if
return result;
} // end findEntry
public boolean contains(T entry)
{
return getEntry(entry) != null;
} // end contains
public T add(T newEntry)
{
T result = null;
if (isEmpty())
setRootNode(new BinaryNode
else
result = addEntry(newEntry);
return result;
} // end add
/** Adds newEntry to the nonempty subtree rooted at rootNode. (non-recursive).
@param newEntry An item to add to the search tree.
*/
private T addEntry(T newEntry)
{
BinaryNode
assert currentNode != null;
T result = null;
boolean found = false;
while (!found)
{
T currentEntry = currentNode.getData();
int comparison = newEntry.compareTo(currentEntry);
if (comparison == 0)
{ // newEntry matches currentEntry;
// return and replace currentEntry
found = true;
result = currentEntry;
currentNode.setData(newEntry);
}
else if (comparison < 0)
{
if (currentNode.hasLeftChild())
currentNode = currentNode.getLeftChild();
else
{
// Add node on the left side
found = true;
// CHANGE THIS TO SET PARENT POINTERS AND FIX UP THREADS
currentNode.setLeftChild(new BinaryNode
} // end if
}
else
{
assert comparison > 0;
if (currentNode.hasRightChild())
currentNode = currentNode.getRightChild();
else
{
// Add node on the right side
found = true;
// CHANGE THIS TO SET PARENT POINTERS AND FIX UP THREADS
//currentNode.setRightChild(new BinaryNode
} // end if
} // end if
} // end while
return result;
} // end addEntry
/** Removes entry from the search tree (non-recursive).
* @return The item if found, otherwise return null.
*/
public T remove(T entry)
{
T result = null;
boolean found = false;
// Locate node (and its parent) that contains a match for entry
NodePair pair = findNode(entry);
BinaryNode
BinaryNode
if (currentNode != null) // Entry is found
{
result = currentNode.getData(); // Get entry to be removed
// Case 1: currentNode has two children
if (currentNode.hasLeftChild() && currentNode.hasRightChild())
{
// Replace entry in currentNode with the entry in another node
// that has at most one child; that node can be deleted
// Get node to remove (contains inorder predecessor; has at
// most one child) and its parent
pair = getNodeToRemove(currentNode);
BinaryNode
parentNode = pair.getSecond();
// Copy entry from nodeToRemove to currentNode
currentNode.setData(nodeToRemove.getData());
currentNode = nodeToRemove;
// Assertion: currentNode is the node to be removed; it has at most one child
// Assertion: Case 1 has been transformed to Case 2
} // end if
// Case 2: currentNode has at most one child; delete it
removeNode(currentNode, parentNode);
} // end if
return result;
} // end remove
private NodePair findNode(T entry)
{
BinaryNode
BinaryNode
NodePair result = new NodePair();
boolean found = false;
while (!found && currentNode != null)
{
T currentData = currentNode.getData();
int comparison = entry.compareTo(currentData);
if (comparison == 0) // entry == current entry
{
found = true;
}
else if (comparison < 0) // entry < current entry
{
parentNode = currentNode;
currentNode = currentNode.getLeftChild();
}
else // entry > root entry
{
parentNode = currentNode;
currentNode = currentNode.getRightChild();
}
}
if (found)
result = new NodePair(currentNode, parentNode);
// found entry is currentNode.getData()
return result;
} // end findNode
private NodePair getNodeToRemove(BinaryNode
{
// Find the inorder predecessor by searching the left subtree;
// it will be the largest entry in the subtree, occurring
// in the node are far right as possible.
BinaryNode
BinaryNode
BinaryNode
while (rightChild.hasRightChild())
{
priorNode = rightChild;
rightChild = rightChild.getRightChild();
} // end while
// rightChild contains the inorder predecessor and is the node to
// remove; priorNode is its parent
return new NodePair(rightChild, priorNode);
} // end getNodeToRemove
// Remove this node directly, it has at most 1 child
private void removeNode(BinaryNode
BinaryNode
{
BinaryNode
if (nodeToRemove.hasLeftChild())
{
childNode = nodeToRemove.getLeftChild();
}
else
{
childNode = nodeToRemove.getRightChild();
}
// Assertion: If nodeToRemove is a leaf, childNode is null
assert (nodeToRemove.isLeaf() && childNode == null) ||
!nodeToRemove.isLeaf();
if (nodeToRemove == getRootNode())
{
setRootNode(childNode);
}
else if (parentNode.getLeftChild() == nodeToRemove)
{
parentNode.setLeftChild(childNode);
}
else
{
parentNode.setRightChild(childNode);
}
} // end removeNode
private class NodePair
{
private BinaryNode
private BinaryNode
public NodePair()
{
first = null;
second = null;
}
public NodePair(BinaryNode
{
first = myFirst;
second = mySecond;
}
public BinaryNode
{
return first;
}
public BinaryNode
{
return second;
}
}
}
****************************************************************************************
package TreePackage;
/**
* An implementation of the ADT Binary Tree.
*
*/
import java.util.*;
public class BinaryTree
{
private BinaryNode
public BinaryTree() {
root = null;
} // end default constructor
public BinaryTree(T rootData) {
root = new BinaryNode
} // end constructor
public BinaryTree(T rootData, BinaryTree
BinaryTree
privateSetTree(rootData, leftTree, rightTree);
} // end constructor
public void setTree(T rootData) {
root = new BinaryNode
} // end setTree
public void setTree(T rootData, BinaryTreeInterface
BinaryTreeInterface
privateSetTree(rootData, (BinaryTree
} // end setTree
private void privateSetTree(T rootData,
BinaryTree
root = new BinaryNode
if ((leftTree != null) && !leftTree.isEmpty()) {
root.setLeftChild(leftTree.root);
// ADD CODE TO SET THE PARENT AND THREAD OF THE LEFT CHILD
}
if ((rightTree != null) && !rightTree.isEmpty()) {
if (rightTree != leftTree) {
root.setRightChild(rightTree.root);
} else {
root.setRightChild(rightTree.root.copy());
}
// ADD CODE TO SET THE PARENT OF THE RiGHT CHILD
// SET THE THREAD OUT OF THE ROOT
} // end if
if ((leftTree != null) && (this != leftTree)) {
leftTree.clear();
}
if ((rightTree != null) && (this != rightTree)) {
rightTree.clear();
}
} // end privateSetTree
public T getRootData() {
if (isEmpty()) {
throw new EmptyTreeException("Empty tree for operation getRootData");
} else {
return root.getData();
}
} // end getRootData
public boolean isEmpty() {
return root == null;
} // end isEmpty
public void clear() {
root = null;
} // end clear
protected void setRootData(T rootData) {
root.setData(rootData);
} // end setRootData
protected void setRootNode(BinaryNode
root = rootNode;
} // end setRootNode
protected BinaryNode
return root;
} // end getRootNode
public int getHeight() {
// Modified from Carrano to return 0 if the tree is empty
if (root == null) {
return 0;
} else {
return root.getHeight();
}
} // end getHeight
public int getNumberOfNodes() {
// Modified from Carrano to return 0 if the tree is empty
if (root == null) {
return 0;
} else {
return root.getNumberOfNodes();
}
} // end getNumberOfNodes
public void inorderTraverse() {
inorderTraverse(root);
} // end inorderTraverse
private void inorderTraverse(BinaryNode
if (node != null) {
inorderTraverse(node.getLeftChild());
System.out.println(node.getData());
inorderTraverse(node.getRightChild());
} // end if
} // end inorderTraverse
//The inorder Iterator that uses the stack will be replaced
//by one that uses threads
private class InorderIterator implements Iterator
private Stack
private BinaryNode
public InorderIterator() {
nodeStack = new Stack
currentNode = root;
} // end default constructor
public boolean hasNext() {
return !nodeStack.isEmpty() || (currentNode != null);
} // end hasNext
public T next() {
BinaryNode
// Find leftmost node with no left child
while (currentNode != null) {
nodeStack.push(currentNode);
currentNode = currentNode.getLeftChild();
} // end while
// Get leftmost node, then move to its right subtree
if (!nodeStack.isEmpty()) {
nextNode = nodeStack.pop();
assert nextNode != null; // Since nodeStack was not empty
// before the pop
currentNode = nextNode.getRightChild();
} else {
throw new NoSuchElementException();
}
return nextNode.getData();
} // end next
public void remove() {
throw new UnsupportedOperationException();
} // end remove
} // end InorderIterator
/* write an inorder iterator.
* @return The iterator.
*/
public Iterator
return new InorderIterator();
}
// Only the one iterator will be implemented by this code
public Iterator
throw new RuntimeException("Pre order iterators not yet supported by this class");
}
public Iterator
throw new RuntimeException("Post order iterators not yet supported by this class");
}
public Iterator
throw new RuntimeException("Level order iterators not yet supported by this class");
}
// ADD IN METHODS FOR ACCESSING THE TREE
}
**********************************************************************************
package TreePackage;
/** An interface for the ADT Binary Tree.
*
*/
public interface BinaryTreeInterface
{
/** Sets this binary tree to a new one-node binary tree.
* @param rootData The object that is the data for the new tree's root.
*/
public void setTree(T rootData);
/** Sets this binary tree to a new binary tree.
* @param rootData The object that is the data for the new tree's root.
* @param leftTree The left subtree of the new tree.
* @param rightTree The right subtree of the new tree. */
public void setTree(T rootData, BinaryTreeInterface
BinaryTreeInterface
} // end BinaryTreeInterface
****************************************************************************
/**
* An exception used to indicate an attempt to access an empty tree.
*
*/
package TreePackage;
public final class EmptyTreeException extends RuntimeException {
public EmptyTreeException(String s) {
super(s);
}
}
********************************************************************************
package TreePackage;
import java.util.Iterator;
/** An interface for the ADT Search Tree.
*
*/
public interface SearchTreeInterface
extends TreeInterface
{
/** Searches for a specific entry in this tree.
* @param entry An object to be found.
* @return True if the object was found in the tree. */
public boolean contains(T entry);
/** Retrieves a specific entry in this tree.
* @param entry An object to be found.
* @return Either the object that was found in the tree or
*null if no such object exists */
public T getEntry(T entry);
/** Adds a new entry to this tree, if if does not match an
* existing object in the tree. Ohterwise, replaces the existing
* object with the new entry.
* @param newEntry An object to be added to the tree.
* @return Either null if newEntry was not in the tree already,
*or the existing entry that matched the parameter
*newEntry and has been replaced in the tree. */
public T add(T newEntry);
/** Removes a specific entry from this tree.
* @param entry An object to be removed.
* @return Either the object that was removed from the tree or
*null if no such object exists. */
public T remove(T entry);
/** Creates an iterator that traverses all entries in this
*tree.
* @return An iterator that provides sequential and ordered access to the
*entries in the tree. */
public Iterator
} // end SearchTreeInterface
**************************************************************************************
package TreePackage;
/** An interface for the ADT Tree.
*
*/
public interface TreeInterface
{
public T getRootData();
public int getHeight();
public int getNumberOfNodes();
public boolean isEmpty();
public void clear();
} // end TreeInterface
***************************************************************************
package TreePackage;
/** An interface for the ADT Tree Iterator.
*
*/
import java.util.Iterator;
public interface TreeIteratorInterface
{
public Iterator
public Iterator
public Iterator
public Iterator
} // end TreeIteratorInterface
*****************************************************************************************
There's total 8 java file in TreePackage.
I need to complete the code for first three file which are
BinaryNode, BinarySearchTree, and Binary Tree
Thank you;0
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help