java - 递归搜索未排序的树

Question

我正在尝试在树中搜索元素 e，但是如您所见，我的搜索 (Position,E) 没有返回 Position。但是，当我添加“return null;”时在方法的最后。它仅在我要查找的 Position 位于其父项的最左侧子项时有效，否则返回 null。我怎样才能让它一直工作直到它到达树的尽头？

public Position<E> search(E e) {
    return search(root(), e);
}

public Position<E> search(Position<E> p, E e) {
    if(p.getElement().equals(e))
        return p;
    for(Position<E> c: children(p))
            return search(c, e);
}

Answer 1

我认为问题出在这个循环中:

for(Position<E> c: children(p))
        return search(c, e);

假设您要搜索的元素位于节点的第二个子节点中，而不是第一个。使用上面的代码，在循环的第一次迭代中，您将递归地探索返回 false 的第一个 child ，然后立即返回 false，而没有机会探索第二个 child 。换句话说，您的方法只查看第一个 child ，因此它可能找不到您要查找的内容。

要解决这个问题，请尝试像这样重写代码:

if(p.getElement().equals(e))
    return p;

for(Position<E> c: children(p)) {
    Position<E> result = search(c, e);
    if (result != null) return result;
}
return null;

这使得在每个子树中进行递归调用。如果任何一个调用未能找到该元素，那很好 - 您只需继续下一个。如果任何一个调用确实找到了该元素，则将其返回。如果所有调用均未找到该元素，则返回 null 以指示失败。

希望这对您有所帮助!