Objective : -additions to BTNode and Tree for remove( ) UML BTNode<E> for Lab 06
ID: 3692684 • Letter: O
Question
Objective:
-additions to BTNode and Tree for remove( )
UML
BTNode<E> for Lab 06
BTNode<E>
-data:E
-left: BTNode<E>
-right: BTNode<E>
+BTNode ( newData:E, newLeft: BTNode<E>, newRight: BTNode<E>)
+getData():E
+getLeft():BTNode<E>
+getRight():BTNode<E>
+getRightMostData():E
+inOrderPrint():void <- code is on slides
+removeRightmost(): BTNode<E>
+setData(newData:E):void
+setLeft(newLeft: BTNode<E>):void
+setRight(newRight: BTNode<E>):void
Tree<E> for Lab 6
Tree<E>
-root: BTNode<E>
-numItems:int
+Tree()
+add(element:E):void
+remove(element:E):boolean
+size():int
+inOrderPrint():void <- calls root. inOrderPrint() if root is not null
NOTE: you will need to extend Comparable for the .compareTo() to work
public class Tree<E extends Comparable<E>>
Explanation / Answer
TreeTester.java
import java.util.Scanner;
public class TreeTester
{
public static void main(String[] args)
{
Scanner input = new Scanner(System.in);
String userSelection;
do
{
System.out.println(" =======================================");
System.out.println("I - Tree of Integer");
System.out.print(" Enter Choice: (Q to quit): ");
userSelection = input.nextLine();
switch (userSelection.toLowerCase())
{
case"i":
System.out.println(" ===================INTEGER====================");
TestTreeWithInteger.runMe();
break;
case "q":
System.out.println(" ===================QUIT====================");
System.out.println(" bye bye!");
break;
default:
System.out.println(" huh?");
}
} while ( !(userSelection.equalsIgnoreCase("Q")) );
}
}
BTNode.java
package lab0809treetester;
public class BTNode<E>
{
private E data;
private BTNode<E> left;
private BTNode<E> right;
/**
* No arg constructor
* @param newData The data for the node
* @param newLeft link to the left node
* @param newRight link to the right node
*/
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
/**
* Adds a new element to the tree
* @param element The element to be added to the tree
*/
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
TreeWithInteger.java
public class TreeWithInteger
{
public static void main(String[] args)
{
runMe();
}
public static void runMe()
{
TestTreeGeneric<Integer> testTreeInteger = new TestTreeGeneric<Integer>();
// array for Lab 8 and Test Condition 1 for Lab 9
Integer[] lab08ArrayOfIntsToAdd = {81, 605, 71, 57, 302, 605, 201, 923};
// To Test remove() method - condition 1
// - cursor is null - target not found
// meaning: attempt to remove value not in tree
Integer testConditionOneSingleIntToDelete = 66 ;
// array for Lab 9 Test Condition 2
Integer[] lab09ArrayOfIntsToAddForCondition2 = { 15, 37, 23, 78 };
// To Test remove() method - condition 2
// node to be removed is at root and no left child
Integer testConditionTwoSingleIntToDelete = 15 ;
// array for Lab 9 Test Condition 3
Integer[] lab09ArrayOfIntsToAddForCondition3 = { 38, 11, 62, 5, 21, 7 };
// To Test remove() method - condition 3
// node removed is not at root and has no left child
Integer testConditionThreeSingleIntToDelete = 5 ;
// array for Lab 9 Test Condition 4
Integer[] lab09ArrayOfIntsToAddForCondition4 = { 38, 11, 62, 5, 21, 7 };
// To Test remove() method - condition 4
// node to be removed has a left child
// - will go left and get largest on left and bring up
Integer testConditionFourSingleIntToDelete = 38 ; // coincidentally root
testTreeInteger.test ( lab08ArrayOfIntsToAdd,
testConditionOneSingleIntToDelete );
testTreeInteger.test ( lab09ArrayOfIntsToAddForCondition2,
testConditionTwoSingleIntToDelete );
testTreeInteger.test ( lab09ArrayOfIntsToAddForCondition3,
testConditionThreeSingleIntToDelete );
testTreeInteger.test ( lab09ArrayOfIntsToAddForCondition4,
testConditionFourSingleIntToDelete );
}
}
TestTreeGeneric.java
public class TestTreeGeneric<E extends Comparable<E>>
{
public void test(E[] testDataAdd, E testDataSingleItemRemove)
{
// creates a Tree of E
Tree<E> myGenericTree = new Tree<E>();
// show initial Tree
displayTree("Display Tree/Size on startup",myGenericTree);
// add some stuff to the Tree
System.out.println(" =========== <<Start adds:");
for (E item : testDataAdd)
{
System.out.print("Adding: " + item);
myGenericTree.add(item);
System.out.println(" added...now size is " + myGenericTree.size());
}
System.out.println("Stopped adding>> ===========");
// show Tree after adds
displayTree(" Display Tree/Size after adds",myGenericTree);
}
private void displayTree(String heading, Tree<E> aTree)
{
System.out.println(" " + heading);
if (aTree.size() == 0)
{
System.out.println(" Tree is empty...Tree says: ");
aTree.printTree();
}
else
{
aTree.printTree();
System.out.println("Size: " + aTree.size());
}
}
}
sample output
Terminal
=======================================
I - Tree of Integer
Enter Choice: (Q to quit): I
===================INTEGER====================
Display Tree/Size on startup
Tree is empty...Tree says:
This tree is empty
===========
<<Start adds:
Adding: 81 added...now size is 1
Adding: 605 added...now size is 2
Adding: 71 added...now size is 3
Adding: 57 added...now size is 4
Adding: 302 added...now size is 5
Adding: 605 added...now size is 6
Adding: 201 added...now size is 7
Adding: 923 added...now size is 8
Stopped adding>>
===========
Display Tree/Size after adds
57
71
81
201
302
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.