Java Создание бинарного дерева поиска (оно работает, но я знаю, что делаю это неправильно)
Меня попросили создать двоичное дерево поиска с использованием целых чисел, затем строки попросили изменить его, чтобы оно было универсальным и позволяло пользователю выбирать, какое дерево ему нужно. Теперь я изменил свой код узла и дерева, чтобы он был универсальным, и он работает со строками и целыми числами (используя BinarySearchTree run = new BinarySearchTree();), но у меня есть много предупреждений о необработанных и универсальных типах, поэтому я знаю, что я не делаю это правильно.
дерево
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(")");
}
}
}
Узел
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(")");
}
}
}
основной класс
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;
}
}
}
}
Теперь я не уверен, стоит ли мне приводить конкретные типы, запускать другие методы или что-то еще. Я посмотрел онлайн, но не могу найти достаточно конкретных ответов, чтобы помочь мне понять, что я делаю неправильно.
Как уже говорилось, мой код работает, но, пожалуйста, скажите, что я делаю неправильно. Также, если вы найдете что-то еще, не относящееся к моей проблеме, но плохое в целом, не стесняйтесь подшучивать.
Спасибо
1 ответ
Всякий раз, когда вы делаете это:
new BSTNode(value);
Вы должны делать это:
new BSTNode<T>(value);
Когда вы используете универсальные шаблоны, вы разрешаете использовать любой тип вместо T. Когда вы создаете новый объект, тип не может оставаться универсальным. Вы должны указать тип, с которым вы создаете экземпляр объекта.