/**
*
* BST.java
*
* Revisions: 1.0 Oct. 16, 2002
* Created the BST class
* 1.1 Oct. 16, 2002
* Compiled, Finished, Tested
* 2.0 Oct. 26, 2002
* Added code to fix problem with remove(), neither autograder
* nor me caught it until after working on
* AircraftCarrier.java
*
*
*
*
* @author Jose Manuel Caban
* @version Version 2.0, Oct. 26, 2002
*/
import java.io.*;
public class BST {
public static final boolean bDebug = false;
public BSTNode root;
///////////
//Methods//
///////////
/**
*Add data to tree
*@param data, data to add
*/
public void add(Comparable data){
if(root == null){
root = new BSTNode(data);
}
else{
add(data,root);
}
}//end add(Comparable)
/**
*Add data to tree helper
*@param data, the data to add
*@param current, the current spot on the tree
*/
private void add(Comparable data, BSTNode current){
if(current.getData().compareTo(data) > 0){
if(current.getLeft() == null){
current.setLeft(new BSTNode(data));
}
else{
add(data,current.getLeft());
}
}
else if(current.getData().compareTo(data) < 0){
if(current.getRight() == null){
current.setRight(new BSTNode(data));
}
else{
add(data,current.getRight());
}
}
else{/*do nothing*/}//current.compareTo() == 0
}//end add(Comparable,BSTNode)
/**
*Add data with Iteration
*I did this for my own enjoyment and mental enrichment
*plus those nested ?: look soooooo advanced
*/
public void addItr(Comparable data){
if(root == null){
root = new BSTNode(data);
}
if(data.compareTo(root.getData()) == 0){
return;
}
//assumes data is not already in tree
BSTNode bTraverse =
(data.compareTo(root.getData())>0?root.getRight():root.getLeft());
BSTNode bPrevTraverse = root;
while(bTraverse != null){
bPrevTraverse = bTraverse;
bTraverse =
(data.compareTo(bTraverse.getData())>0?
bTraverse.getRight():bTraverse.getLeft());
}
if(data.compareTo(bPrevTraverse.getData())>0){
bPrevTraverse.setRight(new BSTNode(data));
}
else{
bPrevTraverse.setLeft(new BSTNode(data));
}
}//end addItr(Comparable)
/**
*Check to see if data is in Tree
*@return null if not, the data if true
*/
public Comparable find(Comparable toFind){
BSTNode current = root;
for(;;){
if(current == null){
return null;
}
else if(toFind.compareTo(current.getData()) == 0){
return current.getData();
}
else if(toFind.compareTo(current.getData()) < 0){
current = current.getLeft();
}
else{
current = current.getRight();
}
}
}//end find(Comparable)
/**
*Remove a piece of data from Tree
*@param toDie, the piece of data to be removed
*/
public Comparable remove(Comparable toDie){
BSTNode bLocation = root;
BSTNode bPrevLocation = null;
boolean bDone = false;
while(bDone != true && bLocation != null){
if(toDie.compareTo(bLocation.getData()) == 0){
bDone = true;
}
else if(toDie.compareTo(bLocation.getData()) < 0){
bPrevLocation = bLocation;
bLocation = bLocation.getLeft();
}
else{
bPrevLocation = bLocation;
bLocation = bLocation.getRight();
}
}
if(bLocation == null){
return null;
}
if(bDebug){ //ya know. having a built in Debugger is why I love
//Visual Studio
System.out.println("bDebug Start");
System.out.println(bLocation.getData());
System.out.println("bDebug End");
}
Comparable data = bLocation.getData();
remove(bLocation,bPrevLocation);
return data;
}//end remove(Comparable)
/**
*Recurse Method for removing a node
*@param bLocation, the location of the node
*@param bPrevLocation, the Parent of bLocation
*/
private void remove(BSTNode bLocation,BSTNode bPrevLocation){
//if no kids
if(bLocation.getLeft() == null && bLocation.getRight() == null){
if(bPrevLocation == null){
root = null;
return;
}
if(bPrevLocation.getLeft() == bLocation){
bPrevLocation.setLeft(null);
}
else{//bPrevLocation.getRight() == bLocation
bPrevLocation.setRight(null);
}
}
//one or two kids, gotta kill its parent, how sad
else{
BSTNode bTraverse;
BSTNode bPrevTraverse;
if(bLocation.getRight() != null){
bTraverse = bLocation.getRight();
bPrevTraverse = bLocation;
while(bTraverse.getLeft() != null){
bPrevTraverse = bTraverse;
bTraverse = bTraverse.getLeft();
}
bLocation.setData(bTraverse.getData());
remove(bTraverse,bPrevTraverse);
}
else if(bLocation.getLeft() != null){
bTraverse = bLocation.getLeft();
bPrevTraverse = bLocation;
while(bTraverse.getRight() != null){
bPrevTraverse = bTraverse;
bTraverse = bTraverse.getRight();
}
bLocation.setData(bTraverse.getData());
remove(bTraverse,bPrevTraverse);
}
else{}
}
}//end remove(BSTNode,BSTNode)
/**
*Traverse tree output
*/
public void outputTree(){
outputTree(root);
}
/**
*Traverse current
*/
public void outputTree(BSTNode current){
if(current == null){
return;
}
outputTree(current.getLeft());
System.out.println(current);
outputTree(current.getRight());
}
/**
*Clear Tree
*/
private void clearTree(){
root = null;
}
/**
*Writes BST data to file
*@param oos, the stream to write with
*@param tree, the BST to get data from
*/
public void writeAircraft(BST tree,PrintWriter pw){
writeAircraft(root,pw);
}
/**
*Writes BST data to file
*@param oos, the stream to write with
*@param current, the current node
*/
private void writeAircraft(BSTNode current,PrintWriter pw){
if(current == null){
return;
}
writeAircraft(current.getLeft(),pw);
Aircraft air = (Aircraft)current.getData();
String temp = air.getModel() + " " + air.getNickname() + " " +
air.getRole() + " " + air.getLaunchPriority();
pw.println(temp);
writeAircraft(current.getRight(),pw);
}
/**
*creates the launchQueue for th aircraft carrier
*/
public void createLaunchQueue(BST bst,Heap toAdd){
createLaunchQueue(bst.root,toAdd);
}
/**
*Helper method for createLaunchQueue(BST,Heap)
*/
private void createLaunchQueue(BSTNode current,Heap toAdd){
if(current == null){
return;
}
createLaunchQueue(current.getRight(),toAdd);
((Aircraft)current.getData()).switchComparators();
toAdd.insert(current);
createLaunchQueue(current.getLeft(),toAdd);
}
/**
* Debugging main for class BST.
* This method will rigorously test my code.
*
*
* @param args a String array of command line arguments.
*/
public static void main(String[] args) {
//lets test this sucker out
BST bst = new BST();
bst.addItr(new Integer(10));
bst.addItr(new Integer(5));
bst.addItr(new Integer(1));
bst.addItr(new Integer(8));
bst.addItr(new Integer(9));
bst.addItr(new Integer(15));
bst.addItr(new Integer(13));
bst.addItr(new Integer(18));
bst.outputTree();
Integer five = new Integer(5);
System.out.println("\nTesting find()...");
System.out.println(bst.find(five));
System.out.println("Done.\n");
//remove w/0 kids
bst.clearTree();
bst.add(new Integer(10));
bst.add(new Integer(5));
bst.add(new Integer(1));
bst.add(new Integer(8));
bst.add(new Integer(9));
bst.add(new Integer(15));
bst.add(new Integer(13));
bst.add(new Integer(18));
System.out.println("\nTesting remove(0 kids)...");
bst.remove(new Integer(1));
bst.outputTree();
System.out.println("Done\n");
//remove w/1 kid
bst.clearTree();
bst.add(new Integer(10));
bst.add(new Integer(5));
bst.add(new Integer(1));
bst.add(new Integer(8));
bst.add(new Integer(9));
bst.add(new Integer(15));
bst.add(new Integer(13));
bst.add(new Integer(18));
System.out.println("\nTesting remove(1 kid)...");
bst.remove(new Integer(8));
bst.outputTree();
System.out.println("Done\n");
//remove w/2 kids
bst.clearTree();
bst.add(new Integer(10));
bst.add(new Integer(5));
bst.add(new Integer(1));
bst.add(new Integer(8));
bst.add(new Integer(9));
bst.add(new Integer(15));
bst.add(new Integer(13));
bst.add(new Integer(18));
System.out.println("\nTesting remove(2 kids)...");
bst.remove(new Integer(5));
bst.outputTree();
System.out.println("Done\n");
//remove root
bst.clearTree();
bst.add(new Integer(10));
bst.add(new Integer(5));
bst.add(new Integer(1));
bst.add(new Integer(8));
bst.add(new Integer(9));
bst.add(new Integer(15));
bst.add(new Integer(13));
bst.add(new Integer(18));
System.out.println("\nTesting remove(root)...");
bst.remove(new Integer(10));
bst.outputTree();
System.out.println("Done\n");
//remove nothing single thing tree
bst.clearTree();
bst.add(new Integer(10));
bst.remove(new Integer(10));
bst.outputTree();
System.out.println("\nTesting remove(nothing but root tree)...");
bst.remove(new Integer(10));
bst.outputTree();
System.out.println("Done\n");
}// end of main(String[] args)
}// end of class BST