versucht eine boolesche Methode zu schreiben, die sagt, ob jemand ein Nachfahre von jemandem ist ... aber es scheint nicht so zu sein. Natürlich ist das Objekt ein Nachkomme, wenn es ein Kind ist ... oder der Nachkomme eines Kindes.
%Vor%aber wo oder wie füge ich ein:
%Vor%Danke!
Walking Bäume ist sehr langsam nach unten (von der Wurzel bis zu den Blättern). Betrachten Sie diese Implementierung für die Is-Vorfahrenprüfung:
%Vor%Der andere Weg ist jetzt ein Stück Kuchen.
%Vor%Keine Schleifen, kein exponentieller Aufwand.
PS:
In meinem Beispiel würde ich vorschlagen, isDescendant in isAncestorOf umzubenennen.
Sie müssen höchstwahrscheinlich über die aktuelle Wurzel rekurrieren.
Bearbeiten: Wenn Ihre Datenstruktur übergeordnete Zeiger hat, verwenden Sie diese, anstatt Ihre Nachkommen in der Baumstruktur zu suchen. Wenn nicht, sollten Sie sie hinzufügen. Eine Lösung mit Elternzeigern finden Sie in der Antwort von whiskiesierra. Nur wenn das Hinzufügen nicht möglich ist, berücksichtigen Sie diese Antwort.
Die aktuellen Antworten haben alle zwei Schleifen durch Kinder (eins in children.contains() , eins später).
Diese Variante mag etwas effizienter sein (ändert aber nicht die O-Klasse) und ist etwas kürzer. (Wenn Kinder ein Set mit schnellem contains-check (wie HashSet) ist und die Hierarchie oft nicht so tief ist (so dass Sie überhaupt nicht recursen müssen), sind die anderen Antworten besser.)
%Vor%Wenn ein Knoten als ein Nachkomme von sich selbst betrachtet wird, können Sie ihn wie folgt schreiben:
%Vor%