Alle Elemente einer Ebene aus einem Baum konstrukt
-
Hi,
Ich habe eine baumähnliche Struktur.
Es gibt zwei Knoten-Typen (abgeleitet von der Klasse KnotenBase):
KnotenA -> hält ein paar strings
KnotenB -> hält Strings + eine List<KnotenBase> die enthält KnotenA und oder KnotenBDie Root ist kein Knoten sondern auch eine Liste: List<KnotenBase>
Jetzt möchte Ich eine Methode Schreiben der ich das Konstrukt (also die "Root-Liste") und einen Int mit gebe, die mir die Ebene definiert die ich haben will.
Als Rückgabe will ich eine Liste mit den Knoten der gewünschten Ebene (aus dem Int).List<KnotenBase> GetLevelFromTree(List<KnotenBase> tree, int i);
Mit i = 0 müsste nichts gemacht werden, und der tree direkt zurückgegebenw erden.Mit dem Baum als Beispiel:
http://upload.wikimedia.org/wikipedia/commons/6/61/Pseudobinärersuchbaum.svg
(Wobei es eben kein Binär-Baum ist wie in dem Beispiel)
i=0: 15
i=1: 5, 16
i=2: 3, 12, 20
i3=: 10,13,18,23Manuell ausprogrammieren geht recht leicht,
aber ist für eine größere Tiefe als 2 ziemlich ... ZachWie kann man sowas generisch machen ...
-
Hmm, Du suchst Dir eine Möglichkeit aus den Baum zu durchlaufen* (z.B. depth-first) und führst eine Ergebnisliste sowie die aktuelle Tiefe als Parameter der rekursiven Funktion mit. Falls die Zielebene erreicht ist, gehören die Knoten zur gesuchten Liste und deren Kinder werden nicht weiter untersucht.
Wo genau liegen die Schwierigkeiten?
-
Hmmm dachte es gibt da eine elegante "Standard-Lösung".
Naja auch hab ich selber nicht daran gedacht die Ergebnis liste "mit zu nehmen" ...
Danke.