有人要求我使用整数制作二叉搜索树,然后使用字符串将其修改为通用的,并允许用户选择他想要的树。现在,我已将节点和树代码更改为通用的,并且它适用于字符串和整数(使用 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;
}
}
}
}
现在我不确定是否应该针对特定类型进行转换、运行不同的方法或其他方法。我在网上查了一下,但找不到足够具体的答案来帮助我理解我做错了什么。
正如之前所说,我的代码可以工作,但请告诉我我做错了什么。另外,如果您发现任何其他与我的问题无关但总体不好的内容,请随意取笑。
谢谢
最佳答案
每当您执行此操作时:
new BSTNode(value);
你应该这样做:
new BSTNode<T>(value);
当您使用泛型时,您允许使用任何类型来代替 T。当您实例化一个新对象时,该类型不能保持泛型。您必须指定实例化对象所用的类型。
关于Java 使二叉搜索树通用(它有效,但我知道我做得不对),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/40796420/