比較器和BST

Question

即時嘗試創建一個方法，它允許我檢查一個BST是否包含一個項目。這是我到目前爲止有：

public boolean contains(Object item) { 
    // YOUR CODE HERE 

    //changes item to E so it can be used in the comparator 
    E value1 = (E) item; 

    if (root.value.equals(item)){ 
     return true; 
    } 

    comp.compare(value1,root.value); 
    if(value1<root.value){ 
     if (left == null) 
      return null; 
     else 
      return left.contains(item); 
    } 

    else if(item >= value){ 
     if (right == null) 
      return null; 
     else 
      return right.contains(item); 
    } 
} 

，這些都是我的領域：

// Data fields 
private BSTNode root; 
private int count = 0; 
private Comparator<E> comp; // default comparator 

/** Private class for the nodes. 
* Has public fields so methods in BSTSet can access fields directly. 
*/ 
private class BSTNode { 

    // Data fields 

    public E value; 
    public BSTNode left = null; 
    public BSTNode right = null; 

    // Constructor 

    public BSTNode(E v) { 
     value = v; 
    } 

} 


public BSTSet() { 
    comp = new ComparableComparator();  // Declared below 
} 

public BSTSet(Comparator <E> c) { 
    comp = c; 
} 

我的問題是如何解決我的contains方法使其作品。到目前爲止，它到達comp.compare（value1.root.value）下的行，並且說'<'不能用於E類型的兩個元素。我如何解決這個問題，以便我可以繼續運行比較器？

Answer 1

你的比較器返回一個int。

如果這個int是0，那麼兩個對象的值是相同的，如果它小於0，它就等於你的<，如果它大於0，它就等於你的>。

您需要使用比較器調用的結果來檢查是否應該遍歷右側或左側的子樹。

另外，請不要如果左/右分支爲空則返回null，返回false。如果沒有左分支並且值小於當前根，那麼這是該算法的正確語義，因爲該項不在樹中，因此爲false。

Answer 2

你可以有類似下面：

public boolean containsItem(int i) { 
    Node<Integer> t = new Node<Integer>(i); 
    Node<Integer> r = (Node<Integer>) root; 
    while(r != null){ 
     int cmp = t.compareTo((Node<Integer>) r); 
     if(cmp == 0) 
      return true; 
     if(cmp >0) r = r.getRight(); 
     else r = r.getLeft(); 
    } 
    return false; 
} 

你可以看看我的博客，看看如何實現BST compareTo方法。