이진 검색 트리 구현 - 메서드 포함

Question

현재 DictionaryApp, BSTSet 및 BSTNode의 세 클래스가 있습니다. BSTSet과 BSTNode에 모두 메서드가 있습니다.

public class BSTSet <E extends Comparable<E>> extends AbstractSet <E> { 

    // the root of the supporting binary search tree 
    private BSTNode<E> root; 

    // number of elements in the set 
    private int count = 0; 


    public boolean isEmpty() { 
     return count == 0; 
    } 


    public boolean contains(E item) throws ClassCastException { 
     if(root == null) return false; 
     return root.contains(item); 
    } 

    public boolean add(E item) { 
     if (item == null) 
      throw new IllegalArgumentException("Null cannot be added to a BSTSet"); 
     if(contains(item))return false; 
     if(root == null){ 
      root = new BSTNode(item); 
      count++; 
      return true; 
     }else{ 
      root.add(item); 
      count++; 
      return true; 
     } 
    } 
} 


public class BSTNode <E extends Comparable<E>> { 

    private E value; 
    private BSTNode<E> left; 
    public BSTNode<E> right; 

    public BSTNode(E value) { 
    this.value = value; 
    } 

    public E getValue() { 
     return value; 
    } 

    public BSTNode<E> getLeft() { 
     return left; 
    } 

    public BSTNode<E> getRight() { 
     return right; 
    } 


    public boolean contains(E item) { 
     if(item.compareTo(value) == 0) return true; 
     if(left != null) left.contains(item); 
     if(right != null) right.contains(item); 
     // no matching node was found 
     return false; 

    } 

    public boolean add(E item) { 
     if(item.compareTo(value) < 0) {left = new BSTNode(item); return true;} 
     if(item.compareTo(value) > 0) {right = new BSTNode(item); return true;} 
     return false; 
    } 
} 

내 문제는 BSTNode 클래스의 contains 메소드가 절대로 true를 반환하지 않으며 이유를 이해할 수 없다는 것입니다. 더 이상 내 코드를 보거나 더 이상 정보가 필요하면 언제든지 물어보십시오. 당신의 BSTNode의 contains 방법에서

Answer 1

, 당신은 left 및 right에 contains를 호출의 결과를 무시하고있다. 자식 노드가 찾은 경우 즉시 true을 반환하십시오. 또한 비교 결과를 사용하여 다음에 검색 할 아동을 결정하십시오.

public boolean contains(E item) { 
    int comp = item.compareTo(value); 
    if(comp == 0) return true; 
    if(comp < 0 && left != null && left.contains(item)) return true; 
    if(comp > 0 && right != null && right.contains(item)) return true; 
    // no matching node was found 
    return false; 
} 

add 메서드는 이미 존재할 수있는 자식 노드를 무시합니다. 그들의 존재를 먼저 테스트하십시오. 존재하지 않는다면 이미하고있는 것처럼 할당하십시오. 이들이 이미 존재하면 그 자식에 대해 재귀 적으로 add을 호출하십시오.

public boolean add(E item) { 
    if(item.compareTo(value) < 0) { 
     if (left == null) left = new BSTNode(item); return true; 
     else return left.add(item); 
    } 
    if(item.compareTo(value) > 0) { 
     if (right == null) right = new BSTNode(item); return true; 
     else return right.add(item); 
    } 
    return false; 
}