Extend the Binary Search Tree ADT to include a public method singleParentCount that returns the number of nodes in the tree that have only one child.

Please add the code in appropriate areas. Thank you

//----------------------------------------------------------------------------

// BinarySearchTree.java by Dale/Joyce/Weems Chapter 8

//

// Defines all constructs for a reference-based BST

//----------------------------------------------------------------------------

package ch08.trees;

import ch05.queues.*;

import ch03.stacks.*;

import support.BSTNode;

public class BinarySearchTree>

implements BSTInterface

{

protected BSTNode root; // reference to the root of this BST

boolean found; // used by remove

// 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;

}

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;

}

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;

}

}

BSTNode.java

//----------------------------------------------------------------------------

// BSTNode.java by Dale/Joyce/Weems Chapter 8

//

// Implements Comparable nodes for a binary search tree.

//----------------------------------------------------------------------------

package support;

public class BSTNode>

{

// Used to hold references to BST nodes for the linked implementation

protected T info; // The info in a BST node

protected BSTNode left; // A link to the left child node

protected BSTNode right; // A link to the right child node

public BSTNode(T info)

{

this.info = info;

left = null;

right = null;

}

public void setInfo(T info)

// Sets info of this BSTNode.

{

this.info = info;

}

public T getInfo()

// Returns info of this BSTNode.

{

return info;

}

public void setLeft(BSTNode link)

// Sets left link of this BSTNode.

{

left = link;

}

public void setRight(BSTNode link)

// Sets right link of this BSTNode.

{

right = link;

}

public BSTNode getLeft()

// Returns left link of this BSTNode.

{

return left;

}

public BSTNode getRight()

// Returns right link of this BSTNode.

{

return right;

}

}

ArrayListStack.java

//----------------------------------------------------------------------

// ArrayListStack.java by Dale/Joyce/Weems Chapter 3

//

// Implements UnboundedStackInterface using an ArrayList to

// hold the stack elements.

//----------------------------------------------------------------------

package ch03.stacks;

import java.util.*;

public class ArrayListStack implements UnboundedStackInterface

{

protected ArrayList stack; // ArrayList that holds stack elements

public ArrayListStack()

{

stack = new ArrayList();

}

public void push(T element)

// Places element at the top of this stack.

{

stack.add(element);

}

public void pop()

// Throws StackUnderflowException if this stack is empty,

// otherwise removes top element from this stack.

{

if (!isEmpty())

{

stack.remove(stack.size() - 1);

}

else

throw new StackUnderflowException("Pop attempted on an empty stack.");

}

public T top()

// Throws StackUnderflowException if this stack is empty,

// otherwise returns top element from this stack.

{

T topOfStack = null;

if (!isEmpty())

topOfStack = stack.get(stack.size() - 1);

else

throw new StackUnderflowException("Top attempted on an empty stack.");

return topOfStack;

}

public boolean isEmpty()

// Returns true if this stack is empty, otherwise returns false.

{

if (stack.size() == 0)

return true;

else

return false;

}

}

ArrayStack.java

//----------------------------------------------------------------

// ArrayStack.java by Dale/Joyce/Weems Chapter 3

//

// Implements BoundedStackInterface using an array to hold the

// stack elements.

//

// Two constructors are provided: one that creates an array of a

// default size and one that allows the calling program to

// specify the size.

//----------------------------------------------------------------

package ch03.stacks;

public class ArrayStack implements BoundedStackInterface

{

protected final int DEFCAP = 100; // default capacity

protected T[] stack; // holds stack elements

protected int topIndex = -1; // index of top element in stack

public ArrayStack()

{

stack = (T[]) new Object[DEFCAP];

}

public ArrayStack(int maxSize)

{

stack = (T[]) new Object[maxSize];

}

public void push(T element)

// Throws StackOverflowException if this stack is full,

// otherwise places element at the top of this stack.

{

if (!isFull())

{

topIndex++;

stack[topIndex] = element;

}

else

throw new StackOverflowException("Push attempted on a full stack.");

}

public void pop()

// Throws StackUnderflowException if this stack is empty,

// otherwise removes top element from this stack.

{

if (!isEmpty())

{

stack[topIndex] = null;

topIndex--;

}

else

throw new StackUnderflowException("Pop attempted on an empty stack.");

}

public T top()

// Throws StackUnderflowException if this stack is empty,

// otherwise returns top element from this stack.

{

T topOfStack = null;

if (!isEmpty())

topOfStack = stack[topIndex];

else

throw new StackUnderflowException("Top attempted on an empty stack.");

return topOfStack;

}

public boolean isEmpty()

// Returns true if this stack is empty, otherwise returns false.

{

if (topIndex == -1)

return true;

else

return false;

}

public boolean isFull()

// Returns true if this stack is full, otherwise returns false.

{

if (topIndex == (stack.length - 1))

return true;

else

return false;

}

}

