java - 二叉搜索树 字符串搜索

Question

我有一个程序，我需要在二叉树中搜索特定单词，我为字符串搜索方法编写的代码不起作用。如果有人可以看一下我将不胜感激。

我尝试了一些修改，但仍然不起作用。

public boolean check(BSTNode t,String key){
    if(!t.word.equals(key)){
        check(t.left,key);
        check(t.right,key);
    }
    else{
        return true;
    }
    return false;
}

Answer 1

可以这样写；

public boolean check(BSTNode t,String key) {
    return 
      t.word.equals(key) || check(t.left,key) || check(t.right,key)
}

或者，更详细地说；

public boolean check(BSTNode t,String key) {
    if (t.word.equals(key)) return true;

    if (check(t.left,key)) return true;

    if (check(t.right,key)) return true;

    return false;
}

您不需要大量 else 语句，因为 return 语句会停止函数中的执行。

编辑:

您还必须检查您的 BSTNode 是否不为 null，否则当您到达树的末尾时，您将得到空指针异常。这可以在函数开始时完成，或者在内部递归 check 调用之前完成:

public boolean check(BSTNode t,String key) {

    if (t == null) return false;

    if (t.word.equals(key)) return true;

    if (check(t.left,key)) return true;

    if (check(t.right,key)) return true;

    return false;
}

或者；

public boolean check(BSTNode t,String key) {
    if (t.word.equals(key)) return true;

    if (t.left != null && check(t.left,key)) return true;

    if (t.right != null && check(t.right,key)) return true;

    return false;
}