Wie kann man einen binären Baum in ein Array umwandeln und wieder in ursprünglicher Form zurück?

Gibts dazu vielleicht irgendeine Traversierungsmethode?

Answer 1

[greyhead]

Meiner Meinung nach liegt der Knackpunkt in der Array-Repräsentation des bin. Baumes, die sicherlich ohne zusätzliche Hilfsarrays, die parent-Referenzen o.ä. enthalten, auskommen soll.

So etwas habe ich hier gefunden: http://www.cogs.susx.ac.uk/courses/dats/notes/html/node79.html

Der Baum wird also mit dem breadth-first-Verfahren traversiert und im Array abgelegt.

Aus dem Array wird der bin. Baum durch die übliche insert-Methode rekonstruiert.

.
Oder habe ich etwas übersehen? Weil nur scharf nachgedacht und nicht mit Programm getestet...

Comments

[giga4meyou]

Ist das breadth-first-Verfahren das gleiche wie Inorder ( http://de.wikipedia.org/wiki/In-order ) wenn ja geht es so nicht.

[greyhead]

@giga4meyou

Breadth-first ist level-order (nach Deinem wikipedia-link).

[giga4meyou]

@greyhead

Ne, dass geht leider auch nicht, habe ich auch schon probiert.

[greyhead]

@giga4meyou

Hmmm. Muss ja ein komischer Baum sein. Ist er vielleicht nur von der Form her binär? Und die Schlüssel im linken Unterbaum nicht immer kleiner bzw. im rechten Unterbaum nicht immer größer?

[giga4meyou]

@greyhead

Ach sory, habe ich ganz vergessen zu sagen es handelt sich um einen binären Suchbaum. Also es trifft genau zu was du gesagt hast. Wobei nicht alle Knoten(auch innere Knoten) vollständig ausgefüllt sein müssen.

[greyhead]

@giga4meyou

Hätte ich ja auch vorher fragen können. Wenigstens hatte ich richtig geraten (uff, schwitz).
Und bei meinem schnell hingeschmierten Testprogramm funktioniert natürlich alles prima.
Basis: http://rosettacode.org/wiki/Tree_traversal#Java

[greyhead]

@greyhead

Oh, ein Jubiläumsstern (mein 50.) für eine interessante Frage. Vielen Dank.

Answer 2

[freejack1982]

BinBaum -> Array: Durchlaufe den binären Suchbaum mit dem Breitendurchlauf. In dieser Reihenfolge kopierst bzw. verweist du die Knoten aufsteigend in das Array. Der Baum wird sozusagen "eingerollt" von links nach rechts, zeilenweise.

Array -> BinBaum: Durchlaufe das Array iterativ vom Anfang bis Ende. Baue den binären Baum sukzessive durch eine einfache insert-Operation wieder auf. Der Baum wird wieder "aufgerollt", indem die Knoten ähnlich dem Breitendurchlauf in den Baum eingefügt werden. Es ergibt sich inbesondere die alte, selbe Anordnung der Knoten.

Beziehung parent node und child node im Array:

rank(linkerSohn) = 2 * rank(Vater)

rank(rechterSohn) = 2 * rank(Vater) + 1

wobei gilt: rank = array_index + 1

Answer 3

[hoehlenknarf]

Kann man z.B. durch Rekursion lösen. Oder suche mal nach Implementierungen von Iteratoren.

Noch ein Hinweis beim Weg zurück vom Array zum Binärbaum: Die Einfüge-Reihenfolge ist wichtig.

Comments

[giga4meyou]

Soweit bin ich auch schon!

[hoehlenknarf]

@giga4meyou

Sorry fürs Überhaupt-Antworten! 10 Sek Google: http://de.wikibooks.org/wiki/JavaStandard:Muster_Iterator#Bin.C3.A4rbaumiterator

[giga4meyou]

@hoehlenknarf

ahm.. das ist glaube ich nur die Implementierung eines binären Baums mittels verketteten Listen und nicht das die Wandlung eines Baums in einen Array. ( Es handelt sich um einen binären Suchbaum)

[giga4meyou]

@hoehlenknarf

sory fürs frech sein, deine erste Antwort wusst ich eben schon und es kam mir so vor als ob es klar wäre.

Mea Culpa

Answer 4

[JoeWied]

Da brauchst du nicht lange zu denken. Davon ausgehend, dass du eine zweidimensionale Tabelle verwendest, musst du eine logische Verbindung von Binärebene zum Tabellen-Zugriff erstsellen. Möglicherweise geht das über einen Schlüssel im Content, der in eine Zielkoodinate umgewandelt werden kann. Das ist vielfach nicht der Fall. Deswegen bleibt nur die Aufnumerierung jeder Ebene auf die Tabelle zu übertragen. Mit dieser kannst du dann beim Rückschreiben wieder den Baum mittels Gruppenbruch erstellen. zB. 1 10 101 102 11 110 12 etc. etc.