Using JAVA. You have been given a partially implemented binary search tree class and a binary search
Question:
Using JAVA. You have been given a partially implemented binary search tree class and a binary search tree node class to use. Your task is to implement the following methods in the binary search tree class BinTree according to the given specification:
BinTreeNode<T> clone()
This function should create a new binary tree (with its own nodes) that is a clone of the original binary search tree. This function should return the root node of the new binary tree.
Note: Make sure you don’t make any changes to the original tree.
BinTreeNode<T> mirror()
This function should create a new binary tree (with its own nodes) that is the mirror image across the vertical axis of the original binary search tree. This function should return the root node of the new binary tree. Note: Make sure you don’t make any changes to the original tree.
void printPreorder()
This function should print out all the elements in the binary search tree as a space separated list that is terminated by a newline. This function should use the pre-order tree traversal strategy.
boolean deleteByMerge(T elem)
This function should delete the given elem from the binary search tree. It returns true if elem is removed successfully and false otherwise. This function should use the delete by merging strategy.
Given Code:
////////BinTreeNode.java//////////
public class BinTreeNode<T extends Comparable<? super T>> {
protected T element;
protected BinTreeNode<T> left, right;
public BinTreeNode() {
left = right = null;
}
public BinTreeNode(T el) {
this(el,null,null);
}
public BinTreeNode(T el, BinTreeNode<T> lt, BinTreeNode<T> rt) {
this.element = el; left = lt; right = rt;
}
public String toString() {
String out = element.toString();
out += " [L: "+ (left == null ? null : left.element) + "] ";
out += " [R: "+ (right == null ? null : right.element) + "] ";
return out;
}
}
////////BinTree.java//////////
@SuppressWarnings("unchecked")
public class BinTree<T extends Comparable<? super T>> {
protected BinTreeNode<T> root = null;
protected static int count = 0;
public BinTree() {}
public void clear(){
root = null;
}
public String inorder(BinTreeNode<T> node)
{
boolean verbose = true;
if (node != null) {
String result = "";
result += inorder(node.left);
if (verbose) {
result += node.toString()+"";
} else {
result += node.element.toString() + " ";
}
result += inorder(node.right);
return result;
}
return "";
}
public boolean isEmpty()
{
return (root == null);
}
public void insert(T element)
{
BinTreeNode<T> nodePtr = root,prevNode = null;
while(nodePtr != null){
prevNode = nodePtr;
if(nodePtr.element.compareTo(element) > 0)
nodePtr = nodePtr.left;
else
nodePtr = nodePtr.right;
}
if(isEmpty())
root = new BinTreeNode<T>(element);
else if(prevNode.element.compareTo(element) > 0)
prevNode.left = new BinTreeNode<T>(element);
else
prevNode.right = new BinTreeNode<T>(element);
}
public T search(T element)
{
//Your code goes here
BinTreeNode<T> nodePtr = root;
while(nodePtr != null){
if(nodePtr.element == element)
return nodePtr.element;
else if(nodePtr.element.compareTo(element) > 0)
nodePtr = nodePtr.left;
else
nodePtr = nodePtr.right;
}
return null;
}
////// You may not change any code above this line //////
////// Implement the functions below this line //////
Accounting Business Reporting for Decision Making
ISBN: 9780730302414
4th edition
Authors: Jacqueline Birt, Keryn Chalmers, Albie Brooks, Suzanne Byrne, Judy Oliver