1) Extend the Binary Search Tree ADT to include a public method leafCount that returns the number of leaf nodes in the tree.

2) 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.

3) The Binary Search Tree ADT is extended to include a boolean method similarTrees that receives references to two binary trees and determines whether the shapes of the trees are the same. (The nodes do not have to contain the same values, but each node must have the same number of children.)

a) Write the declaration of the similarTrees method. Include adequate comments.

b) Write the body of the similarTrees method.

I am sure you will not need all of these but i was not sure which ones were necesarry. thank you I believe all of these questions go hand in hand

BinarySearchTree.java

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

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

}