Question
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.
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
public vo
id setThread(BinaryNode
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
private BinaryNode
public BinaryTree() { root = null; } // end default constructor
public BinaryTree(T rootData) { root = new BinaryNode
public BinaryTree(T rootData, BinaryTree
public void setTree(T rootData) { root = new BinaryNode
public void setTree(T rootData, BinaryTreeInterface
private void privateSetTree(T rootData, BinaryTree
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
protected BinaryNode
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
// The inorder Iterator that uses the stack will be replaced // by one that uses threads private class InorderIterator implements Iterator
private Stack
public InorderIterator() { nodeStack = new Stack
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
/* Create an inorder iterator. * @return The iterator. */ public Iterator
// Only the one iterator will be implemented by this code public Iterator
public Iterator
public Iterator
// ADD IN METHODS FOR ACCESSING THE TREE
}
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