In this lab you will modify a binary search tree so that the nodes are threaded in order. In-order traversal will be implemented using the thread. A client using a binary search tree will be developed.

Codes are provided below:

Identifiers.java

import TreePackage.*; import java.io.*; import java.util.*;

/** * Find the unique identifiers from a .java file. * * @author Charles Hoot * @version 4.0 */ public class Identifiers {

public static void main(String args[]) {

String fileName = getFileName(); System.out.println(); BinarySearchTree unique = getPossibleIds(fileName); // ADD CODE HERE FOR PRINTING THE IDENTIFIERS } /** * Get the possible identifiers from the file. * * @return A tree of possible identifiers from the file. */ private static BinarySearchTree getPossibleIds(String theFileName) { Scanner input; String inString = ""; BinarySearchTree possible = new BinarySearchTree(); try { input = new Scanner(new File(theFileName ) );

//ADD CODE TO READ THE FILE AND CONSTRUCT THE BINARY SEARCH TREE } catch(IOException e) { System.out.println("There was an error with System.in"); System.out.println(e.getMessage()); } return possible; } private static String getFileName() { Scanner input; String inString = "data.txt"; try { input = new Scanner(System.in); System.out.println("Please enter the name of the file:"); inString = input.next(); } catch(Exception e) { System.out.println("There was an error with System.in"); System.out.println(e.getMessage()); System.out.println("Will try the default file name data.txt"); } return inString; } }

BinaryNode.java

package TreePackage;

/** * An implementation of the ADT Binary Node. * * This code is from Chapter 24 of * Data Structures and Abstractions with Java 4/e * by Carrano * * @version 4.0 */ 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

BinarySearchTree.java

package TreePackage; /** An implementation of the ADT Binary Search Tree. * * This code is from Chapter 25 of * Data Structures and Abstractions with Java 4/e * by Carrano * * @version 4.0 */ 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; } } }

BinaryTree.java

package TreePackage;

/** * An implementation of the ADT Binary Tree. * * This code is from Chapter 24 of * Data Structures and Abstractions with Java 4/e * by Carrano * * Modified to use Java's built in Stack class by Charles Hoot * * @version 4.0 */ 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

}