在Java中搜索树中的节点

Question

我有一个使用以下构造函数制作的二叉树：

public Person(String name, int age, char gender, Person c1, Person c2)

其中 c1 是左子树，c2 是右子树。

我想编写一个在最大代内搜索特定名称的方法。就像 a.depthFirstSearch(Eva, 1); 一样，其中 Eva 是要搜索的名称，1 是我可以查看的最大代数（或级别）。

这是我所拥有的： 编辑：

public Person depthFirstSearch(String name, int maxGeneration)
{
    {
Person temp;
if (maxGeneration>1){
    if (this.name.equals(name)){
        temp=this;
        return temp;
        }
    else{
    if (child1!=null)
        temp=child1.depthFirstSearch(name, maxGeneration-1);
    if (child2!=null)
        temp=child1.depthFirstSearch(name, maxGeneration-1);
    }
}   
return null;
}
}

这里有两个问题。我认为每次函数调用自身时深度都会重置为 0，所以我知道我可以在其他地方跟踪深度或找到替代方案。我认为另一个问题是 child2 从未真正到达，因为我在 child1 处返回。我不太确定这是如何工作的，所以如果有人能解释一下，那就太好了。对一些修复有什么建议吗？

另外，我被告知我必须首先搜索深度，这意味着首先研究更深的几代。我不太确定这意味着什么以及它与我在实现中使用的逻辑有何不同。

Answer 1

由于您在每次递归调用中递减 maxGeneration，因此您根本不需要 深度 变量：当 maxGeneration == 0 时，您根本不需要不再搜索并返回null。

至于您的其他问题，不要直接返回 child1.depthFirstSearch(...) 的值，而是将该值存储在临时变量中。如果不为null，则说明已找到该节点，因此立即返回该节点，否则继续在child2下搜索。

---

更新：

应该是if (maxGeneration >= 1) ...（大于或等于），否则最后一次调用maxGeneration == 1 将始终返回 null。或者，您可以只检查 0 并返回 null：

if (maxGeneration == 0)
  return null;

// rest of your code

此外，您仍然没有使用返回值来检查该节点是否确实在左子树中找到。现在，即使您找到 child1 下的节点，您仍然会在 child2 下查找，最终将返回 null，这是错误的。仅当左侧搜索返回 null 时，才需要在 child2 下搜索：

Person temp;
if (child1 != null) {
  temp = child1.depthFirstSearch(name, maxGeneration-1);
  if (temp != null)
    return temp; // found the node, just return
}
// otherwise the following code will execute
if (child2 != null) {
  temp = child2.depthFirstSearch(name, maxGeneration-1);
  if (temp != null)
    return temp; // found the node, just return
}
// didn't find node under either child
return null;