비교기와 BST

Question

메신저에서 BST에 항목이 있는지 확인할 수있는 방법을 만들려고합니다. 이것은 내가 지금까지 무엇을 가지고 :

// 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; 
} 

내 질문에 내가 그것을 작동하도록 내는 방법을 포함 해결 할 방법은 다음과 같습니다

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

이러한 내 필드입니다. 지금까지는 comp.compare (value1.root.value) 아래의 행에 도달하고 '<'을 E 유형의 두 요소에서 사용할 수 없다고 말합니다. 이것을 어떻게 수정하여 비교기를 계속 실행할 수 있습니까?

Answer 1

비교기가 int를 반환합니다.

이 int가 0이면 두 객체의 값이 동일하지 않고 0보다 작 으면 <과 같으며 0보다 크면 해당 값은>과 같습니다.

비교기 호출의 결과를 사용하여 오른쪽 또는 왼쪽 하위 트리를 통과해야하는지 확인해야합니다.

왼쪽/오른쪽 가지가 null이면 false를 반환하고 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 메소드를 구현하는 방법을 볼 수있는 내 블로그에 모습을 가질 수 있습니다.