Baumstruktur zusätzlich ebenenweise repräsentieren

[shark95]

Hallo!

Ich habe mir eine Baumstruktur programmiert, welche folgendermaßen aussieht: Ich habe eine Knotenklasse, welche eine ArrayList<Knoten> "kinder" enthält. Im Konstruktor werden diese Kinder rekursiv befüllt und der Baum ist dann komplett vorhanden. Ich hätte jetzt gerne, dass ich jede Ebene des Baumes zusätzlich noch in einer ArrayListe habe. Bis jetzt bin ich nur auf die Idee gekommen, eine Klassenvariable static ArrayList<Knoten> zu erzeugen und diese dann (ebenfalls im Konstruktor) zu befüllen. Es funktioniert zwar, aber irgendwie stört es mich, dass ich hier in der Knotenklasse eine Klassenvariable verwende (ich finde, es ist kein guter Programmierstil, oder was glaub ihr?) Habt ihr eventuelle eine bessere Lösung? Ich habe das bis jetzt nur mit einer Ebene versucht, ich würde dann für alle weiteren Ebenen ebenfalls eine ArrayList verwenden oder eventuell eine Arraylist aus Arraylisten.

Außerdem muss ich noch feststellen, in welche Ebene ich nun beim Aufruf des Konstruktors aktuell befinde. Da fällt mir auch nur eine Integer Klassenvariable ein, welche inkrementiert bzw. dekrementiert wird. Das finde ich aber auch nicht sonderlich toll programmiert....

Würde mich über ein paar Hinweise freuen

lg

 

[XHelp]

Eine Ebene noch mal extra im Objekt zu haben ist eigentlich nicht sinnvoll, da es redundant ist. Du kannst dir aber eine Methode für den Baum machen, die dir eine List<Knoten> für die Ebene n ausliest und zurückliefert.

 

[shark95]

Vielen Dank für die Antwort! Das würde im Prinzip gehen, jedoch wird der Baum am Beginn des Programms aufgebaut und da der Baum sehr groß ist, wollte ich ein anschließendes darüber iterieren vermeiden.

Was meinst du damit, dass es redundant ist? Ich dachte, wenn ich im Konstruktor einen neuen Kindknoten erzeuge und diesen dann zur ArrayList<Knoten> hinzufüge, dass intern nur eine Referenz auf das Objekt zeigt. Sprich wenn ich noch eine Liste mit dem Objekt befülle, dass diese dann beide auf das gleiche Objekt zeigen?!

 

[XHelp]

Naja, was ist, wenn du einen Knoten löschst? Dann musst du ihn auch aus der Ebene löschen. Und generell gewinnst du durch die Ebenen keine neuen Informationen.
Wie groß ist denn der Baum? Und vor allem: wie oft brauchst du denn eine ganze Ebene?

 

[shark95]

Nach dem Erstellen des Baums werden keine Knoten hinzugefügt oder entfernt. Ziel ist es die einzelnen Ebenen schnell abzufragen (bzw. auszugeben) und zu jedem Element in einer Ebene den Teilbaum aufzubauen.

 

[XHelp]

Bleibt die Frage nach der Größe.
Bist du dir sicher, dass dsa auslesen einer Ebene ein Flaschenhals ist?

 

[shark95]

Ach ja: Größe des Baums befndet sich zurzeit bei insgesamt ca. 2000 Knoten/Blätter werden aber noch mehr, ich schätz mal maximal 5000. Was meinst du mit dem Flaschenhals?

Also nochmals zusammengefasst: Du glaubst, die beste Art die Ebenen zu bekommen ist, einfach den Baum nochmals durch zuiterieren?

 

[XHelp]

Ein Binärbaum mit 5000 Blätter hat ca 12 Ebenen. Kommt natürlich drauf an wie dein Baum aussieht, aber der Aufwand sieht überschaubar aus.
Mach doch einfach eine Methode, die dir aus der Baumstruktur on-fly eine Ebene X ausließt und arbeite damit. Wenn du merkst, dass es viel zu lange dauert, kannst du ja immer noch überlegen.

 

[shark95]

Alles klar, danke! Aber ich habe keinen Binärbaum, sondern einfach eine Baumstruktur. Zurzeit habe ich 4 Ebenen. Ich werds mal so versuchen!

 

[XHelp]

Ja gut, je breiter der Baum ist, desto mehr Pfade musst du besuchen um eine komplette Ebene auszulesen. Aber dennoch lässt sich der Aufwand imho bei diesen Größen vernachlässigen