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-lab 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. 286 Lab 20 Binary Search Trees 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-lab 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-lab 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.) 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 }

*********************************************************************************************************************************************************

Lab 20

Binary Search Trees

286

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

:

pub

lic BinaryNode getThread()

public vo

id 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 pre

-

lab 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

g

etLeftmostInSubtree()

in

BinaryNode

. Refer to the pre

-

lab 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

B

inaryTree

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

****************************

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

}