布尔递归

试图写一个布尔方法，告诉如果某人是某人的后代...但似乎无法做到这一点。当然，如果它是一个孩子......或者孩子的后代，那么这个对象就是后代。布尔递归

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)); 
}

的感谢！

来源

2011-02-16 user618712

您还没有说过节点是形成循环图还是DAG /树，以及子节点是否有连接到其父节点的链接。 – 2011-02-16 16:41:17

行走的树木向下很慢（从根部到树叶）。考虑为祖先检查执行此操作：

/** 
* 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。

来源

2011-02-17 00:25:48 whiskeysierra

我想你想要的是如下：

// 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; 
}

来源

2011-02-16 16:21:43 jjnguy

这就是我在开始时所做的......但我开始试图在我的脑海中遵循它，并且它开始没有意义。但也许是对的？ – user618712 2011-02-16 16:23:00

晚上在这里还是`isDescendant（children.get（i））`将永远是真的？你是不是指`children.get（i）.isDescendant（x）`？ – 2011-02-16 16:23:25

@Alex，你是对的，我改变了。 – jjnguy 2011-02-16 16:24:10

-1

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; 
}

您需要递归在当前根，最有可能的。

来源

2011-02-16 16:25:13

-1

编辑：如果你的数据结构有父指针，使用这些而不是在树中搜索你的后代。如果不是，请考虑添加它们。使用父指针查看whiskeysierra的解答。只有添加它们是不可能的，请考虑这个答案。

目前的答案都必须通过孩子两个循环（一个在children.contains()，一个更高版本）。

这个变种可能更有效一些（但它不会改变O-class），并且有点短。（如果孩子是一组具有快速包含支票（如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; 
}

来源

2011-02-16 17:03:20

回答

相关问题