Поиск о словах в BST с использованием Java

Question

Я хочу проверить, существует ли слово в BST или нет.

Существует ошибка это дает мне false всегда:

if(listOfWords.contain(word)) 
write.print(word+" "); 
// using this method but it does not work 

private boolean contain(englishWord list, String word) { 
    if (list != null) { 
     contain(list.getLeft(), word); 
     if (word.equals(list.getWord())) { 
      return true; 
     } 
     contain(list.getRight(), word); 
    } 
    return false; 
} 

Answer 1

Ваше return true заявление теряется до порядка в рекурсии.

Вы можете использовать что-то вроде,

if (list != null) { 
    if (word.equals(list.getWord()) || contain(list.getLeft(), word) || contain(list.getRight(), word)) { 
     return true; 
    } 
} 
return false; 

Но это займет O(n) временную сложность. И BST разработан, чтобы дать гораздо лучшие результаты, чем это.

Если ваш BST устроен так, как должно быть, что-то подобное должно работать (и будет более эффективным, чем ваш алгоритм).

if (list != null) { 
    int compare = word.compareTo(list.getWord()); 
    if (compare == 0) { 
     return true; 
    } else if (compare > 0) { 
     return contain(list.getRight(), word); 
    } else { 
     return contain(list.getLeft(), word); 
    } 
} 
return false;