PLEASE COMPLETE PROGRAMS FOR THESES THREE FILES.

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.	Create and fully implement three new methods in BinaryNode:

public BinaryNode getParent() public void setParent(BinaryNode p) public boolean hasParent()

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 p to the duplicate.

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 original version 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. Create and fully implement three new methods in BinaryNode:

public BinaryNode getThread() public void setThread(BinaryNode target) public boolean hasThread()

Checkpoint: Compile BinarySearchTree, BinaryNode, and BinaryTree. All tests in TestBinaryTree and TestBST should still pass.

Step 14. Create 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. Create 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, create 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 create 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. Dont 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 Identifiers create a loop to read lines from the file.

Step 30. In the loop, read a line using Scanner and then use the line to create a StringTokenizer.

Step 31. Create 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 be a 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.

-------------------------------------------------------------------------------------------------------------------------------------------------------------

package TreePackage;

/** * An implementation of the ADT Binary Node. * */ class BinaryNode {

private T data; private BinaryNode leftChild; private BinaryNode rightChild; // 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 newLeftChild, BinaryNode newRightChild) { // 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 getLeftChild() { 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 newLeftChild) { 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 getRightChild() { 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 newRightChild) { 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 node) { 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 copy() { BinaryNode newRoot = new BinaryNode(data); 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(rootEntry)); } // end constructor public void setTree(T rootData) // disable setTree (see Segment 25.6) { throw new UnsupportedOperationException(); } // end setTree public void setTree(T rootData, BinaryTreeInterface leftTree, BinaryTreeInterface rightTree) { throw new UnsupportedOperationException(); } // end setTree public T getEntry(T entry) { return findEntry(getRootNode(), entry); } // end getEntry private T findEntry(BinaryNode rootNode, T entry) { 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(newEntry)); 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 currentNode = getRootNode(); 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(newEntry));

} // 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(newEntry)); } // 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 currentNode = pair.getFirst(); BinaryNode parentNode = pair.getSecond(); 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 nodeToRemove = pair.getFirst(); 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 parentNode = null; BinaryNode currentNode = getRootNode(); 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 currentNode) { // 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 leftSubtreeRoot = currentNode.getLeftChild(); BinaryNode rightChild = leftSubtreeRoot; BinaryNode priorNode = currentNode; 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 nodeToRemove, BinaryNode parentNode) { BinaryNode childNode;

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 first; private BinaryNode second;

public NodePair() { first = null; second = null; }

public NodePair(BinaryNode myFirst, BinaryNode mySecond) { first = myFirst; second = mySecond; } public BinaryNode getFirst() { return first; } public BinaryNode getSecond() { return second; } } }

-------------------------------------------------------------------------------------------------------------------------------------------------------------

package TreePackage;

/** * An implementation of the ADT Binary Tree. * */ import java.util.*;

public class BinaryTree implements BinaryTreeInterface {

private BinaryNode root;

public BinaryTree() { root = null; } // end default constructor

public BinaryTree(T rootData) { root = new BinaryNode(rootData); } // end constructor

public BinaryTree(T rootData, BinaryTree leftTree, BinaryTree rightTree) { privateSetTree(rootData, leftTree, rightTree); } // end constructor

public void setTree(T rootData) { root = new BinaryNode(rootData); } // end setTree

public void setTree(T rootData, BinaryTreeInterface leftTree, BinaryTreeInterface rightTree) { privateSetTree(rootData, (BinaryTree) leftTree, (BinaryTree) rightTree); } // end setTree

private void privateSetTree(T rootData, BinaryTree leftTree, BinaryTree rightTree) { root = new BinaryNode(rootData);

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 rootNode) { root = rootNode; } // end setRootNode

protected BinaryNode getRootNode() { 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 node) { 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> nodeStack; private BinaryNode currentNode;

public InorderIterator() { nodeStack = new Stack>(); currentNode = root; } // end default constructor

public boolean hasNext() { return !nodeStack.isEmpty() || (currentNode != null); } // end hasNext

public T next() { BinaryNode nextNode = null;

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

/* Create an inorder iterator. * @return The iterator. */ public Iterator getInorderIterator() { return new InorderIterator(); }

// Only the one iterator will be implemented by this code public Iterator getPreorderIterator() { throw new RuntimeException("Pre order iterators not yet supported by this class"); }

public Iterator getPostorderIterator() { throw new RuntimeException("Post order iterators not yet supported by this class"); }

public Iterator getLevelOrderIterator() { throw new RuntimeException("Level order iterators not yet supported by this class"); }

// ADD IN METHODS FOR ACCESSING THE TREE

}