To create a node for a binary search tree BTNode and to cre

To create a node for a binary search tree (BTNode, ) and to create a binary search tree of comparable objects (Tree BTNode BTNode -data:E -left: BTNode -right: BTNode +BTNode (newData:E, newLeft: BTNode, newRight: BTNode) +getData():E +getLeft():BTNode +getRight():BTNode +getRightMostData():E +inOrderPrint():void +removeRightmost(): BTNode +setData(newData:E):void +setLeft(newleft: BTNode):void +setRight(newRight: BTNode):void needed for remove needed for remove Tree for Lab 7 Tree -root: 8TNode -numltems:int +Tree() +add(element:E):void +remove(element:E):boolean + remove +size():int + printTree():void

Solution

//BTNode.java
public class BTNode<E>
{
private E data;
private BTNode<E> left;
private BTNode<E> right;

public BTNode(E newData, BTNode<E> newLeft, BTNode<E> newRight)
{
data = newData;
left = newLeft;
right = newRight;
}//end constructor
  
/**
* Returns the data
* @return The data
*/
public E getData()
{
return data;
}//end getData
  
/**
* Returns the left link
* @return the left link
*/
public BTNode<E> getLeft()
{
return left;
}//end getLeft
  
/**
* Returns the right link
* @return the right link
*/
public BTNode<E> getRight()
{
return right;
}//end getRight
  
/**
* Prints the tree in order from left to right.
*/
public void inOrderPrint()
{
if (left != null){
left.inOrderPrint();
}//end left
  
System.out.println(data);
  
if(right != null){
right.inOrderPrint();
}//end right
  
}//end inOrderPrint
  
/**
* Sets the data in the node
* @param newData The new data to be passed
*/
public void setData(E newData)
{
data = newData;
}//end setData
  
/**
* Sets a new link to left
* @param newLeft the new link to go left
*/
public void setLeft(BTNode<E> newLeft)
{
left = newLeft;
}//end setLeft
  
/**
* Sets a new link to the right
* @param newRight the new link to the right
*/
public void setRight(BTNode<E> newRight)
{
right = newRight;
}//end setRight
  
public E getRightMostData()
{
if(right == null){
return data;
} else {
return right.getRightMostData();
}//end right == null if-else
}//end getRightMostData
  
public BTNode<E> removeRightmost()
{
if (right == null){
return left;
} else {
right = right.removeRightmost();
return this;
}//end if right == null if=-else
}//end removeRightMost
}//end BTNode

=======================================================================

//Tree.java

public class Tree<E extends Comparable<E>>
{
private BTNode<E> root;
private int numItems;
  
/**
* No-arg constructor
*/
public Tree()
{
root = null;
numItems = 0;
}//end constructor
  

public void add(E element)
{
if (root == null) {
root = new BTNode<E>(element, null, null);
}else{
BTNode<E> cursor = root;
boolean done = false;
  
while(!done){
if (element.compareTo(cursor.getData()) <= 0){//cursor.getData().compareTo(element) > 0){
if (cursor.getLeft() == null) {
cursor.setLeft(new BTNode<E>(element,null,null));
done = true;
} else {
cursor = cursor.getLeft();
} //end left is null if-else
}else{
if(cursor.getRight() == null){
cursor.setRight(new BTNode(element, null, null));
done = true;
}else{
cursor = cursor.getRight();
}//end cursor.getRight if-else
}//end compareto if-else
}//end while
}//end root ==null if-else
numItems++;
}//end add
  
/**
* Get the number of elements in the tree
* @return The size of the tree
*/
public int size()
{
return numItems;
}//end size
  
/**
* Print the tree in order
*/
public void printTree()
{
if (root == null){
System.out.println(\"This tree is empty\");
}else{
root.inOrderPrint();
}//end if-else
}//end inOrderPrint
  
public boolean remove(E target)
{
BTNode<E> cursor = root;
BTNode<E> parentOfCursor = null;
boolean found = false;
  
while (cursor != null && !found){
if (target.equals(cursor.getData())){
found = true;
}else{
if(target.compareTo(cursor.getData()) <= 0){
parentOfCursor = cursor;
cursor = cursor.getLeft();
}else{
parentOfCursor = cursor;
cursor = cursor.getRight();
}//end target.compareTo if-else
}//end target.equals if-else
}//end cursor && found while
  
if (cursor != null){
if (cursor.getLeft() == null && cursor == root){
root = root.getRight();
} else if (cursor.getLeft() == null && cursor!= root){
if (cursor == parentOfCursor.getLeft()){
parentOfCursor.setLeft(cursor.getRight());
} else {
parentOfCursor.setRight(cursor.getRight());
}//end cursor ==parentOfCursor.setLEft if-else
} else{
cursor.setData(cursor.getLeft().getRightMostData());
cursor.setLeft(cursor.getLeft().removeRightmost());
} //end cursor == root if-else
}//end found if
return found;
}
}//end Tree