java - 使用 Java 在 BST 中搜索单词

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;