二叉搜索树验证在从根节点开始验证之前需要最小和最大范围。
下面是我为整数执行此操作的代码。
public boolean checkBST(Node root) {
int min = Integer.MIN_VALUE;
int max = Integer.MAX_VALUE;
return validateBST(root, min, max);
}
参考 ： https://en.wikipedia.org/wiki/Binary_search_tree#Verification
随着验证在树中向下进行，将根据在子树节点上找到的值来取消有效范围。但是，对于验证顶部节点，我需要指定一个接受任何值的范围。
使用数字基元类型包装器(如Integer(上面的示例)或Double(如果您提交到特定元素类型)很容易做到这一点。但是，我需要推广这种方法，以便它适用于任何给定的T类型(它可以是Number，或者完全不同的东西)。
我们可以假设T是一个Comparable<? extends T>，或者在构造树时传递了适当的比较器。
我该怎么做？
要比较对象，您需要它们来实现Comparable因此将节点类型定义为Comparable的子类：
class Node<Q extends Comparable<Q>>{
private final Q value;
private Node left, right;
Node getLeft() {
return left;
}
Node getRight() {
return right;
}
Node(Q value){
this.value = value;
}
Q getValue(){
return value;
}
}
当Q实现可比较时，您可以比较两个对象，例如：
Node<String> minNode = new Node<>("Z");
Node<String> maxNode = new Node<>("A");
Node<String> aNode = new Node<>("L");
System.out.println(aNode.getValue().compareTo(minNode.getValue())< 0 &&
aNode.getValue().compareTo(maxNode.getValue()) > 0 );
能够比较，你应该能够定义boolean isBST(Node node, Node minNode, Node maxNode)
编辑：如果你的问题是关于"任何给定T的Integer.MIN_VALUE和Integer.MAX_VALUE的通用版本"：
我认为实际上不需要这样做。您可以遍历整个图形，找到最小值、最大值并使用这些值。
如果我正确理解了这个问题，那么您正在询问如何计算出任何给定类型的绝对最大值或最小值，以便您可以指定一个接受任何值为有效的范围。
不幸的是，一般来说，任意T不一定具有可实例化的最小值和最大值。事实上，int和Integer这样做只是因为由于表示限制，它们不能任意大或小。
例如String可以争辩说空字符串(")是最小值，当然小于或等于使用其自然顺序的任何其他String，但最大字符串是什么。它可能会无限长地重复最大 unicode 字符，因此您无法创建这样的对象。
但是，这不应该阻止您定义包含任何值或它们在一端打开的范围(即它们有最小值但没有最大值，反之亦然)。
例如，如果要在将使用此类范围的方法的签名中将范围指定为两个参数，则可以简单地指定null以指示最小值或最大值不存在，即范围的末尾是开放的。
在我看来，这与您的valideteBST配合得很好，因为它已经具有这两个参数。
class BST<T extends Comparable<T>> {
// ...
public boolean checkBST(Node<T> root) {
return validateBST(root, null, null);
}
// ...
boolean validateBST(Node<T> node, T min, T max) {
if (node == null) {
// nothing to do here.
return true;
}
final T value = node.getValue();
if (min != null && min.compareTo(value) >= 0) {
return false;
} else if (max != null && max.compareTo(value) <= 0) {
return false;
} else {
return validateBST(node.getLeft(), min, value) &&
validateBST(node.getRight(), value, max);
}
}
// ...
}
现在有些人可能不喜欢为此直观地使用null。在这种情况下，您可能需要定义一个封装它的Range<T>类：
public class Range<T extends Comparable<T>> {
private T min;
private T max;
private Range(T min, T max) {
this.min = min;
this.max = max;
}
public static <T> of(T min, T max) {
Objects.requiresNonNull(min);
Objects.requiresNonNull(max);
return new Range(min, max);
}
public static <T> from(T min) {
Objects.requiresNonNull(min);
return new Range(min, null);
}
public static <T> to(T max) {
Objects.requiresNonNull(max);
return new Range(null, max);
}
public static <T> all() {
return new Range(null, null);
}
public Range<T> subRangeTo(T max) {
Objects.requiresNonNull(max);
return new Range<>(this.min, max);
}
public Range<T> subRangeFrom(T min) {
Objects.requiresNonNull(min);
return new Range<>(min, this.max);
}
public boolean encloses(T value) {
Objects.requiresNonNull(value);
return (min == null || min.compareTo(value) < 0)
&& (max == null || max.compareTo(value) > 0);
}
}
然后验证中的代码就更简单了：
// ...
public boolean checkBST(Node<T> root) {
return validateBST(root, Range.all());
}
// ...
boolean validateBST(Node<T> node, Range<T> range) {
if (node == null) {
return true;
}
if (!range.encloses(node.getValue)) {
return false;
} else {
return validateBST(node.getLeft(), Range.subRangeTo(value))
&& validateBST(node.getRight(), Range.subRangeFrom(value));
}
}
// ...
请注意，任一解决方案中的范围都不包含限制值。
这对于没有重复键的 BST 树是必需的。对于可能具有重复键的树，您可以通过使范围"封闭"比较以接受值与其限制相同来使该方法起作用。
或者，节点可以保存对该键的重复次数，以便键保持唯一，如果大多数键要重复，这更有意义。