我有以下类，我想让用户选择是否要创建带有整数的 BST 或带有字符串的 BST。当用户选择 5 时如何从整数创建 BST，或者当用户按 6 时如何从字符串创建 BST？另外，如果有人发现我的泛型有问题，请告诉我!
非常感谢
public class BSTNode <T extends Comparable<T>>
{
T value;
BSTNode<T> left;
BSTNode<T> right;
public BSTNode(T value, BSTNode<T> l,BSTNode<T> r)
{
this.value = value;
left = l;
right = r;
}
public BSTNode(T value)
{
this(value,null,null);
}
public T getValue()
{
return value;
}
public void setValue(T value)
{
this.value = value;
}
public BSTNode<T> getLeftChild()
{
return left;
}
public BSTNode<T> getRightChild()
{
return right;
}
public void setLeftChild(BSTNode<T> node)
{
left = node;
}
public void setRightChild(BSTNode<T> 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.compareTo(this.value)==0)
return false;
else if (value.compareTo(this.value) < 0)
{
if (left == null)
{
left = new BSTNode<T>(value);
return true;
} else
return left.add(value);
}
else if (value.compareTo(this.value) > 0)
{
if (right == null)
{
right = new BSTNode<T>(value);
return true;
}
else
return right.add(value);
}
return false;
}
public boolean remove(T value2, BSTNode<T> parent)
{
if (value2.compareTo(this.value)<0)
{
if (left != null)
return left.remove(value2, this);
else
return false;
}
else if (value2.compareTo(this.value)>0)
{
if (right != null)
return right.remove(value2, 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;
}
}
public T minValue()
{
if (left == null)
return value;
else
return left.minValue();
}
}
public class BinarySearchTree <T extends Comparable<T>>
{
private BSTNode<T> root;
public BinarySearchTree(T value)
{
root = new BSTNode<T>(value);
}
public BSTNode getRoot()
{
return root;
}
public boolean search(T value)
{
if (root.equals(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 static void displayInorder(BSTNode T)
{
if (T!=null)
{
if (T.getLeftChild()!=null)
{
displayInorder(T.getLeftChild());
}
System.out.print(T.getValue() + " ");
if(T.getRightChild()!=null)
{
displayInorder(T.getRightChild());
}
}
}
}
import java.util.Scanner;
public class main {
public static void main(String[] args) {
BinarySearchTree b = new BinarySearchTree(null);
boolean flag = true;
while (flag) {
Scanner scan = new Scanner(System.in);
System.out.println("Select 1 to add values in to BST\n"
+ "Select 2 to delete values from the BST \n"
+ "Select 3 to search for a value\n"
+ "Select 4 to display te values held in the BST\n"
+ "Select 5 to create a BST of strings\n"
+ "Select 6 to create a BST of integers\n"
+ "Select 7 to exit" );
int opt = scan.nextInt();
switch (opt) {
case 1: System.out.println("Insert the value of your choice: ");
String str = scan.next();
b.add(str);
break;
case 2: System.out.println("Insert the value of your choice: ");
str = scan.next();
b.remove( str);
break;
case 3:
System.out.println("Insert the value of your choice: ");
str = scan.next();
b.search(str);
break;
case 4:
BinarySearchTree.displayInorder(b.getRoot());
break;
case 5:
case 7:
flag=false;
break;
}
}
}
}
最佳答案
为了在代码中充分利用泛型，这是我的建议:
我将添加一个方法来将字符串(用户输入)处理为树类中的适当类型:
...
import java.util.function.Function;
...
public class BinarySearchTree <T extends Comparable<T>>
{
private BSTNode<T> root;
private Function<String,T> valueDecoder
public BinarySearchTree(final Function<String,T> valueDecoder)
{
this.valueDecoder = valueDecoder;
root = new BSTNode<T>(null);
}
...
public boolean decodeAndAdd(final String encodedValue) {
return add(valueDecoder.apply(encodedValue));
}
public boolean decodeAndRemove(final String encodedValue) {
return remove(valueDecoder.apply(encodedValue));
}
}
```
然后您将离开 b变量未定义/空，直到您实际上知道用户提供的选择的树类型。因为它可能包含 String或Integer这里你只能使用?作为类型参数，也许 ? extends Comparable<?>因为这是约束的一部分... ?在这种情况下没问题:
BinarySearchTree<?> b = null ;
现在，当用户请求String时或Integer树，您需要提供适当的 lambda 将扫描的字符串传输到实际的元素值:
case 5:
b = new BinarySearchTree<>(scanStr -> scanStr);
break;
case 6:
b = new BinarySearchTree<>(scanStr -> Integer.parseInt(scanStr));
break;
现在添加和删除都很简单:
case 1:
b.decodeAndAdd(scan.next());
break;
case 2:
b.decodeAndRemove(scan.next());
break;
如果用户在树是 Integer 时提供无效的整数字符串值树它会导致 NumberFormatException然后程序就会停止。也许您宁愿显示错误消息并允许用户执行其他操作。为此:
case 6:
b = new BinarySearchTree<>(scanStr -> {
try {
return Integer.parseInt(scanStr);
} catch (NumberFormatException ex) {
throw new IllegalArgumentException("you must provide a valid integer value: '" + scanStr + "'");
}
});
break;
...
case 1:
try {
b.decodeAndAdd(scan.next());
} catch (final IllegalArgumentException ex) {
System.err.println("ERROR: " + ex.getMessage());
}
break;
case 2:
try {
b.decodeAndRemove(scan.next());
} catch (final IllegalArgumentException ex) {
System.err.println("ERROR: " + ex.getMessage());
}
break;
如果您想让事情变得更加模块化，那么将decodeAndAdd和decodeAndRemove添加到BinarySearchTree类中可能并不理想，因为BST可能会在问题中描述的用户命令行上下文之外使用。
在这种情况下，您可以定义一个类似于类的通用“结构”，其中包含一个引用，该引用包含对 BST 的引用和解码 lambda，并且使用类型参数将它们的元素类型绑定(bind)为相同。您还可以在另一个用户界面专用 BST 中扩展 BST 类，以添加此功能:
class CommandLineBST<T> {
public final BST<T> tree;
public final Function<String, T> valueDecoder;
public CommandLineBST(final BST<T> tree, final Function<String, T> decoder) {
this.tree = tree;
this.valueDecoder = decoder;
}
public boolean add(final String scanStr) {
return tree.add(valueDecoder.apply(scanStr));
}
public boolean remove(final String scanStr) {
return tree.remove(valueDecoder.apply(scanStr));
}
}
或
class CommandLineBST<T> extends BST<T> {
private Function<String, T> valueDecoder;
public CommandLineBST(final Function<String, T> valueDecoder) {
super(null);
this.valueDecoder = valueDecoder;
}
public boolean decodeAndAdd(final String scanStr) { ... }
public boolean decodeAndRemove(final String scanStr) { ... }
}
关于java - 通用二叉搜索树，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/47492314/