布尔递归

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。

Answer 3

public boolean isDescendant(member currentRoot, member x){
    //check the current level
    if (currentRoot.children().contains(x)){
        return true;
    }

    //leaf
    if( currentRoot.children().isEmpty() ){ return false; }

    //try all my children
    boolean found = false;
    for( Member child : currentRoot.children() ){
       found = isDescendant( child, x );
       if( found ) break;
    }

    return found;
}

您很可能需要递归当前的根。

Answer 4

编辑：如果您的数据结构有父指针，请使用这些指针而不是在树中搜索您的后代。如果没有，请考虑添加它们。请参阅威士忌塞拉 (whiskysierra) 的答案，了解带有父指针的解决方案。仅当无法添加它们时，才考虑这个答案。

---

当前的答案都有两个通过子项的循环（一个在 children.contains() 中，一个在后面）。

这个变体可能更高效一些（但它不会改变 O 级），并且更短一些。 （如果children是一个具有快速包含检查的集合（如HashSet），并且层次结构通常不是那么深（因此您根本不需要递归），那么其他答案更好。）

public boolean isDescendant(Member x) {
   for(Member child : children) {
      if(child.equals(x) || child.isDescendant(x))
        return true;
   }
   return false;
}

如果一个节点被认为是后代就其本身而言，你可以这样写：

public boolean isDescendant(Member x) {
   if(equals(x))
      return true;
   for(Member child : children) {
      if(child.isDescendant(x))
        return true;
   }
   return false;
}