布尔递归

Question

试图写一个布尔方法,告诉某人是否是某人的后裔......但似乎无法做到这一点.当然,如果它是一个孩子......或者是孩子的后代,那么这个物体就是后代.

public boolean isDescendant(member x){
    if (children.contains(x)){
        return true;
    }
    else{
        return false;
    }
}

但我在哪里或如何插入:

for (int i = 0; i < children.size(); i++){
    isDescendant(children.get(i));
}

谢谢!

Answer 1

我想你想要的是:

// Cleaned up version
public boolean isDescendant(member x){
    // check for direct descendance 
    if (children.contains(x)){
        return true;
    }
    // check for being descendant of the children
    for (Child c: children){
        if (children.get(i).isDescendant(x)) {
            return true;
        }
    }
    return false;
}

Answer 2

树木向下行走的速度非常慢（从根部到叶子）。考虑 is-ancestor 检查的这种实现：

/**
 * Checks whether the given node is an ancestor of this node.
 */
public boolean isDescendantOf(Node ancestor) {
    Preconditions.checkNotNull(ancestor, "Ancestor");
    if (equals(ancestor)) {
        // every node is an ancestor to itself
        return true;
    } else if (parent == null) {
        // not related
        return false;
    } else {
        // recursive call
        return parent.isDescendantOf(ancestor);
    }
}

另一种方式现在是小菜一碟。

public boolean isDescendant(Node descendant) {
    return descendant.isDescendantOf(this);
}

没有循环，没有指数级的努力。

PS：
在我的示例中，我建议重命名isDescendant为isAncestorOf.