Please help with this JAVA c ode. Thank you! Complete the implementation of Link
ID: 3920214 • Letter: P
Question
Please help with this JAVA code. Thank you!
Complete the implementation of LinkedBinaryTree. Speci cally, implement these methods: get- RootElement(), getRootNode(), getLeft(), getRight(), size(), getHeight(), height(), contains(), toString(), and iteratorPreOrder(). Review the comments in LinkedBinaryTree and BinaryTreeADT for imple- mentation requirements. [12 points]
import java.util.*;
/**
* LinkedBinaryTree implements the BinaryTreeADT interface
*
* @author Lewis and Chase
* @version 4.0
*/
public class LinkedBinaryTree<T> implements BinaryTreeADT<T>, Iterable<T>
{
protected BinaryTreeNode<T> 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<T> left,
LinkedBinaryTree<T> 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
{
// TODO: Implement this.
}
/**
* 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<T> getRootNode() throws EmptyCollectionException
{
// TODO: Implement this.
}
/**
* Returns the left subtree of the root of this tree.
*
* @return a link to the left subtree fo the tree
*/
public LinkedBinaryTree<T> getLeft()
{
// TODO: Implement this.
}
/**
* Returns the right subtree of the root of this tree.
*
* @return a link to the right subtree of the tree
*/
public LinkedBinaryTree<T> getRight()
{
// TODO: Implement this.
}
/**
* 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<T> 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)
{
// TODO: Implement this.
}
/**
* 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<T> 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<T> findNode(T targetElement,
BinaryTreeNode<T> next)
{
if (next == null)
return null;
if (next.getElement().equals(targetElement))
return next;
BinaryTreeNode<T> 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<T> 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<T> iteratorInOrder()
{
ArrayUnorderedList<T> 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<T> node,
ArrayUnorderedList<T> 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<T> iteratorPreOrder()
{
//TODO: Implement this.
}
/**
* 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<T> node,
ArrayUnorderedList<T> tempList)
{
//TODO: Implement this.
}
/**
* 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<T> 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<T> node,
ArrayUnorderedList<T> 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<T> iteratorLevelOrder()
{
ArrayUnorderedList<BinaryTreeNode<T>> nodes = new ArrayUnorderedList<>();
ArrayUnorderedList<T> tempList = new ArrayUnorderedList<>();
BinaryTreeNode<T> 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<T>
{
private int expectedModCount;
private Iterator<T> iter;
/**
* Sets up this iterator using the specified iterator.
*
* @param iter the list iterator created by a tree traversal
*/
public TreeIterator(Iterator<T> 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();
}
}
}
Explanation / Answer
Program:
/* Class BSTNode */
class BSTNode
{
BSTNode left, right;
int data;
/* Constructor */
public BSTNode()
{
left = null;
right = null;
data = 0;
}
/* Constructor */
public BSTNode(int n)
{
left = null;
right = null;
data = n;
}
/* Function to set left node */
public void setLeft(BSTNode n)
{
left = n;
}
/* Function to set right node */
public void setRight(BSTNode n)
{
right = n;
}
/* Function to get left node */
public BSTNode getLeft()
{
return left;
}
/* Function to get right node */
public BSTNode getRight()
{
return right;
}
/* Function to set data to node */
public void setData(int d)
{
data = d;
}
/* Function to get data from node */
public int getData()
{
return data;
}
}
/* Class BST */
class BST
{
private BSTNode root;
/* Constructor */
public BST()
{
root = null;
}
/* Function to check if tree is empty */
public boolean isEmpty()
{
return root == null;
}
/* Functions to insert data */
public void insert(int data)
{
root = insert(root, data);
}
/* Function to insert data recursively */
private BSTNode insert(BSTNode node, int data)
{
if (node == null)
node = new BSTNode(data);
else
{
if (data <= node.getData())
node.left = insert(node.left, data);
else
node.right = insert(node.right, data);
}
return node;
}
/* Functions to delete data */
public void delete(int k)
{
if (isEmpty())
System.out.println("Tree Empty");
else if (search(k) == false)
System.out.println("Sorry "+ k +" is not present");
else
{
root = delete(root, k);
System.out.println(k+ " deleted from the tree");
}
}
private BSTNode delete(BSTNode root, int k)
{
BSTNode p, p2, n;
if (root.getData() == k)
{
BSTNode lt, rt;
lt = root.getLeft();
rt = root.getRight();
if (lt == null && rt == null)
return null;
else if (lt == null)
{
p = rt;
return p;
}
else if (rt == null)
{
p = lt;
return p;
}
else
{
p2 = rt;
p = rt;
while (p.getLeft() != null)
p = p.getLeft();
p.setLeft(lt);
return p2;
}
}
if (k < root.getData())
{
n = delete(root.getLeft(), k);
root.setLeft(n);
}
else
{
n = delete(root.getRight(), k);
root.setRight(n);
}
return root;
}
/* Functions to count number of nodes */
public int countNodes()
{
return countNodes(root);
}
/* Function to count number of nodes recursively */
private int countNodes(BSTNode r)
{
if (r == null)
return 0;
else
{
int l = 1;
l += countNodes(r.getLeft());
l += countNodes(r.getRight());
return l;
}
}
/* Functions to search for an element */
public boolean search(int val)
{
return search(root, val);
}
/* Function to search for an element recursively */
private boolean search(BSTNode r, int val)
{
boolean found = false;
while ((r != null) && !found)
{
int rval = r.getData();
if (val < rval)
r = r.getLeft();
else if (val > rval)
r = r.getRight();
else
{
found = true;
break;
}
found = search(r, val);
}
return found;
}
/* Function for inorder traversal */
public void inorder()
{
inorder(root);
}
private void inorder(BSTNode r)
{
if (r != null)
{
inorder(r.getLeft());
System.out.print(r.getData() +" ");
inorder(r.getRight());
}
}
/* Function for preorder traversal */
public void preorder()
{
preorder(root);
}
private void preorder(BSTNode r)
{
if (r != null)
{
System.out.print(r.getData() +" ");
preorder(r.getLeft());
preorder(r.getRight());
}
}
/* Function for postorder traversal */
public void postorder()
{
postorder(root);
}
private void postorder(BSTNode r)
{
if (r != null)
{
postorder(r.getLeft());
postorder(r.getRight());
System.out.print(r.getData() +" ");
}
}
}
/* Class BinarySearchTree */
public class BinarySearchTree
{
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
/* Creating object of BST */
BST bst = new BST();
System.out.println("Binary Search Tree Test ");
char ch;
/* Perform tree operations */
do
{
System.out.println(" Binary Search Tree Operations ");
System.out.println("1. insert ");
System.out.println("2. delete");
System.out.println("3. search");
System.out.println("4. count nodes");
System.out.println("5. check empty");
int choice = scan.nextInt();
switch (choice)
{
case 1 :
System.out.println("Enter integer element to insert");
bst.insert( scan.nextInt() );
break;
case 2 :
System.out.println("Enter integer element to delete");
bst.delete( scan.nextInt() );
break;
case 3 :
System.out.println("Enter integer element to search");
System.out.println("Search result : "+ bst.search( scan.nextInt() ));
break;
case 4 :
System.out.println("Nodes = "+ bst.countNodes());
break;
case 5 :
System.out.println("Empty status = "+ bst.isEmpty());
break;
default :
System.out.println("Wrong Entry ");
break;
}
/* Display tree */
System.out.print(" Post order : ");
bst.postorder();
System.out.print(" Pre order : ");
bst.preorder();
System.out.print(" In order : ");
bst.inorder();
System.out.println(" Do you want to continue (Type y or n) ");
ch = scan.next().charAt(0);
} while (ch == 'Y'|| ch == 'y');
}
}