递归搜索未排序的树

Question

我正在尝试在树中搜索元素 e，但是如您所见，我的搜索 (Position,E) 没有 return 位置。但是，当我在方法末尾添加 "return null;" 时。它仅在我要查找的 Position 位于其父项的最左侧子项时有效，否则 returns 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);

假设您要搜索的元素位于节点的第二个 child 而不是第一个。使用上面的代码，在循环的第一次迭代中，您将递归地探索第一个 child，其中 returns false，然后立即 return 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;

这使得在每个子树中进行递归调用。如果任何一个调用未能找到该元素，那很好 - 您只需继续下一个。如果任何一个调用确实找到了该元素，您 return 它。如果 none 次调用找到了元素，那么你 return null 表示失败。

希望对您有所帮助！

Answer 2

您需要跟踪每个子树及其 return 值。尝试如下操作：

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)) {
        Position tmp = search(c, e);
        if (tmp != null) {
            return tmp;
        }
    }
    return null;
}

谢谢，

尤里

递归搜索未排序的树

Searching in a unsorted tree recursively

java

algorithm

tree

data-structures