Mary Sue Mary Sue - 15 days ago 5
Java Question

Java Making a binary search tree generic (it works but I know I'm not doing it right)

I've been asked to make a binary search tree using ints, then strings then asked to modify it to be generic and allow the user to choose which he wants a tree of. Now I've changed my node and tree code to be generic and it works with strings and ints (using BinarySearchTree run = new BinarySearchTree();) but I have a lot of warning about raw and generic types so I know I'm not doing it right.

Tree

public class BinarySearchTree<T extends Comparable<T>> {
private BSTNode <T> root;

public BinarySearchTree() {
root = null;
}

public boolean search(T value) {
if (root == null)
return false;
else
return root.search(value);
}

public boolean add(T value) {
if (root == null) {
root = new BSTNode(value);
return true;
} else
return root.add(value);
}

public boolean remove(T value) {
if (root == null)
return false;
else {
if (root.getValue() == value) {
BSTNode auxRoot = new BSTNode(null);
auxRoot.setLeftChild(root);
boolean result = root.remove(value, auxRoot);
root = auxRoot.getLeftChild();
return result;
} else {
return root.remove(value, null);
}
}
}
public void printInorder() {
if (root != null){
System.out.print("(");
root.printInorder();
System.out.println(")");
}
}
}


Node

public class BSTNode<T extends Comparable<T>>{
private T value;
private BSTNode<T> left;
private BSTNode<T> right;

public BSTNode(T value) {
this.value = value;
left = null;
right = null;
}

public T getValue() {
return value;
}

public void setValue(T value) {
this.value = value;
}

public BSTNode getLeftChild() {
return left;
}

public BSTNode getRightChild() {
return right;
}

public void setLeftChild(BSTNode node) {
left = node;
}

public void setRightChild(BSTNode node) {
right = node;
}

public boolean search(T value) {
if (value.equals(this.value))
return true;
else if (value.compareTo(this.value) < 0) {
if (left == null)
return false;
else
return left.search(value);
} else if (value.compareTo(this.value) > 0) {
if (right == null)
return false;
else
return right.search(value);
}
return false;
}

public boolean add(T value) {
if (value == this.value)
return false;
else if (value.compareTo(this.value) < 0) {
if (left == null) {
left = new BSTNode(value);
return true;
} else
return left.add(value);
} else if (value.compareTo(this.value) > 0) {
if (right == null) {
right = new BSTNode(value);
return true;
} else
return right.add(value);
}
return false;
}

public boolean remove(T value, BSTNode parent) {
if (value.compareTo(this.value) < 0) {
if (left != null)
return left.remove(value, this);
else
return false;
} else if (value.compareTo(this.value) > 0) {
if (right != null)
return right.remove(value, this);
else
return false;
} else {
if (left != null && right != null) {
this.value = right.minValue();
right.remove(this.value, this);
} else if (parent.left == this) {
parent.left = (left != null) ? left : right;
} else if (parent.right == this) {
parent.right = (left != null) ? left : right;
}
return true;
}
}

Comparable getVal(){
return (Comparable) value;
}


public T minValue() {
if (left == null)
return value;
else
return left.minValue();
}

public void printInorder() {
if (left != null) {
System.out.print("(");
left.printInorder();
System.out.print(")");
}
System.out.print(this.value);
if (right != null) {
System.out.print("(");
right.printInorder();
System.out.print(")");
}
}
}


main class

import java.util.Scanner;

public class Run {

public static void main(String[] args){
BinarySearchTree run = new BinarySearchTree();

boolean running = true;
while(running == true){
System.out.println("Please select from the following options");
System.out.println("[0] To add a value to the tree");
System.out.println("[1] To delete a value to the tree");
System.out.println("[2] To search for a value in the tree");
System.out.println("[3] To display the values in the tree inorder");
System.out.println("[4] To exit");
System.out.println("[5] To create a BST of strings");
System.out.println("[6] To create a BST of integers");
Scanner select = new Scanner(System.in);
int in = select.nextInt();
switch(in){
case 0:
System.out.println("Enter a value to add to the tree");
String adding = select.next();
run.add(adding);
System.out.println(adding + " has been added");
break;
case 1:
System.out.println("Enter a value to delete from the tree");
String delete = select.next();
if(run.remove(delete) == true)
System.out.println(delete + " removed");
else
System.out.println(delete + " not found");
break;

case 2:
System.out.println("Enter a value to search for it in the tree");
String find = select.next();
if(run.search(find) == true)
System.out.println("Found " + find);
else
System.out.println(find + " not found.");
break;

case 3:
run.printInorder();
break;
case 4:
running = false;
break;

}
}

}
}


Now I'm not sure if I should be casting for the specific types, running different methods or something else. I've had a look online but I can't find specific enough answers to help me understand what it is I'm doing wrong.

As said before my code works but please tell me what it is I'm doing wrong. Also if you find anything else not specific to my problem but bad in general feel free to poke fun.

Thanks

Answer

Whenever you are doing this:

new  BSTNode(value);

You should be doing this:

new  BSTNode<T>(value);

When you use generics, you are allowing any type to be used in place of T. When you instantiate a new object, the type cannot remain generic. You have to specify the type you are instantiating the object with.