Реализация двоичного дерева поиска - Содержит метод

Question

В настоящее время у меня есть 3 класса - 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 никогда не возвращает истину, и я не могу понять, почему. Если вы хотите больше узнать о моем коде или больше информации, пожалуйста, не стесняйтесь спрашивать.

Answer 1

В вашем contains методе BSTNode «s, вы не обращая внимания на результаты вызова contains на left и right. Если дочерний узел нашел его, немедленно отправьте 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; 
}