Write a method called writeLessThan void writeLessThan(T searchElement) Your met

ID: 3767138 • Letter: W

Question

Write a method called writeLessThan void writeLessThan(T searchElement) Your method should gather the elements(use any collection for this array or an arraylist) that are less than the searchElement. Your collection should be in an ascending order and note that searchElement need not be in the tree…

Hint: Consider using inOrder…

Test your method in your client code.

import ch05.queues.*;
import ch03.stacks.*;
import java.util.LinkedList;
import support.BSTNode;

public class BinarySearchTree>
implements BSTInterface
{
protected BSTNode root; // reference to the root of this BST

boolean found; // used by remove
int value;
// for traversals
protected LinkedUnbndQueue inOrderQueue; // queue of info
protected LinkedUnbndQueue preOrderQueue; // queue of info
protected LinkedUnbndQueue postOrderQueue; // queue of info

public BinarySearchTree()
// Creates an empty BST object.
{
root = null;
}

public boolean isEmpty()
// Returns true if this BST is empty; otherwise, returns false.
{
return (root == null);
}

private int recSize(BSTNode tree)
// Returns the number of elements in tree.
{
if (tree == null)
return 0;
else
return recSize(tree.getLeft()) + recSize(tree.getRight()) + 1;
}

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> hold = new LinkedStack>();
BSTNode currNode;
hold.push(root);
while (!hold.isEmpty())
{
currNode = hold.top();
hold.pop();
count++;
if (currNode.getLeft() != null)
hold.push(currNode.getLeft());
if (currNode.getRight() != null)
hold.push(currNode.getRight());
}
}
return count;
}

private boolean recContains(T element, BSTNode tree)
// Returns true if tree contains an element e such that
// e.compareTo(element) == 0; otherwise, returns false.
{
if (tree == null)
return false; // element is not found
else if (element.compareTo(tree.getInfo()) < 0)
return recContains(element, tree.getLeft()); // Search left subtree
else if (element.compareTo(tree.getInfo()) > 0)
return recContains(element, tree.getRight()); // Search right subtree
else
return true; // element is found
}

public boolean contains (T element)
// Returns true if this BST contains an element e such that
// e.compareTo(element) == 0; otherwise, returns false.
{
return recContains(element, root);
}

private T recGet(T element, BSTNode tree)
// Returns an element e from tree such that e.compareTo(element) == 0;
// if no such element exists, returns null.
{
if (tree == null)
return null; // element is not found
else if (element.compareTo(tree.getInfo()) < 0)
return recGet(element, tree.getLeft()); // get from left subtree
else
if (element.compareTo(tree.getInfo()) > 0)
return recGet(element, tree.getRight()); // get from right subtree
else
return tree.getInfo(); // element is found
}

public T get(T element)
// Returns an element e from this BST such that e.compareTo(element) == 0;
// if no such element exists, returns null.
{
return recGet(element, root);
}

private BSTNode recAdd(T element, BSTNode tree)
// Adds element to tree; tree retains its BST property.
{
if (tree == null)
// Addition place found
tree = new BSTNode(element);
else if (element.compareTo(tree.getInfo()) <= 0)
tree.setLeft(recAdd(element, tree.getLeft())); // Add in left subtree
else
tree.setRight(recAdd(element, tree.getRight())); // Add in right subtree
return tree;
}
@Override
public void add (T element)
// Adds element to this BST. The tree retains its BST property.
{
root = recAdd(element, root);
}

private T getPredecessor(BSTNode tree)
// Returns the information held in the rightmost node in tree
{
while (tree.getRight() != null)
tree = tree.getRight();
return tree.getInfo();
}

private BSTNode removeNode(BSTNode tree)
// Removes the information at the node referenced by tree.
// The user's data in the node referenced by tree is no
// longer in the tree. If tree is a leaf node or has only
// a non-null child pointer, the node pointed to by tree is
// removed; otherwise, the user's data is replaced by its
// logical predecessor and the predecessor's node is removed.
{
T data;

if (tree.getLeft() == null)
return tree.getRight();
else if (tree.getRight() == null)
return tree.getLeft();
else
{
data = getPredecessor(tree.getLeft());
tree.setInfo(data);
tree.setLeft(recRemove(data, tree.getLeft()));
return tree;
}
}

private BSTNode recRemove(T element, BSTNode tree)
// Removes an element e from tree such that e.compareTo(element) == 0
// and returns true; if no such element exists, returns false.
{
if (tree == null)
found = false;
else if (element.compareTo(tree.getInfo()) < 0)
tree.setLeft(recRemove(element, tree.getLeft()));
else if (element.compareTo(tree.getInfo()) > 0)
tree.setRight(recRemove(element, tree.getRight()));
else
{
tree = removeNode(tree);
found = true;
}
return tree;
}

public boolean remove (T element)
// Removes an element e from this BST such that e.compareTo(element) == 0
// and returns true; if no such element exists, returns false.
{
root = recRemove(element, root);
return found;
}

private void inOrder(BSTNode tree)
// Initializes inOrderQueue with tree elements in inOrder order.
{
if (tree != null)
{
inOrder(tree.getLeft());
inOrderQueue.enqueue(tree.getInfo());
inOrder(tree.getRight());
}
}

private void preOrder(BSTNode tree)
// Initializes preOrderQueue with tree elements in preOrder order.
{
if (tree != null)
{
preOrderQueue.enqueue(tree.getInfo());
preOrder(tree.getLeft());
preOrder(tree.getRight());
}
}

private void postOrder(BSTNode tree)
// Initializes postOrderQueue with tree elements in postOrder order.
{
if (tree != null)
{
postOrder(tree.getLeft());
postOrder(tree.getRight());
postOrderQueue.enqueue(tree.getInfo());
}
}

public int reset(int orderType)
// Initializes current position for an iteration through this BST
// in orderType order. Returns current number of nodes in the BST.
{
int numNodes = size();

if (orderType == INORDER)
{
inOrderQueue = new LinkedUnbndQueue();
inOrder(root);
}
else
if (orderType == PREORDER)
{
preOrderQueue = new LinkedUnbndQueue();
preOrder(root);
}
if (orderType == POSTORDER)
{
postOrderQueue = new LinkedUnbndQueue();
postOrder(root);
}
return numNodes;
}
@Override
public T getNext (int orderType)
// Preconditions: The BST is not empty
// The BST has been reset for orderType
// The BST has not been modified since the most recent reset
// The end of orderType iteration has not been reached
//
// Returns the element at the current position on this BST for orderType
// and advances the value of the current position based on the orderType.
{
if (orderType == INORDER)
return inOrderQueue.dequeue();
else
if (orderType == PREORDER)
return preOrderQueue.dequeue();
else
if (orderType == POSTORDER)
return postOrderQueue.dequeue();
else return null;
}
public int height(BSTNode node)
{
if (node==null)
return 0;
else
return 1 + Math.max(height(node.getLeft()), height(node.getRight()));
}

Explanation / Answer

import ch05.queues.*;
import ch03.stacks.*;
import java.util.LinkedList;
import support.BSTNode;

import java.io.*;

import java.util.*;