BoundedStackInterface.java

//----------------------------------------------------------------------------

// BoundedStackInterface.java by Dale/Joyce/Weems Chapter 3

//

// Interface for a class that implements a stack of with a bound

// on the size of the stack. A stack is a last-in, first-out structure.

//----------------------------------------------------------------------------

package ch03.stacks;

public interface BoundedStackInterface extends StackInterface

{

void push(T element) throws StackOverflowException;

// Throws StackOverflowException if this stack is full,

// otherwise places element at the top of this stack.

boolean isFull();

// Returns true if this stack is full, otherwise returns false.

}

LinkedStack.java

//----------------------------------------------------------------------

// LinkedStack.java by Dale/Joyce/Weems Chapter 3

//

// Implements UnboundedStackInterface using a linked list

// to hold the stack elements.

//-----------------------------------------------------------------------

package ch03.stacks;

import support.LLNode;

public class LinkedStack implements UnboundedStackInterface

{

protected LLNode top; // reference to the top of this stack

public LinkedStack()

{

top = null;

}

public void push(T element)

// Places element at the top of this stack.

{

LLNode newNode = new LLNode(element);

newNode.setLink(top);

top = newNode;

}

public void pop()

// Throws StackUnderflowException if this stack is empty,

// otherwise removes top element from this stack.

{

if (!isEmpty())

{

top = top.getLink();

}

else

throw new StackUnderflowException("Pop attempted on an empty stack.");

}

public T top()

// Throws StackUnderflowException if this stack is empty,

// otherwise returns top element from this stack.

{

if (!isEmpty())

return top.getInfo();

else

throw new StackUnderflowException("Top attempted on an empty stack.");

}

public boolean isEmpty()

// Returns true if this stack is empty, otherwise returns false.

{

if (top == null)

return true;

else

return false;

}

}

StackInterface.java

//----------------------------------------------------------------------------

// StackInterface.java by Dale/Joyce/Weems Chapter 3

//

// Interface for a class that implements a stack of .

// A stack is a last-in, first-out structure.

//----------------------------------------------------------------------------

package ch03.stacks;

public interface StackInterface

{

void pop() throws StackUnderflowException;

// Throws StackUnderflowException if this stack is empty,

// otherwise removes top element from this stack.

T top() throws StackUnderflowException;

// Throws StackUnderflowException if this stack is empty,

// otherwise returns top element from this stack.

boolean isEmpty();

// Returns true if this stack is empty, otherwise returns false.

}

StackOverflowException.java

package ch03.stacks;

public class StackOverflowException extends RuntimeException

{

public StackOverflowException()

{

super();

}

public StackOverflowException(String message)

{

super(message);

}

}

StackUnderflowException.java

package ch03.stacks;

public class StackUnderflowException extends RuntimeException

{

public StackUnderflowException()

{

super();

}

public StackUnderflowException(String message)

{

super(message);

}

}

UnboundedStackInterface.java

//----------------------------------------------------------------------------

// UnboundedStackInterface.java by Dale/Joyce/Weems Chapter 3

//

// Interface for a class that implements a stack of with no bound

// on the size of the stack. A stack is a last-in, first-out structure.

//----------------------------------------------------------------------------

package ch03.stacks;

public interface UnboundedStackInterface extends StackInterface

{

void push(T element);

// Places element at the top of this stack.

}

ArrayBndQueue.java

//---------------------------------------------------------------------------

// ArrayBndQueue.java by Dale/Joyce/Weems Chapter 5

//

// Implements BoundedQueueInterface with an array to hold the queue elements.

//

// Two constructors are provided: one that creates a queue of a default

// capacity and one that allows the calling program to specify the capacity.

//---------------------------------------------------------------------------

package ch05.queues;

public class ArrayBndQueue implements BoundedQueueInterface

