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 KnotenB

    Die 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,23

    Manuell ausprogrammieren geht recht leicht,
    aber ist für eine größere Tiefe als 2 ziemlich ... Zach 😉

    Wie 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?

    * http://de.wikipedia.org/wiki/Binärbaum#Traversierung



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


Log in to reply