Question
*JAVA You will be coding new methods for binary search trees. The first method you will implement is a recursive minimum computation on a tree,
*JAVA You will be coding new methods for binary search trees. The first method you will implement is a recursive minimum computation on a tree, min2(). You may look at the iterative version in the code to understand the functionality, but your implementation should use recursion and return the smallest data element in the tree.
The second operation you will be coding is a count of the number of leaves in the tree, leafCount(). For this method, you should develop an iterative (i.e., NOT recursive) method that returns an integer count of the number of leaves in the tree. Your implementation will use a similar algorithm to the iterative size method discussed in class, you just need to figure out what operations to perform when you visit each node. To implement the method, use the Java Stack class in Java.util.
The last operation you will be coding is a count of the height of the tree, height(). For this method, use recursion to determine the number of edges between the root of the tree and the deepest leaf node. As an example, in the tree pictured in Figure 1, the height of the tree is the number of edges between hello and is.
Use the template code provided online as a framework for this lab. All method headers are already implemented, you only need to fill in the methods where commented. You can use the included Lab12.java as test driver code to see if your program is working correctly. You will be editing the included file BinarySearchTree.java.
Rubric: Compiles without errors. Recursive min correctly implemented. Iterative leafCount correctly implemented with built-in stacks. Recursive height operation correctly implemented.
SUBMIT: modified BinarySearchTree.java
BinarySearchTree.java (unmodified)
import java.util.*; // Iterator, Comparator
import ch04.queues.*;
import ch02.stacks.*;
import support.BSTNode;
public class BinarySearchTree implements BSTInterface
{
protected BSTNode root; // reference to the root of this BST
protected Comparator comp; // used for all comparisons
protected boolean found; // used by remove
public BinarySearchTree()
// Precondition: T implements Comparable
// Creates an empty BST object - uses the natural order of elements.
{
root = null;
comp = new Comparator()
{
public int compare(T element1, T element2)
{
return ((Comparable)element1).compareTo(element2);
}
};
}
public BinarySearchTree(Comparator comp)
// Creates an empty BST object - uses Comparator comp for order
// of elements.
{
root = null;
this.comp = comp;
}
public boolean isFull()
// Returns false; this link-based BST is never full.
{
return false;
}
public boolean isEmpty()
// Returns true if this BST is empty; otherwise, returns false.
{
return (root == null);
}
public T min()
// If this BST is empty, returns null;
// otherwise returns the smallest element of the tree.
{
if (isEmpty())
return null;
else
{
BSTNode node = root;
while (node.getLeft() != null)
node = node.getLeft();
return node.getInfo();
}
}
public T max()
// If this BST is empty, returns null;
// otherwise returns the largest element of the tree.
{
if (isEmpty())
return null;
else
{
BSTNode node = root;
while (node.getRight() != null)
node = node.getRight();
return node.getInfo();
}
}
private int recSize(BSTNode node)
// Returns the number of elements in subtree rooted at node.
{
if (node == null)
return 0;
else
return 1 + recSize(node.getLeft()) + recSize(node.getRight());
}
public int size()
// Returns the number of elements in this BST.
{
return recSize(root);
}
public int size2()
// Returns the number of elements in this BST.
{
int count = 0;
if (root != null)
{
LinkedStack> nodeStack = new LinkedStack>();
BSTNode currNode;
nodeStack.push(root);
while (!nodeStack.isEmpty())
{
currNode = nodeStack.top();
nodeStack.pop();
count++;
if (currNode.getLeft() != null)
nodeStack.push(currNode.getLeft());
if (currNode.getRight() != null)
nodeStack.push(currNode.getRight());
}
}
return count;
}
private boolean recContains(T target, BSTNode node)
// Returns true if the subtree rooted at node contains info i such that
// comp.compare(target, i) == 0; otherwise, returns false.
{
if (node == null)
return false; // target is not found
else if (comp.compare(target, node.getInfo()) < 0)
return recContains(target, node.getLeft()); // Search left subtree
else if (comp.compare(target, node.getInfo()) > 0)
return recContains(target, node.getRight()); // Search right subtree
else
return true; // target is found
}
public boolean contains (T target)
// Returns true if this BST contains a node with info i such that
// comp.compare(target, i) == 0; otherwise, returns false.
{
return recContains(target, root);
}
private T recGet(T target, BSTNode node)
// Returns info i from the subtree rooted at node such that
// comp.compare(target, i) == 0; if no such info exists, returns null.
{
if (node == null)
return null; // target is not found
else if (comp.compare(target, node.getInfo()) < 0)
return recGet(target, node.getLeft()); // get from left subtree
else
if (comp.compare(target, node.getInfo()) > 0)
return recGet(target, node.getRight()); // get from right subtree
else
return node.getInfo(); // target is found
}
public T get(T target)
// Returns info i from node of this BST where comp.compare(target, i) == 0;
// if no such node exists, returns null.
{
return recGet(target, root);
}
private BSTNode recAdd(T element, BSTNode node)
// Adds element to tree rooted at node; tree retains its BST property.
{
if (node == null)
// Addition place found
node = new BSTNode(element);
else if (comp.compare(element, node.getInfo()) <= 0)
node.setLeft(recAdd(element, node.getLeft())); // Add in left subtree
else
node.setRight(recAdd(element, node.getRight())); // Add in right subtree
return node;
}
public boolean add (T element)
// Adds element to this BST. The tree retains its BST property.
{
root = recAdd(element, root);
return true;
}
/*
public boolean add (T element)
// Adds element to this BST. The tree retains its BST property.
{
BSTNode newNode = new BSTNode(element);
BSTNode prev = null, curr = null;
if (root == null)
root = newNode;
else
{
curr = root;
while (curr != null)
{
if (comp.compare(element, curr.getInfo()) <= 0)
{
prev = curr;
curr = curr.getLeft();
}
else
{
prev = curr;
curr = curr.getRight();
}
}
if (comp.compare(element, prev.getInfo()) <= 0)
prev.setLeft(newNode);
else
prev.setLeft(newNode);
}
return true;
}
*/
private T getPredecessor(BSTNode subtree)
// Returns the information held in the rightmost node of subtree
{
BSTNode temp = subtree;
while (temp.getRight() != null)
temp = temp.getRight();
return temp.getInfo();
}
private BSTNode removeNode(BSTNode node)
// Removes the information at node from the tree.
{
T data;
if (node.getLeft() == null)
return node.getRight();
else if (node.getRight() == null)
return node.getLeft();
else
{
data = getPredecessor(node.getLeft());
node.setInfo(data);
node.setLeft(recRemove(data, node.getLeft()));
return node;
}
}
private BSTNode recRemove(T target, BSTNode node)
// Removes element with info i from tree rooted at node such that
// comp.compare(target, i) == 0 and returns true;
// if no such node exists, returns false.
{
if (node == null)
found = false;
else if (comp.compare(target, node.getInfo()) < 0)
node.setLeft(recRemove(target, node.getLeft()));
else if (comp.compare(target, node.getInfo()) > 0)
node.setRight(recRemove(target, node.getRight()));
else
{
node = removeNode(node);
found = true;
}
return node;
}
public boolean remove (T target)
// Removes a node with info i from tree such that comp.compare(target,i) == 0
// and returns true; if no such node exists, returns false.
{
root = recRemove(target, root);
return found;
}
public Iterator getIterator(BSTInterface.Traversal orderType)
// Creates and returns an Iterator providing a traversal of a "snapshot"
// of the current tree in the order indicated by the argument.
// Supports Preorder, Postorder, and Inorder traversal.
{
final LinkedQueue infoQueue = new LinkedQueue();
if (orderType == BSTInterface.Traversal.Preorder)
preOrder(root, infoQueue);
else
if (orderType == BSTInterface.Traversal.Inorder)
inOrder(root, infoQueue);
else
if (orderType == BSTInterface.Traversal.Postorder)
postOrder(root, infoQueue);
return new Iterator()
{
public boolean hasNext()
// Returns true if the iteration has more elements; otherwise returns false.
{
return !infoQueue.isEmpty();
}
public T next()
// Returns the next element in the iteration.
// Throws NoSuchElementException - if the iteration has no more elements
{
if (!hasNext())
throw new IndexOutOfBoundsException("illegal invocation of next " +
" in BinarySearchTree iterator. ");
return infoQueue.dequeue();
}
public void remove()
// Throws UnsupportedOperationException.
// Not supported. Removal from snapshot iteration is meaningless.
{
throw new UnsupportedOperationException("Unsupported remove attempted on "
+ "BinarySearchTree iterator. ");
}
};
}
private void preOrder(BSTNode node, LinkedQueue q)
// Enqueues the elements from the subtree rooted at node into q in preOrder.
{
if (node != null)
{
q.enqueue(node.getInfo());
preOrder(node.getLeft(), q);
preOrder(node.getRight(), q);
}
}
private void inOrder(BSTNode node, LinkedQueue q)
// Enqueues the elements from the subtree rooted at node into q in inOrder.
{
if (node != null)
{
inOrder(node.getLeft(), q);
q.enqueue(node.getInfo());
inOrder(node.getRight(), q);
}
}
private void postOrder(BSTNode node, LinkedQueue q)
// Enqueues the elements from the subtree rooted at node into q in postOrder.
{
if (node != null)
{
postOrder(node.getLeft(), q);
postOrder(node.getRight(), q);
q.enqueue(node.getInfo());
}
}
public Iterator iterator()
// InOrder is the default, "natural" order.
{
return getIterator(BSTInterface.Traversal.Inorder);
}
}
BSTInterface.java
package ch07.trees;
import ch05.collections.CollectionInterface;
import java.util.Iterator;
public interface BSTInterface
{
// Used to specify traversal order.
public enum Traversal {Inorder, Preorder, Postorder};
T min();
// If this BST is empty, returns null;
// otherwise returns the smallest element of the tree.
T max();
// If this BST is empty, returns null;
// otherwise returns the largest element of the tree.
public Iterator
// Creates and returns an Iterator providing a traversal of a "snapshot"
// of the current tree in the order indicated by the argument.
}
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
Database Design And SQL For DB2
Authors: James Cooper
1st Edition
1583473572, 978-1583473573
