使用 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;

使用 Java 在 BST 中搜索单词

Search about word in BST using Java

java

binary-search-tree