boolean Rekursion

beim schreiben einer booleschen Methode, dass man sagt, wenn jemand eine decendant von jemanden...aber kann nicht scheinen, es zu tun. natürlich, das Objekt ist ein Nachfahre wenn es ein Kind...oder ein Nachkomme, ein Kind.

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

aber wo oder wie kann ich das einfügen:

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

Dank!

  • Sie habe noch nicht gesagt, ob die Knoten bilden eine zyklische Kurve oder eines DAG / Baum, und ob ein Kind-Knoten hat eine Verbindung zu seinem übergeordneten Knoten.
InformationsquelleAutor user618712 | 2011-02-16
  1. 4

    Walking Bäume sehr langsam nach unten (von der Wurzel zu den Blättern). Betrachten Sie diese Umsetzung für die ist-Vorfahr-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);
    }
}

    Der andere Weg ist jetzt ein Stück Kuchen.

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

    Keine Schleifen, keine exponentional Aufwand.

    PS:

    In meinem Beispiel würde ich vorschlagen, umbenennen isDescendant zu isAncestorOf.

    • Natürlich funktioniert dies nur, wenn der Knoten einen Zeiger auf Ihre Eltern. (Wenn Sie nicht haben, ist es eine überlegung Wert hinzufügen, wenn man diese braucht isDescendantOf öfter als einmal.)
    InformationsquelleAutor whiskeysierra
  2. 5

    Ich denke, was Sie wollen, ist unten:

    //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;
}
    • das Tat ich dann auch zuerst...aber ich begann zu versuchen, zu Folgen, es in meinem Kopf aus und begann es zu keinen Sinn machen. aber vielleicht war es rechts?
    • Ist es abends hier oder isDescendant(children.get(i)) wird immer wahr? Meinst du children.get(i).isDescendant(x)?
    • du hast Recht, habe ich geändert.
    • haben Sie diese getestet. Es sieht zumindest meistens die richtige für mich.
    • Nur ästhetik, aber Sie können loszuwerden, die "else" und wahrscheinlich noch eine für-jeden statt. 🙂
    • diese Lösung prüft nur 2 Ebenen von Kindern (direkte und Kind, des Kindes). Aber ich denke, die Frage war über alle Ebenen (wenn einige Kind von einer beliebigen Ebene ist gleich x, dann x ist Nachkomme)
    • dies wird recurse, weil der Aufruf isDescendant wird dann überprüfen Sie die nächste Kinder-Kinder, und so weiter.
    • ja, ich denke, das sieht hässlich auch. Aber ich habe versucht, den code so ähnlich wie die OP wie möglich.

    InformationsquelleAutor jjnguy
  3. -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;
}

    Müssen Sie recurse über die aktuellen root, wahrscheinlich.

    • Sie ändern könnte, dass dies eine member-Funktion durch entfernen der iteration fo aktuellen root und ruft isDescendant auf jedes child-element. Ich denke, es ist klarer als ein funktionales Konzept, aber.
    InformationsquelleAutor Stefan Kendall
  4. -1

    Edit: Wenn Sie Ihre Daten-Struktur hat parent-Pointer, verwenden Sie diese statt suchen Ihre Nachfahren im Baum. Wenn nicht, sollten Sie Sie hinzufügen. Siehe die Antwort von whiskeysierra für eine Lösung mit parent-Zeigern. Nur, wenn Sie Sie hinzufügen ist nicht möglich, sollten Sie diese beantworten.

    Aktuelle Antworten alle haben zwei Schleifen durch Kinder (eines in children.contains() man später).

    Diese Variante ist vielleicht ein wenig effizienter (aber es ändert sich nicht die O-Klasse), und ist ein wenig kürzer. (Wenn die Kinder einen Satz mit fast enthält-check (wie HashSet) und oft ist die Hierarchie ist nicht so tief (so dass Sie nicht brauchen, um recurse an alle), die anderen Antworten sind besser).

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

    Wenn ein Knoten wird als ein Nachkomme von sich selbst, Sie können schreiben Sie es so:

    public boolean isDescendant(Member x) {
   if(equals(x))
      return true;
   for(Member child : children) {
      if(child.isDescendant(x))
        return true;
   }
   return false;
}
    InformationsquelleAutor Paŭlo Ebermann
Schreibe einen Kommentar