Question
Please help me implement size(), height(), getHeight(), and toString() for a binary tree. Method headers must remain the same. BinaryTreeNode.java is also included below. import
Please help me implement size(), height(), getHeight(), and toString() for a binary tree. Method headers must remain the same. BinaryTreeNode.java is also included below.
import java.util.*;
/**
* LinkedBinaryTree implements the BinaryTreeADT interface
*
* @author Lewis and Chase
* @version 4.0
*/
public class LinkedBinaryTree implements BinaryTreeADT, Iterable
{
protected BinaryTreeNode root;
protected int modCount;
/**
* Creates an empty binary tree.
*/
public LinkedBinaryTree()
{
root = null;
}
/**
* Creates a binary tree with the specified element as its root.
*
* @param element the element that will become the root of the binary tree
*/
public LinkedBinaryTree(T element)
{
root = new BinaryTreeNode<>(element);
}
/**
* Creates a binary tree with the specified element as its root and the
* given trees as its left child and right child
*
* @param element the element that will become the root of the binary tree
* @param left the left subtree of this tree
* @param right the right subtree of this tree
*/
public LinkedBinaryTree(T element, LinkedBinaryTree left,
LinkedBinaryTree right)
{
root = new BinaryTreeNode<>(element);
root.setLeft(left.root);
root.setRight(right.root);
}
/**
* Returns a reference to the element at the root
*
* @return a reference to the specified target
* @throws EmptyCollectionException if the tree is empty
*/
@Override
public T getRootElement() throws EmptyCollectionException
{
if(isEmpty())
throw new EmptyCollectionException("LinkedBinaryTree");
return root.getElement();
}
/**
* Returns a reference to the node at the root
*
* @return a reference to the specified node
* @throws EmptyCollectionException if the tree is empty
*/
protected BinaryTreeNode getRootNode() throws EmptyCollectionException
{
if(isEmpty())
throw new EmptyCollectionException("LinkedBinaryTree");
return root;
}
/**
* Returns the left subtree of the root of this tree.
*
* @return a link to the left subtree for the tree
*/
public LinkedBinaryTree getLeft()
{
LinkedBinaryTree leftTree = new LinkedBinaryTree<>();
leftTree.root = root.getLeft();
return leftTree;
}
/**
* Returns the right subtree of the root of this tree.
*
* @return a link to the right subtree of the tree
*/
public LinkedBinaryTree getRight()
{
LinkedBinaryTree rightTree = new LinkedBinaryTree<>();
rightTree.root = root.getRight();
return rightTree;
}
/**
* Returns true if this binary tree is empty and false otherwise.
*
* @return true if this binary tree is empty, false otherwise
*/
@Override
public boolean isEmpty()
{
return (root == null);
}
/**
* Returns the integer size of this tree.
*
* @return the integer size of the tree
*/
@Override
public int size()
{
// TODO: Implement this
}
/**
* Returns the height of this tree.
*
* @return the height of the tree
*/
public int getHeight()
{
// TODO: Implement this
}
/**
* Returns the height of the specified node.
*
* @param node the node from which to calculate the height
* @return the height of the tree
*/
private int height(BinaryTreeNode node)
{
// TODO: Implement this.
}
/**
* Returns true if this tree contains an element that matches the
* specified target element and false otherwise.
*
* @param targetElement the element being sought in this tree
* @return true if the element in is this tree, false otherwise
*/
@Override
public boolean contains(T targetElement)
{
return (targetElement == find(targetElement));
}
/**
* Returns a reference to the specified target element if it is
* found in this binary tree. Throws a ElementNotFoundException if
* the specified target element is not found in the binary tree.
*
* @param targetElement the element being sought in this tree
* @return a reference to the specified target
* @throws ElementNotFoundException if the element is not in the tree
*/
public T find(T targetElement) throws ElementNotFoundException
{
BinaryTreeNode current = findNode(targetElement, root);
if (current == null)
throw new ElementNotFoundException("LinkedBinaryTree");
return (current.getElement());
}
/**
* Returns a reference to the specified target element if it is
* found in this binary tree.
*
* @param targetElement the element being sought in this tree
* @param next the element to begin searching from
*/
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;
}
/**
* Returns a string representation of this binary tree showing
* the nodes in an inorder fashion. Each element will be
* separated by a space.
*
* @return a string representation of this binary tree
*/
@Override
public String toString()
{
// TODO: Implement this.
}
/**
* Returns an iterator over the elements in this tree using the
* iteratorInOrder method
*
* @return an in order iterator over this binary tree
*/
@Override
public Iterator iterator()
{
return iteratorInOrder();
}
/**
* Performs an inorder traversal on this binary tree by calling an
* overloaded, recursive inorder method that starts with
* the root.
*
* @return an in order iterator over this binary tree
*/
@Override
public Iterator iteratorInOrder()
{
ArrayUnorderedList tempList = new ArrayUnorderedList<>();
inOrder(root, tempList);
return new TreeIterator(tempList.iterator());
}
/**
* Performs a recursive inorder traversal.
*
* @param node the node to be used as the root for this traversal
* @param tempList the temporary list for use in this traversal
*/
protected void inOrder(BinaryTreeNode node,
ArrayUnorderedList tempList)
{
if (node != null)
{
inOrder(node.getLeft(), tempList);
tempList.addToRear(node.getElement());
inOrder(node.getRight(), tempList);
}
}
/**
* Performs an preorder traversal on this binary tree by calling
* an overloaded, recursive preorder method that starts with
* the root.
*
* @return a pre order iterator over this tree
*/
@Override
public Iterator iteratorPreOrder()
{
ArrayUnorderedList tempList = new ArrayUnorderedList<>();
preOrder(root, tempList);
return new TreeIterator(tempList.iterator());
}
/**
* Performs a recursive preorder traversal.
*
* @param node the node to be used as the root for this traversal
* @param tempList the temporary list for use in this traversal
*/
protected void preOrder(BinaryTreeNode node,
ArrayUnorderedList tempList)
{
if(node != null)
{
tempList.addToRear(node.getElement());
preOrder(node.getLeft(), tempList);
preOrder(node.getRight(), tempList);
}
}
/**
* Performs an postorder traversal on this binary tree by calling
* an overloaded, recursive postorder method that starts
* with the root.
*
* @return a post order iterator over this tree
*/
@Override
public Iterator iteratorPostOrder()
{
throw new UnsupportedOperationException("preOrder");
}
/**
* Performs a recursive postorder traversal.
*
* @param node the node to be used as the root for this traversal
* @param tempList the temporary list for use in this traversal
*/
protected void postOrder(BinaryTreeNode node,
ArrayUnorderedList tempList)
{
//Not required.
}
/**
* Performs a levelorder traversal on this binary tree, using a
* templist.
*
* @return a levelorder iterator over this binary tree
*/
@Override
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());
}
/**
* Inner class to represent an iterator over the elements of this tree
*/
private class TreeIterator implements Iterator
{
private int expectedModCount;
private Iterator iter;
/**
* Sets up this iterator using the specified iterator.
*
* @param iter the list iterator created by a tree traversal
*/
public TreeIterator(Iterator iter)
{
this.iter = iter;
expectedModCount = modCount;
}
/**
* Returns true if this iterator has at least one more element
* to deliver in the iteration.
*
* @return true if this iterator has at least one more element to deliver
* in the iteration
* @throws ConcurrentModificationException if the collection has changed
* while the iterator is in use
*/
@Override
public boolean hasNext() throws ConcurrentModificationException
{
if (!(modCount == expectedModCount))
throw new ConcurrentModificationException();
return (iter.hasNext());
}
/**
* Returns the next element in the iteration. If there are no
* more elements in this iteration, a NoSuchElementException is
* thrown.
*
* @return the next element in the iteration
* @throws NoSuchElementException if the iterator is empty
*/
@Override
public T next() throws NoSuchElementException
{
if (hasNext())
return (iter.next());
else
throw new NoSuchElementException();
}
/**
* The remove operation is not supported.
*
* @throws UnsupportedOperationException if the remove operation is called
*/
@Override
public void remove()
{
throw new UnsupportedOperationException();
}
}
}
/** * BinaryTreeNode represents a node in a binary tree with a left and * right child. * * @author Lewis and Chase * @version 4.0 */ public class BinaryTreeNode
/** * Creates a new tree node with the specified data. * * @param obj the element that will become a part of the new tree node */ public BinaryTreeNode(T obj) { element = obj; left = null; right = null; }
/** * Creates a new tree node with the specified data. * * @param obj the element that will become a part of the new tree node * @param left the tree that will be the left subtree of this node * @param right the tree that will be the right subtree of this node */ public BinaryTreeNode(T obj, LinkedBinaryTree
if (left != null) children = 1 + left.numChildren();
if (right != null) children = children + 1 + right.numChildren();
return children; } /** * Return the element at this node. * * @return the element stored at this node */ public T getElement() { return element; } /** * Return the right child of this node. * * @return the right child of this node */ public BinaryTreeNode
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
Data Visualization A Practical Introduction
Authors: Kieran Healy
1st Edition
0691181624, 978-0691181622
