java - 在 Java 中搜索树中的节点

Question

我有一个二叉树，使用以下构造函数:

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

其中 c1 是左 child ，c2 是右 child 。

我想编写一个在最大代内搜索特定名称的方法。比如 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，因此根本不需要 depth 变量:当 maxGeneration == 0 时，您不再搜索并返回 null。

至于你的其他问题，不是直接返回 child1.depthFirstSearch(...) 的值，而是将值存储在一个临时变量中。如果不为null，则找到节点，立即返回，否则继续在child2下查找。

---

更新:

应该是if (maxGeneration >= 1) ...(大于或等于)，否则最后一次调用maxGeneration == 1总是会返回无效的。或者，您可以只检查 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;