打印给定范围内的BST键

Question

我想知道在给定范围[min，max]内打印BST键的方法出了什么问题。给定类别

public class BinarySearchTree<E extends Comparable<? super E>> {
private Node<E> root;

// Constructors and other methods

private static class Node<E> {
private E data;
private Node<E> left;
private Node<E> right;

private Node(E data) {
data = data;
left = right = null;
}
}
}

这个解决方案有什么问题：

public void printPart(E min, E max) {
Print(root, min, max);
}
private void Print(Node<E> n, E min, E max){
if(n!=null){
if(n.data.compareTo(min) > 0){ // If node data is greater than min recurse through left subtree
Print(n.left, min, max);
}else if(n.data.compareTo(min) >=0 && n.data.compareTo(max) <=0){ // Printing the root if it lies between the given bounderies
System.out.println(n.data);
} else{ // recurse through right subtree
Print(n.right, min, max);
}
}
}

Answer 1

当前算法的条件是错误的。您首先检查：

if(n.data.compareTo(min) > 0){ // If node data is greater than min recurse through left subtree
Print(n.left, min, max);

每当node的数据大于min时，就通过左子树递归。但是如果它大于min而小于max呢？由于这是一个if... else if...构造，所以其他条件永远不会满足。因此，您可能会错过打印大于min且小于max的node。

那么第二个条件如下：

}else if(n.data.compareTo(min) >=0 && n.data.compareTo(max) <=0){ // Printing the root if it lies between the given bounderies
System.out.println(n.data);

现在，如果node在min和max之间的适当间隔内，则只打印它，而不会左右递归。您可能还缺少其他node。

因此，一般来说，条件写得不正确。以下代码首先检查node是否处于min/max间隔中。如果是这样，它将左右遍历，并打印节点。这是一个inorder遍历，这就是为什么它先向左，然后打印，然后向右。然后它检查CCD_ 16是否小于CCD_。在这种情况下，它向右递归，否则向左递归。

public void printPart(E min, E max) {
Print(root, min, max);
}
private void Print(Node<E> n, E min, E max){
if(n!=null){
if(n.data.compareTo(min) >=0 && n.data.compareTo(max) <=0){ // If node lies in min/max interval: print and recurse both left and right
Print(n.left, min, max);  // we do an inorder: left, root, right
System.out.println(n.data);
Print(n.right, min, max);
}else if(n.data.compareTo(min) < 0){ // If node less than min, recurse right
Print(n.right, min, max);
} else{ // recurse left
Print(n.left, min, max);
}
}
}

Answer 2

首先遍历整个树正确：

private void Print(Node node) {
if (node == null) return;
Print(node.left);
// Visit the node in BST sorted order here.
Print(node.right);
}

在您的情况下；访问"；是检查节点的值是否在该范围内。

在每次递归调用中传递范围没有多大意义。它冗长且容易出错。您可以将其作为类属性：

class RangePrinter<E extends Comparable<? super E>> {
private final E min, max;
private RangePrinter(E min, E max) {
this.min = min; this.max = max;
}
private void print(Node<E> node) {
if (node == null) return;
print(node.left);
if (min.compareTo(node.data) <= 0 && node.data.compareTo(max) <= 0) 
System.out.println(node.data);
print(node.right);
}
static <E extends Comparable<? super E>> void Print(Node<E> node, E min, E max) {
new RangePrinter(min, max).print(node);
}
}

将其与RangerPrinter.Print(root, 3, 42);一起使用。

请注意，这是一个幼稚的解决方案，因为您可能有一个具有十亿个节点的树，并且只需要打印3个。这个算法将访问所有十亿。一个好的人最多只需要访问90个左右。但实现起来更难(至少在Java中(。。。