Please help with this JAVA program. Thank you! [LC PP 11.2 modi ed] The LinkedBi
ID: 3920215 • Letter: P
Question
Please help with this JAVA program. Thank you!
[LC PP 11.2 modi ed] The LinkedBinarySearchTree class is currently using the nd and contains methods of the LinkedBinaryTree class via inheritance. This is not optimal! Implement these two methods for the LinkedBinarySearchTree class, nd() and contains(), so that they will be more e cient by making use of the ordering property of a binary search tree. Notice that ve other methods in LinkedBinarySearchTree are not yet implemented: removeMax(), ndMin(), ndMax(), getLeft(), getRight(), ndNode(). If any are needed by your algorithms, implement them, otherwise you may omit them.
/**
* LinkedBinarySearchTree implements the BinarySearchTreeADT interface
* with links.
*
* @author Lewis and Chase
* @version 4.0
*/
public class LinkedBinarySearchTree<T> extends LinkedBinaryTree<T>
implements BinarySearchTreeADT<T>
{
/**
* Creates an empty binary search tree.
*/
public LinkedBinarySearchTree()
{
super();
}
/**
* Creates a binary search with the specified element as its root.
*
* @param element the element that will be the root of the new binary
* search tree
*/
public LinkedBinarySearchTree(T element)
{
super(element);
if (!(element instanceof Comparable))
throw new NonComparableElementException("LinkedBinarySearchTree");
}
/**
* Adds the specified object to the binary search tree in the
* appropriate position according to its natural order. Note that
* equal elements are added to the right.
*
* @param element the element to be added to the binary search tree
*/
@Override
public void addElement(T element)
{
if (!(element instanceof Comparable))
throw new NonComparableElementException("LinkedBinarySearchTree");
Comparable<T> comparableElement = (Comparable<T>)element;
if (isEmpty())
root = new BinaryTreeNode<T>(element);
else
{
if (comparableElement.compareTo(root.getElement()) < 0)
{
if (root.getLeft() == null)
this.getRootNode().setLeft(new BinaryTreeNode<T>(element));
else
addElement(element, root.getLeft());
}
else
{
if (root.getRight() == null)
this.getRootNode().setRight(new BinaryTreeNode<T>(element));
else
addElement(element, root.getRight());
}
}
modCount++;
}
/**
* Adds the specified object to the binary search tree in the
* appropriate position according to its natural order. Note that
* equal elements are added to the right.
*
* @param element the element to be added to the binary search tree
*/
private void addElement(T element, BinaryTreeNode<T> node)
{
Comparable<T> comparableElement = (Comparable<T>)element;
if (comparableElement.compareTo(node.getElement()) < 0)
{
if (node.getLeft() == null)
node.setLeft(new BinaryTreeNode<T>(element));
else
addElement(element, node.getLeft());
}
else
{
if (node.getRight() == null)
node.setRight(new BinaryTreeNode<T>(element));
else
addElement(element, node.getRight());
}
}
/**
* Removes the first element that matches the specified target
* element from the binary search tree and returns a reference to
* it. Throws a ElementNotFoundException if the specified target
* element is not found in the binary search tree.
*
* @param targetElement the element being sought in the binary search tree
* @throws ElementNotFoundException if the target element is not found
*/
@Override
public T removeElement(T targetElement)
throws ElementNotFoundException
{
T result = null;
if (isEmpty())
throw new ElementNotFoundException("LinkedBinarySearchTree");
else
{
BinaryTreeNode<T> parent = null;
if (((Comparable<T>)targetElement).equals(root.element))
{
result = root.element;
BinaryTreeNode<T> temp = replacement(root);
if (temp == null)
root = null;
else
{
root.element = temp.element;
root.setRight(temp.right);
root.setLeft(temp.left);
}
modCount--;
}
else
{
parent = root;
if (((Comparable)targetElement).compareTo(root.element) < 0)
result = removeElement(targetElement, root.getLeft(), parent);
else
result = removeElement(targetElement, root.getRight(), parent);
}
}
return result;
}
/**
* Removes the first element that matches the specified target
* element from the binary search tree and returns a reference to
* it. Throws a ElementNotFoundException if the specified target
* element is not found in the binary search tree.
*
* @param targetElement the element being sought in the binary search tree
* @param node the node from which to search
* @param parent the parent of the node from which to search
* @throws ElementNotFoundException if the target element is not found
*/
private T removeElement(T targetElement, BinaryTreeNode<T> node, BinaryTreeNode<T> parent)
throws ElementNotFoundException
{
T result = null;
if (node == null)
throw new ElementNotFoundException("LinkedBinarySearchTree");
else
{
if (((Comparable<T>)targetElement).equals(node.element))
{
result = node.element;
BinaryTreeNode<T> temp = replacement(node);
if (parent.right == node)
parent.right = temp;
else
parent.left = temp;
modCount--;
}
else
{
parent = node;
if (((Comparable)targetElement).compareTo(node.element) < 0)
result = removeElement(targetElement, node.getLeft(), parent);
else
result = removeElement(targetElement, node.getRight(), parent);
}
}
return result;
}
/**
* Returns a reference to a node that will replace the one
* specified for removal. In the case where the removed node has
* two children, the inorder successor is used as its replacement.
*
* @param node the node to be removed
* @return a reference to the replacing node
*/
private BinaryTreeNode<T> replacement(BinaryTreeNode<T> node)
{
BinaryTreeNode<T> result = null;
if ((node.left == null) && (node.right == null))
result = null;
else if ((node.left != null) && (node.right == null))
result = node.left;
else if ((node.left == null) && (node.right != null))
result = node.right;
else
{
BinaryTreeNode<T> current = node.right;
BinaryTreeNode<T> parent = node;
while (current.left != null)
{
parent = current;
current = current.left;
}
current.left = node.left;
if (node.right != current)
{
parent.left = current.right;
current.right = node.right;
}
result = current;
}
return result;
}
/**
* Removes elements that match the specified target element from
* the binary search tree. Throws a ElementNotFoundException if
* the specified target element is not found in this tree.
*
* @param targetElement the element being sought in the binary search tree
* @throws ElementNotFoundException if the target element is not found
*/
@Override
public void removeAllOccurrences(T targetElement)
throws ElementNotFoundException
{
removeElement(targetElement);
try
{
while (contains((T)targetElement))
removeElement(targetElement);
}
catch (Exception ElementNotFoundException)
{
}
}
/**
* Removes the node with the least value from the binary search
* tree and returns a reference to its element. Throws an
* EmptyCollectionException if this tree is empty.
*
* @return a reference to the node with the least value
* @throws EmptyCollectionException if the tree is empty
*/
@Override
public T removeMin() throws EmptyCollectionException
{
T result = null;
if (isEmpty())
throw new EmptyCollectionException("LinkedBinarySearchTree");
else
{
if (root.left == null)
{
result = root.element;
root = root.right;
}
else
{
BinaryTreeNode<T> parent = root;
BinaryTreeNode<T> current = root.left;
while (current.left != null)
{
parent = current;
current = current.left;
}
result = current.element;
parent.left = current.right;
}
modCount--;
}
return result;
}
/**
* Removes the node with the highest value from the binary
* search tree and returns a reference to its element. Throws an
* EmptyCollectionException if this tree is empty.
*
* @return a reference to the node with the highest value
* @throws EmptyCollectionException if the tree is empty
*/
@Override
public T removeMax() throws EmptyCollectionException
{
// TODO: May need to implement.
}
/**
* Returns the element with the least value in the binary search
* tree. It does not remove the node from the binary search tree.
* Throws an EmptyCollectionException if this tree is empty.
*
* @return the element with the least value
* @throws EmptyCollectionException if the tree is empty
*/
@Override
public T findMin() throws EmptyCollectionException
{
// TODO: May need to implement.
}
/**
* Returns the element with the highest value in the binary
* search tree. It does not remove the node from the binary
* search tree. Throws an EmptyCollectionException if this
* tree is empty.
*
* @return the element with the highest value
* @throws EmptyCollectionException if the tree is empty
*/
@Override
public T findMax() throws EmptyCollectionException
{
// TODO: May need to implement.
}
// TODO: Implement find.
// TODO: Implement contains.
/**
* Returns the left subtree of the root of this tree.
*
* @return a link to the left subtree fo the tree
*/
@Override
public LinkedBinarySearchTree<T> getLeft()
{
// TODO: May need to implement.
}
/**
* Returns the right subtree of the root of this tree.
*
* @return a link to the right subtree of the tree
*/
@Override
public LinkedBinarySearchTree<T> getRight()
{
// TODO: May need to implement.
}
/**
* Returns a reference to the specified target element if it is
* found in this tree.
*
* @param targetElement the element being sought in the tree
* @param next the tree node to begin searching on
*/
private BinaryTreeNode<T> findNode(T targetElement, BinaryTreeNode<T> next)
{
// TODO: May need to implement.
}
}
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');
}
}