recursividad booleana

Question

tratando de escribir un método booleano que diga si alguien es descendiente de alguien ... pero parece que no puede hacerlo. por supuesto, el objeto es un descendiente si es un niño ... o el descendiente de un niño.

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

pero dónde o cómo puedo insertar:

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

gracias!

Answer 1

árboles que caminan hacia abajo es muy lento (desde la raíz hasta las hojas). Considere esta implementación para la verificación is-ancestro:

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

La otra forma es ahora un pedazo de pastel.

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

Sin vueltas, sin esfuerzo exponencial.

PS:
En mi ejemplo, yo sugeriría cambiar el nombre de isDescendant a isAncestorOf.

Answer 2

Creo que lo que quiere es a continuación:

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

Es necesario recursivo sobre la raíz actual, lo más probable.

Answer 4

Editar: Si su estructura de datos tiene punteros padres, utilícelos en lugar de buscar sus descendientes en el árbol. Si no, considere agregarlos. Vea la respuesta de whiskeysierra para una solución con sugerencias para padres. Solo si agregarlos no es posible, considere esta respuesta.

---

Las respuestas actuales tienen dos bucles a través de los niños (uno en children.contains(), uno más tarde).

Esta variante puede ser un poco más eficiente (pero no cambia la clase O), y es un poco más corta. (Si los niños es un conjunto con rápida contiene-cheque (como HashSet) y, a menudo la jerarquía no es tan profunda (por lo que no es necesario en absoluto recursivo), las otras respuestas son mejores.)

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

Si un nodo se considera un descendiente de sí mismo, puede escribir así:

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