在给定范围内打印 BST 键

Question

我想知道我在给定范围 [min, max] 中打印 BST 键的方法有什么问题。鉴于 class

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);

每当 nodes 数据大于 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 遍历，这就是为什么它先向左，然后打印然后向右。然后它检查 node 是否小于 min。在这种情况下，它向右递归，否则向左递归。

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 属性：

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 中）...

在给定范围内打印 BST 键

Print BST keys in the given range

java

algorithm

recursion

binary-tree

binary-search-tree