在 Binary Tree Java 中查找并返回一个节点

Question

嗨，我正在尝试找到一个等于参数给出的字符串的节点并返回该节点。我的结构是字符串的二叉树。我们假设搜索的字符串存在。

var q 被初始化为树的根。（在我调用方法查找的函数中）

private NodeTree find(NodeTree q, String cont){
   if(q._contingut.equals(cont)) return q;
   else {
       if(q._left!=null) return find(q._left,cont);
       else if(q._right!=null)return find(q._right,cont);
   }
   return null;
} 

Answer 1

在 find（） 函数的第 4 行中，您不应该返回对左侧子树进行递归调用的结果。相反，如果从左侧子树中获得"NULL"，则应在右侧子树中搜索字符串。

这是更新的代码

private NodeTree find(NodeTree q, String cont){
   if(q==NULL) return NULL;
   if(q._contingut.equals(cont)) return q;
   NodeTree result = NULL;
   if(!q._left) result = find(q._left,cont);
   if(!result && q._right) result = find(q._right,cont);
   return result;
} 

Answer 2

如果您的 BST 构建正确，您需要决定查找位置（左侧或右侧子树）将当前节点值与查询值进行比较，如下所示：

NodeTree find(NodeTree q, String query) {
   if(q.value.equals(query)) 
       return q;
   else if (q.value.compareTo(query) > 0) 
       return q.left == null ? null : find(q.left, query);
   else
       return q.right == null ? null : find(q.right, query);
}