BinärBaum

[Kobsarj]

Hallo Leute, habe eine Frage. Muss aus einer Preorder und einer Inorder Reihenfolge den dazugehörigen Binärbaum erstellen. Bin aber glaub zu blöd das zu machen. Habe was versucht, kommt mir aber falsch vor. Wäre für Hilfe dankbar.

Preorder: ABCDEFG
Inorder: ACFEGDB

 

[CSHW89]

Sieht richtig aus.
lg Kevin

 

[Kobsarj]

Hi, danke für die Antwort. Ich bin aber glaub bissle verwirrt. Ich dachte nämlich, dass Inorder ACFEDGB wäre bei meinem Baum.In einer anderen Übung hatte ich den Baum im Anhang und habe da Inorder als
12,9,7,6,13,10,8,11,14 angegeben. Wenn mein Baum aber stimmt dann muss ja Inorder hier 12,9,7,6,13,10,14,11,8 sein. Was würde jetzt stimmen? Danke für die Hilfe.

 

[CSHW89]

Beide Reihen sind inkorrekt. Es müsste 7,12,9,6,13,10,8,11,14 sein. Man kann es sich so vorstellen, dass man die Zahlen von links nach rechts durchgeht. Allerdings muss der Baum dafür so dargestellt werden, dass immer der linke Teilbaum komplett links von der Wurzel dargestellt ist, und der recht komplett rechts, und das für jeden Teilbaum. Im zweiten Beispiel ist dies fast erreicht. Allerdings müsste die 12 zwischen 7 und 9 rutschen. Dann hast du die oben erwähnte Reihe.

PS: dein erster Baum ist etwas entartet. C muss ein paar Pixel nach rechts. Und der komplette Teilbaum von D abwärts muss zwischen B und C zusammen gestaucht werden. Dann hast du die Inorder, die du angegeben hast.

 

[Kobsarj]

Danke für die Hilfe habs jetzt kapiert.