列印給定范圍內的BST密鑰

我想知道我在給定范圍 [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);
        }
    }

}

uj5u.com熱心網友回復：

您當前演算法的條件是錯誤的。你首先檢查：

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...構造，因此其他條件從未達到。因此，您可能會錯過列印node大于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);

現在，如果和node之間的間隔適當，則您只是在列印它，而不要左右遞回。您可能還缺少其他s。minmaxnode

所以，一般情況下，條件寫得不正確。下面的代碼首先檢查 是否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);
        }
    }

}

uj5u.com熱心網友回復：

首先正確遍歷整個樹：

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

請注意，這是一個簡單的解決方案，因為您可能有一棵具有 10 億個節點的樹，并且只需要列印 3 個。該演算法將訪問所有 10 億個節點。一個好的人最多只需要訪問大約 90 個。但這實作起來比較棘手（至少在 Java 中）......

標籤：爪哇 算法 递归 二叉树 二叉搜索树

上一篇：VersionOneRest查詢已洗掉專案

下一篇：從函式Python中獲取錯誤的回傳值