二进制搜索树字符串搜索

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; 
} 

因为return报表功能停止执行，你不需要很多的else声明。

编辑：

您还必须检查你的BSTNode不为空，或者当你到达树的最后，你会得到空指针异常。这可能在函数的开始做，或之前内部递归调用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; 
}