TreeSet/포함 메서드

Question

연습으로 나는 내 TreeSet 구현하려고합니다. 추가 및 제거 메소드를 코딩하기 전에 더 쉽게 보이는 것처럼 포함하는 것으로 시작하는 것이 좋지만 막혔습니다.

다음

static class Leaf<E extends Comparable<E>> implements Tree<E> { 

       //stuff 
     @Override 
     public boolean contains() { 
      return false; 
     } 

} 

가 Node 클래스의 :

내 나무가 Node 및 Leaf로 구성되어있다 (나는 그것의 좋은 부분을 조사하기 위해 내 나무로 말할 수있는 방법

static class Node<E extends Comparable<E>> implements Tree<E> { 

    private final E value; 
    private Tree<E> left; 
    private Tree<E> right; 

    //some stuff 
    @Override 
    public boolean contains(E elem) { 
     //here i'm blocked 
    } 
} 

왼쪽 또는 오른쪽) 요소와?

Answer 1

재귀 사용!

보시다시피 Leaf 개체는 Tree의 끝 부분을 구성하므로 메서드 중단 조건이됩니다.

Tree에 저장 될 객체는 Comparable이어야합니다. 그래서 다음과 같이 할 수 있습니다 포함 : 당신이 볼 수 있듯이 요소가 Tree에없는 경우

@Override 
public boolean contains(E elem) { 
    int compare = elem.compareTo(value); //here we compare the element with 
             //the compareTo method that the objects 
             //used must redefined 

    if(compare==0) 
      return true; //here the current node contains elem ! 
     else if(compare < 0) 
      return left.contains(elem); //elem is inferior than the elem present in the current node hence we look into the left part of the tree 
     else 
      return right.contains(elem); //elem is superior than the elem present in the current node hence we look into the right part of the tree 
    } 

, 우리는 마지막에 Leaf에있을 것입니다 그리고 그것은 false를 반환합니다.

당신은 요소 (왼쪽 또는 오른쪽) add 및 remove

Answer 2

가 어떻게 그것의 좋은 부분을 조사하기 위해 내 나무로 말할 수있는 코드에 동일한 로직을 구현 할 수 있습니까?

글쎄, 당신은 value이 compareTo을 사용하여 elem을 비교해야합니다. 결과가 0이면 값이 이미 동일하므로 true을 반환 할 수 있습니다.

elem이 value보다 작은 경우 left.contains(elem)으로 재발행 할 수 있으며 그렇지 않은 경우 right.contains(elem)으로 재발행 할 수 있습니다. left 또는 right 값이 리프 일 경우 false을 반환합니다. 그렇지 않으면 적절하게 다시 계산됩니다.