package TreePackage; /** * An implementation of the ADT Binary Node. */ class BinaryNode { private T data; private BinaryNode leftChild; private BinaryNode rightChild; // ADD A PRIVATE VARIABLE TO HOLD A PRARENT 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 ANOTHER CONSTRUCTOR HERE THAT SETS ALL FOUR PRIVATE VARIABLES /** * 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 } // end BinaryNode
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 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 } // 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 /* Modified to use Java's built in stack class * */ 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 }
package TreePackage; /** * This interface is similar to the DecisionTreeInterface * and allows a client to move down from the root in a binary tree. */ public interface BinaryTreeAccessInterface extends BinaryTreeInterface { /** Gets the data in the current node. * @return The data object in the current node. * If there is no current node, return null. * */ public T getCurrentData(); /** Determines if the current node has a left child. * @return True if the left child is non-null. * If there is no current node, return null. * */ public boolean canAdvanceToLeft(); /** Sets the current node to the left child of * the current node. * If there is no left node, make the current null. * */ public void advanceToLeft(); /** Determines if the current node has a right child. * @return True if the right child is non-null. * */ public boolean canAdvanceToRight(); /** Sets the current node to the right child of * the current node. * If there is no right node, make the current null. * */ public void advanceToRight(); /** Sets the current node to the root of the tree.*/ public void resetAccess(); } // end BinaryTreeAccessInterface
package TreePackage; /** An interface for the ADT Binary Tree. */ public interface BinaryTreeInterface extends TreeInterface, TreeIteratorInterface { /** 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 leftTree, BinaryTreeInterface rightTree); } // end BinaryTreeInterface
package TreePackage; /** * This interface extends the access to a binary tree that has parent * pointers. */ public interface BinaryWithParentsTreeAccessInterface extends BinaryTreeAccessInterface { /** Determines if the current node has a parent * @return true if the parent point is non-null * */ public boolean canGoBackToParent(); /** Sets the current node to the parent of * the current node. */ public void goBackToParent(); } // end BinaryWithParentsTreeAccessInterface
/** * 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; /** 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 getPreorderIterator(); public Iterator getPostorderIterator(); public Iterator getInorderIterator(); public Iterator getLevelOrderIterator(); } // end TreeIteratorInterface
Place the subdirectory TreePackage' under this directory with the source files and place all of the package files in this subdirectory. This should now enable you to successfully compile and run the test applications. Modifying BinaryTree for BasicAccess The first task is to add methods to the Binary Tree class to implement the basic access given by BinaryTreeAccessInterface. Step1.Change the declaration of the BinaryTree so that it implements BinaryTreeAccessInterface Step 2.InBinaryTree, add the six methods required by BinaryTreeAccessInterface Step 3.InBinaryTree, add a private variable of type BinaryNode
that will reference the current access node Step 4.Implement each of the methods just added. Refer to the pre-lab. Step 5.Anytime the structure of the binary tree is changed, the access needs to be reset. Call rsetAccess) in the constructors, setTree, and clear Checkpoin: Compie BinaryNode and Binary Tree. Run TestBinary Tree and TestBasicAccess. All cests should pass. Modifying BinaryTree with Parent References Step 6. In the class BinaryNode, add a private variable that will hold the parent reference Step 7. Add a new constructor, which has four arguments: data, left, right, and parent Step 8Modify the constructor that takes three arguments to use the new constructor with null for the parent. Step 9. Create and fully implement three new methods in BinaryNode public BinaryNode*T> getParent ) public void setParent Binaryvode p) public boolean hasParent ) Checkpoin: Compile BinaryNode and Binary Tree. All ests in TestBinary Tree and TestBasicAccess should scill pass. Step 10. Make a duplicate of the method copy) in BinaryNode and add an argument BinaryNode p to the duplicate. Step 11.In the duplicate, set the parent of newRoot to be p Step 12. In the original, set the parent of nexRoot to be nul1. (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. If not, it is the responsibility of the method that called copy to set it correctly.) Step 13. In both the original and the duplicate, change the two recursive calls to copyso that they pass newRoot as the parameter Checkponc: BnaryNode should compile successfull;y. Checkpoint: Compile BinaryNode and BinaryTree. All tests in TestBinaryTree and TestBasicAccess should scill pass. Place the subdirectory TreePackage' under this directory with the source files and place all of the package files in this subdirectory. This should now enable you to successfully compile and run the test applications. Modifying BinaryTree for BasicAccess The first task is to add methods to the Binary Tree class to implement the basic access given by BinaryTreeAccessInterface. Step1.Change the declaration of the BinaryTree so that it implements BinaryTreeAccessInterface Step 2.InBinaryTree, add the six methods required by BinaryTreeAccessInterface Step 3.InBinaryTree, add a private variable of type BinaryNode that will reference the current access node Step 4.Implement each of the methods just added. Refer to the pre-lab. Step 5.Anytime the structure of the binary tree is changed, the access needs to be reset. Call rsetAccess) in the constructors, setTree, and clear Checkpoin: Compie BinaryNode and Binary Tree. Run TestBinary Tree and TestBasicAccess. All cests should pass. Modifying BinaryTree with Parent References Step 6. In the class BinaryNode, add a private variable that will hold the parent reference Step 7. Add a new constructor, which has four arguments: data, left, right, and parent Step 8Modify the constructor that takes three arguments to use the new constructor with null for the parent. Step 9. Create and fully implement three new methods in BinaryNode public BinaryNode*T> getParent ) public void setParent Binaryvode p) public boolean hasParent ) Checkpoin: Compile BinaryNode and Binary Tree. All ests in TestBinary Tree and TestBasicAccess should scill pass. Step 10. Make a duplicate of the method copy) in BinaryNode and add an argument BinaryNode p to the duplicate. Step 11.In the duplicate, set the parent of newRoot to be p Step 12. In the original, set the parent of nexRoot to be nul1. (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. If not, it is the responsibility of the method that called copy to set it correctly.) Step 13. In both the original and the duplicate, change the two recursive calls to copyso that they pass newRoot as the parameter Checkponc: BnaryNode should compile successfull;y. Checkpoint: Compile BinaryNode and BinaryTree. All tests in TestBinaryTree and TestBasicAccess should scill pass
