java 布尔递归

boolean recursion

提问by user618712

trying to write a boolean method that tells if someone is a decendant of someone...but can't seem to do it. of course, the object is a descendant if it's a child...or the descendant of a child.

试图编写一个布尔方法来判断某人是否是某人的后代……但似乎无法做到。当然，如果对象是一个孩子……或者一个孩子的后代，那么它就是一个后代。

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

but where or how do i insert:

但是我在哪里或如何插入：

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

thanks!

谢谢！

采纳答案by whiskeysierra

Walking trees is very slow downwards (from the root to the leaves). Consider this implementation for the is-ancestor check:

向下行走的树木非常缓慢（从根到叶）。考虑这个用于 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);
    }
}

The other way is now a piece of cake.

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

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

No loops, no exponentional effort.

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

PS:
In my example i would suggest renaming isDescendantto isAncestorOf.

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

回答by jjnguy

I think what you want is below:

我认为您想要的是以下内容：

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

回答by Stefan Kendall

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

You need to recurse over the current root, most likely.

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

回答by Pa?lo Ebermann

Edit:If your data structure has parent pointers, use these instead of searching your descendants in the tree. If not, consider adding them. See the answer from whiskeysierra for a solution with parent pointers. Only if adding them is not possible, consider this answer.

编辑：如果您的数据结构具有父指针，请使用它们而不是在树中搜索您的后代。如果没有，请考虑添加它们。有关父指针的解决方案，请参阅whiskeysierra 的答案。只有在不可能添加它们时，才考虑这个答案。

---

---

The current answers all have two loops through children (one in children.contains(), one later).

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

This variant may be a bit more efficient (but it does not change the O-class), and is a bit shorter. (If children is a set with fast contains-check (like HashSet) and often the hierarchy is not so deep (so you don't need to recurse at all), the other answers are better.)

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

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

If a node is considered a descendant of itself, you can write it like this:

如果一个节点被认为是它自己的后代，你可以这样写：

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