{

protected final int DEFCAP = 100; // default capacity

protected T[] queue; // array that holds queue elements

protected int numElements = 0; // number of elements n the queue

protected int front = 0; // index of front of queue

protected int rear; // index of rear of queue

public ArrayBndQueue()

{

queue = (T[]) new Object[DEFCAP];

rear = DEFCAP - 1;

}

public ArrayBndQueue(int maxSize)

{

queue = (T[]) new Object[maxSize];

rear = maxSize - 1;

}

public void enqueue(T element)

// Throws QueueOverflowException if this queue is full;

// otherwise, adds element to the rear of this queue.

{

if (isFull())

throw new QueueOverflowException("Enqueue attempted on a full queue.");

else

{

rear = (rear + 1) % queue.length;

queue[rear] = element;

numElements = numElements + 1;

}

}

public T dequeue()

// Throws QueueUnderflowException if this queue is empty;

// otherwise, removes front element from this queue and returns it.

{

if (isEmpty())

throw new QueueUnderflowException("Dequeue attempted on empty queue.");

else

{

T toReturn = queue[front];

queue[front] = null;

front = (front + 1) % queue.length;

numElements = numElements - 1;

return toReturn;

}

}

public boolean isEmpty()

// Returns true if this queue is empty; otherwise, returns false

{

return (numElements == 0);

}

public boolean isFull()

// Returns true if this queue is full; otherwise, returns false.

{

return (numElements == queue.length);

}

}

ArrayUnbndQueue.java

//---------------------------------------------------------------------------

// ArrayUnbndQueue.java by Dale/Joyce/Weems Chapter 5

//

// Implements UnboundedQueueInterface with an array to hold queue elements.

//

// Two constructors are provided; one that creates a queue of a default

// original capacity and one that allows the calling program to specify the

// original capacity.

//

// If an enqueue is attempted when there is no room available in the array, a

// new array is created, with capacity incremented by the original capacity.

//---------------------------------------------------------------------------

package ch05.queues;

public class ArrayUnbndQueue implements UnboundedQueueInterface

{

protected final int DEFCAP = 100; // default capacity

protected T[] queue; // array that holds queue elements

protected int origCap; // original capacity

protected int numElements = 0; // number of elements in the queue

protected int front = 0; // index of front of queue

protected int rear; // index of rear of queue

public ArrayUnbndQueue()

{

queue = (T[]) new Object[DEFCAP];

rear = DEFCAP - 1;

origCap = DEFCAP;

}

public ArrayUnbndQueue(int origCap)

{

queue = (T[]) new Object[origCap];

rear = origCap - 1;

this.origCap = origCap;

}

private void enlarge()

// Increments the capacity of the queue by an amount

// equal to the original capacity.

{

// create the larger array

T[] larger = (T[]) new Object[queue.length + origCap];

// copy the contents from the smaller array into the larger array

int currSmaller = front;

for (int currLarger = 0; currLarger < numElements; currLarger++)

{

larger[currLarger] = queue[currSmaller];

currSmaller = (currSmaller + 1) % queue.length;

}

// update instance variables

queue = larger;

front = 0;

rear = numElements - 1;

}

public void enqueue(T element)

// Adds element to the rear of this queue.

{

if (numElements == queue.length)

enlarge();

rear = (rear + 1) % queue.length;

queue[rear] = element;

numElements = numElements + 1;

}

public T dequeue()

// Throws QueueUnderflowException if this queue is empty;

// otherwise, removes front element from this queue and returns it.

{

if (isEmpty())

throw new QueueUnderflowException("Dequeue attempted on empty queue.");

else

{

T toReturn = queue[front];

queue[front] = null;

front = (front + 1) % queue.length;

numElements = numElements - 1;

return toReturn;

}

}

public boolean isEmpty()

// Returns true if this queue is empty; otherwise, returns false

{

return (numElements == 0);

}

}

BoundedQueueInterface.java

//----------------------------------------------------------------------------

// BoundedQueueInterface.java by Dale/Joyce/Weems Chapter 5

//

// Interface for a class that implements a queue of T with a bound

// on the size of the queue. A queue is a "first in, first out" structure.

//----------------------------------------------------------------------------

package ch05.queues;

public interface BoundedQueueInterface extends QueueInterface

{

void enqueue(T element) throws QueueOverflowException;

// Throws QueueOverflowException if this queue is full;

// otherwise, adds element to the rear of this queue.

boolean isFull();

// Returns true if this queue is full; otherwise, returns false.

}

GlassQueue.java

//---------------------------------------------------------------------------

// GlassQueue.java by Dale/Joyce/Weems Chapter 5

//

// Extends ArrayUnbndQueue with operations to determine the size of the queue

// and to access the front and rear queue elements without removing them.

//---------------------------------------------------------------------------

package ch05.queues;

public class GlassQueue extends ArrayUnbndQueue

{

public GlassQueue()

{

super();

}

public GlassQueue(int origCap)

{

super(origCap);

}

public int size()

// Returns the number of elements in this queue.

{

return numElements;

}

public T peekFront()

// Returns the object at the front of this queue.

// If the queue is empty, returns null.

{

return queue[front];

}

public T peekRear()

// Returns the object at the rear of this queue.

// If the queue is empty, returns null.

{

return queue[rear];

}

}

LinkedUnbndQueue.java

