Cosc241 - Java
Lab 19: Binary Search Tree App
BST.java
package lab19;
/**
* The objects of this class are Binary Search Trees but they are represented
* without a header node. In particular we have to represent an empty list as
* one where the left and right pointers are null (and that is not the same
* as their being empty!).
*
* @author Mike Atkinson and Iain Hewson
*/
public class BST<E extends Comparable<E>> {
/** The root element of this BST. */
private E element;
/** The left and right subtrees of this BST. */
private BST<E> left, right;
/** Creates an empty BST. */
public BST() {
left = right = null;
}
/**
* Creates a one node BST with element at the root.
*
* @param element the element to place at the root.
*/
public BST(E element) {
this.element = element;
this.left = new BST<E>();
this.right = new BST<E>();
}
/**
* Changes datafields so that this BST becomes that BST.
*
* @param that the BST to make this BST the same as.
*/
private void becomes(BST<E> that) {
this.left = that.left;
this.right = that.right;
this.element = that.element;
}
/**
* Returns true if this BST is empty, otherwise false.
*
* @return true if empty, otherwise false.
*/
public boolean isEmpty() {
return left == null && right == null;
}
/**
* Decides whether target is present in this BST.
*
* @param target the element being searched for.
* @return true if target is present, false if target not present.
*/
public boolean isPresent(E target) {
if (isEmpty()) {
return false;
}
int direction = target.compareTo(element);
if (direction == 0) {
return true;
}
if (direction < 0) {
return left.isPresent(target);
}
return right.isPresent(target);
}
/**
* Insert a new element in this BST.
*
* @param element the element to be inserted.
*/
public void insert(E element) {
if (isEmpty()) {
this.becomes(new BST<E>(element));
} else {
int direction = element.compareTo(this.element);
if (direction == 0) //it is already in the tree
return;
if (direction > 0) //go right
right.insert(element);
else //go left
left.insert(element);
}
}
/**
* Deletes target from this BST.
*
* @param target the element being deleted.
*/
public void delete(E target) {
// implement this method for lab 19
}
/**
* Deletes the smallest element from this BST. It is only used when this
* BST is known to be non-empty.
*
* @return the deleted element.
*/
private E deleteMin() {
// the next line is just to make the code compile
return null;
// implement this method for lab 19
}
/** Deletes the root of this BST. */
private void deleteRoot() {
// implement this method for lab 19
}
/**
* Creates a String representation of the BST by performing an in-order
* traversal.
*
* @return the inorder listing in String format of the BST.
*/
private String toStringAux() {
return (left.isEmpty() ? "" : left.toStringAux() + ", ")
+ element +
(right.isEmpty() ? "" : ", " + right.toStringAux());
}
/**
* In-order traversal String listing of this BST.
*
* @return the inorder listing in String format of the BST.
*/
public String toString() {
return "[" + (isEmpty() ? "" : toStringAux()) + "]";
}
/**
* Returns a String representation of this BST as a tree on its side with
* the root at the left.
*
* @return An indented String representation of this BST.
*/
public String toPrettyString() {
return toPrettyString("");
}
/**
* A recursive method which returns a String representation of this BST as
* a tree on its side with the root at the left.
*
* @param spaces A String of spaces used to create the appropriate indent.
* @return An indented String representation of this BST.
*/
private String toPrettyString(String spaces) {
if (isEmpty()) {
return "";
} else {
return right.toPrettyString(spaces + " ") +
(right.isEmpty() ? "" : spaces + " /\n") +
spaces + element + "\n" +
(left.isEmpty() ? "" : spaces + " \\\n") +
left.toPrettyString(spaces + " ");
}
// Note: the format for a conditional expression in Java is:
// i = (condition) ? expressionOne : expressionTwo;
// This is the same as:
// if (condition) {
// i = expressionOne;
// } else {
// i = conditionTwo;
// }
}
} // end of class BST
BSTOriginal.java
package lab19;
/**
* The objects of this class are Binary Search Trees but they are represented
* without a header node. In particular we have to represent an empty list as
* one where the left and right pointers are null (and that is not the same
* as their being empty!).
*
* @author Mike Atkinson and Iain Hewson
*/
public class BST<E extends Comparable<E>> {
int i = 0;
/** The root element of this BST. */
private E element;
/** The left and right subtrees of this BST. */
private BST<E> left, right;
/** Creates an empty BST. */
public BST() {
left = right = null;
}
/**
* Creates a one node BST with element at the root.
*
* @param element the element to place at the root.
*/
public BST(E element) {
this.element = element;
this.left = new BST<E>();
this.right = new BST<E>();
}
/**
* Changes datafields so that this BST becomes that BST.
*
* @param that the BST to make this BST the same as.
*/
private void becomes(BST<E> that) {
this.left = that.left;
this.right = that.right;
this.element = that.element;
}
/**
* Returns true if this BST is empty, otherwise false.
*
* @return true if empty, otherwise false.
*/
public boolean isEmpty() {
return left == null && right == null;
}
/**
* Decides whether target is present in this BST.
*
* @param target the element being searched for.
* @return true if target is present, false if target not present.
*/
public boolean isPresent(E target) {
if (isEmpty()) {
return false;
}
int direction = target.compareTo(element);
if (direction == 0) {
return true;
}
if (direction < 0) {
return left.isPresent(target);
}
return right.isPresent(target);
}
/**
* Insert a new element in this BST.
*
* @param element the element to be inserted.
*/
public void insert(E element) {
if (isEmpty()) {
this.becomes(new BST<E>(element));
} else {
int direction = element.compareTo(this.element);
if (direction == 0) //it is already in the tree
return;
if (direction > 0) //go right
right.insert(element);
else //go left
left.insert(element);
}
}
/**
* Deletes target from this BST.
*
* @param target the element being deleted.
*/
public void delete(E target) {
// implement this method for lab 19
if (isEmpty()) {
System.out.println("empty");
} else {
int comparison = element.compareTo(target);
if (comparison > 0){ //k less than root, therefore go left
left.delete(target);
System.out.println("left ");
}
else if (comparison < 0) { //k greater than root, therefore go right
right.delete(target);
System.out.println("right ");
}
else if (comparison == 0)
deleteRoot();
}
}
/**
* Deletes the smallest element from this BST. It is only used when this
* BST is known to be non-empty.
*
* @return the deleted element.
*/
private E deleteMin() { // really deleteMax
// implement this method for lab 19
if (right.right.element == null){
E returnValue = right.element;
right.element = right.left.element;
return returnValue;
} else {
return right.deleteMin();
}
}
/** Deletes the root of this BST. */
private void deleteRoot() {
// implement this method for lab 19
System.out.println("root");
if(isEmpty()){
System.out.println("root empty");
}
else if (left.element == null){
element = right.element;
// right.becomes(new BST<E>(element));
}
else if (right.element == null){
element = left.element;
left.element = null;
}
else {
if (left.right.element == null){ //left has no right child
element = left.element;
left.element = left.left.element;
left.deleteRoot();
}
else {
left.element = deleteMin();
}
}
}
/**
* Creates a String representation of the BST by performing an in-order
* traversal.
*
* @return the inorder listing in String format of the BST.
*/
private String toStringAux() {
return (left.isEmpty() ? "" : left.toStringAux() + ", ")
+ element +
(right.isEmpty() ? "" : ", " + right.toStringAux());
}
/**
* In-order traversal String listing of this BST.
*
* @return the inorder listing in String format of the BST.
*/
public String toString() {
return "[" + (isEmpty() ? "" : toStringAux()) + "]";
}
/**
* Returns a String representation of this BST as a tree on its side with
* the root at the left.
*
* @return An indented String representation of this BST.
*/
public String toPrettyString() {
return toPrettyString("");
}
/**
* A recursive method which returns a String representation of this BST as
* a tree on its side with the root at the left.
*
* @param spaces A String of spaces used to create the appropriate indent.
* @return An indented String representation of this BST.
*/
private String toPrettyString(String spaces) {
if (isEmpty()) {
return "";
} else {
return right.toPrettyString(spaces + " ") +
(right.isEmpty() ? "" : spaces + " /\n") +
spaces + element + "\n" +
(left.isEmpty() ? "" : spaces + " \\\n") +
left.toPrettyString(spaces + " ");
}
// Note: the format for a conditional expression in Java is:
// i = (condition) ? expressionOne : expressionTwo;
// This is the same as:
// if (condition) {
// i = expressionOne;
// } else {
// i = conditionTwo;
// }
}
} // end of class BST
BSTApp.java
package lab19;
import java.util.*;
public class BSTApp {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
BST<String> bst = new BST<String>();
while(input.hasNextLine()){
handleLine(input.nextLine(), bst);
}
}
public static void handleLine(String line, BST<String> bst) {
Scanner tokens = new Scanner(line);
if (tokens.hasNext("[idp]")) { // if next token is i, d, or p
char command = tokens.next().charAt(0);
switch(command) {
case 'i':
while(tokens.hasNext()){
bst.insert(tokens.next());
}
break;
case 'd':
if(tokens.hasNext()) {
bst.delete(tokens.next());
}
break;
case 'p':
System.out.println(bst);
System.out.println(bst.toPrettyString());
break;
}
}
}
}
ImmutableListApp.java
package lab19;
import java.util.*;
public class ImmutableListApp {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
BST<String> bst = new BST<String>();
while(input.hasNextLine()){
handleLine(input.nextLine(), bst);
}
}
public static void handleLine(String line, BST<String> bst) {
Scanner tokens = new Scanner(line);
if (tokens.hasNext("[arsp]")) { // if next token is a,g, r or p
char command = tokens.next().charAt(0);
switch(command) {
case 'a':
if(tokens.hasNext()){
bst = bst.add(tokens.next());
bst = bst.addAll(iList);
System.out.println(bst);
}
break;
case 's':
if(tokens.hasNext()) {
bst.set(tokens.nextInt(), tokens.next());
}
break;
case 'r':
if(tokens.hasNextInt()) {
bst.remove(tokens.nextInt());
}
break;
case 'p':
System.out.println(bst);
break;
}
}
}
}
/**
* The objects of this class are Binary Search Trees but they are represented
* without a header node. In particular we have to represent an empty list as
* one where the left and right pointers are null (and that is not the same
* as their being empty!).
*
* @author Mike Atkinson and Iain Hewson
*/
public class BST<E extends Comparable<E>> {
/** The root element of this BST. */
private E element;
/** The left and right subtrees of this BST. */
private BST<E> left, right;
/** Creates an empty BST. */
public BST() {
left = right = null;
}
/**
* Creates a one node BST with element at the root.
*
* @param element the element to place at the root.
*/
public BST(E element) {
this.element = element;
this.left = new BST<E>();
this.right = new BST<E>();
}
/**
* Changes datafields so that this BST becomes that BST.
*
* @param that the BST to make this BST the same as.
*/
private void becomes(BST<E> that) {
this.left = that.left;
this.right = that.right;
this.element = that.element;
}
/**
* Returns true if this BST is empty, otherwise false.
*
* @return true if empty, otherwise false.
*/
public boolean isEmpty() {
return left == null && right == null;
}
/**
* Decides whether target is present in this BST.
*
* @param target the element being searched for.
* @return true if target is present, false if target not present.
*/
public boolean isPresent(E target) {
if (isEmpty()) {
return false;
}
int direction = target.compareTo(element);
if (direction == 0) {
return true;
}
if (direction < 0) {
return left.isPresent(target);
}
return right.isPresent(target);
}
/**
* Insert a new element in this BST.
*
* @param element the element to be inserted.
*/
public void insert(E element) {
if (isEmpty()) {
this.becomes(new BST<E>(element));
} else {
int direction = element.compareTo(this.element);
if (direction == 0) //it is already in the tree
return;
if (direction > 0) //go right
right.insert(element);
else //go left
left.insert(element);
}
}
/**
* Deletes target from this BST.
*
* @param target the element being deleted.
*/
public void delete(E target) {
// implement this method for lab 19
}
/**
* Deletes the smallest element from this BST. It is only used when this
* BST is known to be non-empty.
*
* @return the deleted element.
*/
private E deleteMin() {
// the next line is just to make the code compile
return null;
// implement this method for lab 19
}
/** Deletes the root of this BST. */
private void deleteRoot() {
// implement this method for lab 19
}
/**
* Creates a String representation of the BST by performing an in-order
* traversal.
*
* @return the inorder listing in String format of the BST.
*/
private String toStringAux() {
return (left.isEmpty() ? "" : left.toStringAux() + ", ")
+ element +
(right.isEmpty() ? "" : ", " + right.toStringAux());
}
/**
* In-order traversal String listing of this BST.
*
* @return the inorder listing in String format of the BST.
*/
public String toString() {
return "[" + (isEmpty() ? "" : toStringAux()) + "]";
}
/**
* Returns a String representation of this BST as a tree on its side with
* the root at the left.
*
* @return An indented String representation of this BST.
*/
public String toPrettyString() {
return toPrettyString("");
}
/**
* A recursive method which returns a String representation of this BST as
* a tree on its side with the root at the left.
*
* @param spaces A String of spaces used to create the appropriate indent.
* @return An indented String representation of this BST.
*/
private String toPrettyString(String spaces) {
if (isEmpty()) {
return "";
} else {
return right.toPrettyString(spaces + " ") +
(right.isEmpty() ? "" : spaces + " /\n") +
spaces + element + "\n" +
(left.isEmpty() ? "" : spaces + " \\\n") +
left.toPrettyString(spaces + " ");
}
// Note: the format for a conditional expression in Java is:
// i = (condition) ? expressionOne : expressionTwo;
// This is the same as:
// if (condition) {
// i = expressionOne;
// } else {
// i = conditionTwo;
// }
}
} // end of class BST
/**
* The objects of this class are Binary Search Trees but they are represented
* without a header node. In particular we have to represent an empty list as
* one where the left and right pointers are null (and that is not the same
* as their being empty!).
*
* @author Mike Atkinson and Iain Hewson
*/
public class BST<E extends Comparable<E>> {
int i = 0;
/** The root element of this BST. */
private E element;
/** The left and right subtrees of this BST. */
private BST<E> left, right;
/** Creates an empty BST. */
public BST() {
left = right = null;
}
/**
* Creates a one node BST with element at the root.
*
* @param element the element to place at the root.
*/
public BST(E element) {
this.element = element;
this.left = new BST<E>();
this.right = new BST<E>();
}
/**
* Changes datafields so that this BST becomes that BST.
*
* @param that the BST to make this BST the same as.
*/
private void becomes(BST<E> that) {
this.left = that.left;
this.right = that.right;
this.element = that.element;
}
/**
* Returns true if this BST is empty, otherwise false.
*
* @return true if empty, otherwise false.
*/
public boolean isEmpty() {
return left == null && right == null;
}
/**
* Decides whether target is present in this BST.
*
* @param target the element being searched for.
* @return true if target is present, false if target not present.
*/
public boolean isPresent(E target) {
if (isEmpty()) {
return false;
}
int direction = target.compareTo(element);
if (direction == 0) {
return true;
}
if (direction < 0) {
return left.isPresent(target);
}
return right.isPresent(target);
}
/**
* Insert a new element in this BST.
*
* @param element the element to be inserted.
*/
public void insert(E element) {
if (isEmpty()) {
this.becomes(new BST<E>(element));
} else {
int direction = element.compareTo(this.element);
if (direction == 0) //it is already in the tree
return;
if (direction > 0) //go right
right.insert(element);
else //go left
left.insert(element);
}
}
/**
* Deletes target from this BST.
*
* @param target the element being deleted.
*/
public void delete(E target) {
// implement this method for lab 19
if (isEmpty()) {
System.out.println("empty");
} else {
int comparison = element.compareTo(target);
if (comparison > 0){ //k less than root, therefore go left
left.delete(target);
System.out.println("left ");
}
else if (comparison < 0) { //k greater than root, therefore go right
right.delete(target);
System.out.println("right ");
}
else if (comparison == 0)
deleteRoot();
}
}
/**
* Deletes the smallest element from this BST. It is only used when this
* BST is known to be non-empty.
*
* @return the deleted element.
*/
private E deleteMin() { // really deleteMax
// implement this method for lab 19
if (right.right.element == null){
E returnValue = right.element;
right.element = right.left.element;
return returnValue;
} else {
return right.deleteMin();
}
}
/** Deletes the root of this BST. */
private void deleteRoot() {
// implement this method for lab 19
System.out.println("root");
if(isEmpty()){
System.out.println("root empty");
}
else if (left.element == null){
element = right.element;
// right.becomes(new BST<E>(element));
}
else if (right.element == null){
element = left.element;
left.element = null;
}
else {
if (left.right.element == null){ //left has no right child
element = left.element;
left.element = left.left.element;
left.deleteRoot();
}
else {
left.element = deleteMin();
}
}
}
/**
* Creates a String representation of the BST by performing an in-order
* traversal.
*
* @return the inorder listing in String format of the BST.
*/
private String toStringAux() {
return (left.isEmpty() ? "" : left.toStringAux() + ", ")
+ element +
(right.isEmpty() ? "" : ", " + right.toStringAux());
}
/**
* In-order traversal String listing of this BST.
*
* @return the inorder listing in String format of the BST.
*/
public String toString() {
return "[" + (isEmpty() ? "" : toStringAux()) + "]";
}
/**
* Returns a String representation of this BST as a tree on its side with
* the root at the left.
*
* @return An indented String representation of this BST.
*/
public String toPrettyString() {
return toPrettyString("");
}
/**
* A recursive method which returns a String representation of this BST as
* a tree on its side with the root at the left.
*
* @param spaces A String of spaces used to create the appropriate indent.
* @return An indented String representation of this BST.
*/
private String toPrettyString(String spaces) {
if (isEmpty()) {
return "";
} else {
return right.toPrettyString(spaces + " ") +
(right.isEmpty() ? "" : spaces + " /\n") +
spaces + element + "\n" +
(left.isEmpty() ? "" : spaces + " \\\n") +
left.toPrettyString(spaces + " ");
}
// Note: the format for a conditional expression in Java is:
// i = (condition) ? expressionOne : expressionTwo;
// This is the same as:
// if (condition) {
// i = expressionOne;
// } else {
// i = conditionTwo;
// }
}
} // end of class BST
import java.util.*;
public class BSTApp {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
BST<String> bst = new BST<String>();
while(input.hasNextLine()){
handleLine(input.nextLine(), bst);
}
}
public static void handleLine(String line, BST<String> bst) {
Scanner tokens = new Scanner(line);
if (tokens.hasNext("[idp]")) { // if next token is i, d, or p
char command = tokens.next().charAt(0);
switch(command) {
case 'i':
while(tokens.hasNext()){
bst.insert(tokens.next());
}
break;
case 'd':
if(tokens.hasNext()) {
bst.delete(tokens.next());
}
break;
case 'p':
System.out.println(bst);
System.out.println(bst.toPrettyString());
break;
}
}
}
}
import java.util.*;
public class ImmutableListApp {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
BST<String> bst = new BST<String>();
while(input.hasNextLine()){
handleLine(input.nextLine(), bst);
}
}
public static void handleLine(String line, BST<String> bst) {
Scanner tokens = new Scanner(line);
if (tokens.hasNext("[arsp]")) { // if next token is a,g, r or p
char command = tokens.next().charAt(0);
switch(command) {
case 'a':
if(tokens.hasNext()){
bst = bst.add(tokens.next());
bst = bst.addAll(iList);
System.out.println(bst);
}
break;
case 's':
if(tokens.hasNext()) {
bst.set(tokens.nextInt(), tokens.next());
}
break;
case 'r':
if(tokens.hasNextInt()) {
bst.remove(tokens.nextInt());
}
break;
case 'p':
System.out.println(bst);
break;
}
}
}
}
