QUESTION
package jsjf;
import java.util.*;
import jsjf.exceptions.*;
public class LinkedBinaryTree implements BinaryTreeADT,
Iterable
{
protected BinaryTreeNode root;
protected int modCount;
public LinkedBinaryTree()
{
root = null;
}
public LinkedBinaryTree(T element)
{
root = new
BinaryTreeNode(element);
}
public LinkedBinaryTree(T element, LinkedBinaryTree
left,
LinkedBinaryTree
right)
{
root = new
BinaryTreeNode(element);
root.setLeft(left.root);
root.setRight(right.root);
}
public T getRootElement() throws
EmptyCollectionException
{
// To be completed as a Programming
Project
return null; // temp
}
protected BinaryTreeNode getRootNode() throws
EmptyCollectionException
{
// To be completed as a Programming
Project
return null; // temp
}
public LinkedBinaryTree getLeft()
{
// To be completed as a Programming
Project
return null; // temp
}
public LinkedBinaryTree getRight()
{
// To be completed as a Programming
Project
return null; // temp
}
public boolean isEmpty()
{
return (root == null);
}
public int size()
{
// To be completed as a Programming
Project
return 0; // temp
}
public int getHeight()
{
// To be completed as a Programming
Project
return 0; // temp
}
private int height(BinaryTreeNode node)
{
// To be completed as a Programming
Project
return 0; // temp
}
public boolean contains(T targetElement)
{
// To be completed as a Programming
Project
return true; // temp
}
public T find(T targetElement) throws
ElementNotFoundException
{
BinaryTreeNode current =
findNode(targetElement, root);
if (current == null)
throw new
ElementNotFoundException("LinkedBinaryTree");
return
(current.getElement());
}
private BinaryTreeNode findNode(T
targetElement,
BinaryTreeNode
next)
{
if (next == null)
return null;
if
(next.getElement().equals(targetElement))
return next;
BinaryTreeNode temp = findNode(targetElement, next.getLeft());
if (temp == null)
temp =
findNode(targetElement, next.getRight());
return temp;
}
public String toString()
{
// To be completed as a Programming
Project
return ""; // temp
}
public Iterator iterator()
{
return iteratorInOrder();
}
public Iterator iteratorInOrder()
{
ArrayUnorderedList tempList = new
ArrayUnorderedList();
inOrder(root, tempList);
return new
TreeIterator(tempList.iterator());
}
protected void inOrder(BinaryTreeNode node,
ArrayUnorderedList tempList)
{
if (node != null)
{
inOrder(node.getLeft(), tempList);
tempList.addToRear(node.getElement());
inOrder(node.getRight(), tempList);
}
}
public Iterator iteratorPreOrder()
{
// To be completed as a Programming
Project
return null; // temp
}
protected void preOrder(BinaryTreeNode node,
ArrayUnorderedList tempList)
{
// To be completed as a Programming
Project
}
public Iterator iteratorPostOrder()
{
// To be completed as a Programming
Project
return null; // temp
}
protected void postOrder(BinaryTreeNode node,
ArrayUnorderedList tempList)
{
// To be completed as a Programming
Project
}
public Iterator iteratorLevelOrder()
{
ArrayUnorderedList> nodes
=
new ArrayUnorderedList>();
ArrayUnorderedList tempList = new
ArrayUnorderedList();
BinaryTreeNode current;
nodes.addToRear(root);
while (!nodes.isEmpty())
{
current =
nodes.removeFirst();
if (current
!= null)
{
tempList.addToRear(current.getElement());
if (current.getLeft() != null)
nodes.addToRear(current.getLeft());
if (current.getRight() != null)
nodes.addToRear(current.getRight());
}
else
tempList.addToRear(null);
}
return new
TreeIterator(tempList.iterator());
}
private class TreeIterator implements Iterator
{
private int expectedModCount;
private Iterator iter;
public TreeIterator(Iterator
iter)
{
this.iter =
iter;
expectedModCount
= modCount;
}
public boolean hasNext() throws
ConcurrentModificationException
{
if (!(modCount
== expectedModCount))
throw new ConcurrentModificationException();
return
(iter.hasNext());
}
public T next() throws
NoSuchElementException
{
if
(hasNext())
return (iter.next());
else
throw new NoSuchElementException();
}
public void remove()
{
throw new
UnsupportedOperationException();
}
}
}
Complete all missing methods in LinkedBinarySearchTree. Show test cases for all implemented methods being sure to include edge cases for methods where applicable.
Then, implement a balance tree method for this class using the brute force method.
Show test cases for two different degenerate trees, outputting the height of the tree before and after balancing the tree. Then, demonstrate insertions into a balanced tree that result in degenerate trees and rebalance the tree again.Hint: Copy the elements into an ArrayList using an in-order traversal. Recursively build a balanced tree using a binary partitioning.
Public Answer
