boolean recursion

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)){
      开发者_如何学C  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!

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

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

/**
 * 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 isDescendant to isAncestorOf.

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.

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.

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

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.)

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