//---------------------------------------------------------------------------

// LinkedUnbndQueue.java by Dale/Joyce/Weems Chapter 5

//

// Implements UnboundedQueueInterface using a linked list

//---------------------------------------------------------------------------

package ch05.queues;

import support.LLNode;

public class LinkedUnbndQueue implements UnboundedQueueInterface

{

protected LLNode front; // reference to the front of this queue

protected LLNode rear; // reference to the rear of this queue

public LinkedUnbndQueue()

{

front = null;

rear = null;

}

public void enqueue(T element)

// Adds element to the rear of this queue.

{

LLNode newNode = new LLNode(element);

if (rear == null)

front = newNode;

else

rear.setLink(newNode);

rear = newNode;

}

public T dequeue()

// Throws QueueUnderflowException if this queue is empty;

// otherwise, removes front element from this queue and returns it.

{

if (isEmpty())

throw new QueueUnderflowException("Dequeue attempted on empty queue.");

else

{

T element;

element = front.getInfo();

front = front.getLink();

if (front == null)

rear = null;

return element;

}

}

public boolean isEmpty()

// Returns true if this queue is empty; otherwise, returns false.

{

if (front == null)

return true;

else

return false;

}

}

QueueInterface.java

//----------------------------------------------------------------------------

// QueueInterface.java by Dale/Joyce/Weems Chapter 5

//

// Interface for a class that implements a queue of T.

// A queue is a "first in, first out" structure.

//----------------------------------------------------------------------------

package ch05.queues;

public interface QueueInterface

{

T dequeue() throws QueueUnderflowException;

// Throws QueueUnderflowException if this queue is empty;

// otherwise, removes front element from this queue and returns it.

boolean isEmpty();

// Returns true if this queue is empty; otherwise, returns false.

}

QueueOverflowException.java

package ch05.queues;

public class QueueOverflowException extends RuntimeException

{

public QueueOverflowException()

{

super();

}

public QueueOverflowException(String message)

{

super(message);

}

}

QueueUnderflowException.java

package ch05.queues;

public class QueueUnderflowException extends RuntimeException

{

public QueueUnderflowException()

{

super();

}

public QueueUnderflowException(String message)

{

super(message);

}

}

SyncArrayBndQueue.java

//---------------------------------------------------------------------------

// SyncArrayBndQueue.java by Dale/Joyce/Weems Chapter 5

//

// Implements BoundedQueueInterface with an array to hold the queue elements.

// Operations are synchronized to allow concurrent access.

//

// Two constructors are provided: one that creates a queue of a default

// capacity and one that allows the calling program to specify the capacity.

//---------------------------------------------------------------------------

package ch05.queues;

public class SyncArrayBndQueue implements BoundedQueueInterface

{

protected final int DEFCAP = 100; // default capacity

protected T[] queue; // array that holds queue elements

protected int numElements = 0; // number of elements n the queue

protected int front = 0; // index of front of queue

protected int rear; // index of rear of queue

public SyncArrayBndQueue()

{

queue = (T[]) new Object[DEFCAP];

rear = DEFCAP - 1;

}

public SyncArrayBndQueue(int maxSize)

{

queue = (T[]) new Object[maxSize];

rear = maxSize - 1;

}

public synchronized void enqueue(T element)

// Throws QueueOverflowException if this queue is full;

// otherwise, adds element to the rear of this queue.

{

if (isFull())

throw new QueueOverflowException("Enqueue attempted on a full queue.");

else

{

rear = (rear + 1) % queue.length;

queue[rear] = element;

numElements = numElements + 1;

}

}

public synchronized T dequeue()

// Throws QueueUnderflowException if this queue is empty;

// otherwise, removes front element from this queue and returns it.

{

if (isEmpty())

throw new QueueUnderflowException("Dequeue attempted on empty queue.");

else

{

T toReturn = queue[front];

queue[front] = null;

front = (front + 1) % queue.length;

numElements = numElements - 1;

return toReturn;

}

}

public synchronized boolean isEmpty()

// Returns true if this queue is empty; otherwise, returns false

{

return (numElements == 0);

}

public synchronized boolean isFull()

// Returns true if this queue is full; otherwise, returns false.

{

return (numElements == queue.length);

}

}

UnboundedQueueInterface.java

//----------------------------------------------------------------------------

// UnboundedQueueInterface.java by Dale/Joyce/Weems Chapter 5

//

// Interface for a class that implements a queue of T with no bound

// on the size of the queue. A queue is a "first in, first out" structure.

//----------------------------------------------------------------------------

package ch05.queues;

public interface UnboundedQueueInterface extends QueueInterface

{

void enqueue(T element);

// Adds element to the rear of this queue.

}