binäre Suchbäume Preorder-Traversierung

[Mariexshhx]

Hallo ich soll mit einem Array was die Preorder-Traversierung Besucherreifolge enthält den binären Suchbaum wiederherstellen. Ich frage mich gerade, ob dies überhaupt eindeutig möglich ist? Also ich soll einen Algorithmus beschreiben der genau dies tut.

 

[Jw456]

Warum soll das nicht möglich sein links ist ja immer keiner als die Wurzel.

Wenn zb 7 die Wurzel ist und das nächste ist 9 wo ist dann das Blatt, links oder rechst?

 

[Mariexshhx]

Warum soll das nicht möglich sein links ist ja immer keiner als die Wurzel.

Wenn zb 7 die Wurzel ist und das nächste ist 9 wo ist dann das Blatt, links oder rechst?

rechts. Nur ist das immer so eindeutig ... wenn ich z.B. 30,20,15,10,25,45 als Preorder gegeben habe. Ist 30 die Wurzel dann prüf ich die nächste Stelle also die 20 wird zum linken kind von 30 dann 15 die wird zum linken kind der 20. Dann die 10 dann muss ich doch prüfen ob sie größer ist als die 20 ist sie nicht also dann wird sie das linke kind der 15. So und jetzt die 25 da ist es füt mich nicht eindeutig wird sie das rechte Kind der 20 oder das rechte Kind der 15?

 

[Jw456]

                30
       20              

    15    25
 10

 

[Mariexshhx]

                30
       20             

    15    25
 10

aber das ist dann doch nicht eindeutig oder es könnte auch das rechte Kind der 15 sein?

 

[Jw456]

Du hast sicherlich Recht mit der 25 rechts von 15.
WLR
Da nach der 25 nichts zwischen 15 und 25 kommt kann die 25 als rechtes Blatt an die 15.

 

[Mariexshhx]

Du hast sicherlich Recht mit der 25 rechts von 15.
WLR
Da nach der 25 nichts zwischen 15 und 25 kommt kann die 25 als rechtes Blatt an die 15.

aber einen eindeutigen Algorithmus gibt es dann nicht oder ?

 

[Jw456]

Eigentlich doch

 

[Jw456]

Wie so ist es nicht eindeutig..

Nehmen wir den Knoten 15.
Links kleiner als der Knoten (10) passt
Rechts größer als der Knoten aber nicht größer als der vorherige Knoten (20)
Also können es Werte von 16-19 sein.

Eine Stufe höher (20)
Rechts Werte von 21 bis 29 Wurzel (30)
Da ist die 25 dabei.

Für mich ist das eindeutig.

 

[Mariexshhx]

Wie so ist es nicht eindeutig..

Nehmen wir den Knoten 15.
Links kleiner als der Knoten (10) passt
Rechts größer als der Knoten aber nicht größer als der vorherige Knoten (20)
Also können es Werte von 16-19 sein.

Eine Stufe höher (20)
Rechts Werte von 21 bis 29 Wurzel (30)
Da ist die 25 dabei.

Für mich ist das eindeutig.

achso ich dachte man könnte die 25 auch als rechtes Kind von 15 setzen

 

[Mariexshhx]

Könnte man den Algorithmus so beschreiben:

Man könnte mit einer Schleife über die Positionen des Arrays iterrieren. Bei der Besucherreinfolge von PreOrder- Traversierung wird erst die Wurzel dann der linke und dann der rechte Teilbaum wiederhergestellt. Somit ist das Element an der Stelle A[0] die Wurzel. Wenn das nächste Element im Array kleiner ist, als die Wurzel existiert ein linker Teilbaum. Somit wird dieses Element linker Kinderknoten der Wurzel. Im anderen Fall wäre es der rechte Kinderknoten. Wenn das nächste Element kleiner ist, als das zuvor betrachtete also an der Stelle A[i-1], dann wird es zum linken Kinderknoten, sonst zum rechten. Falls das folgende Element größer ist, als A[i-2] wird es zum rechten Kinderknoten von A[i-2] sonst wird es zum rechten/linken Kinderknoten A[i-1]. Zudem muss bei jedem betrachteten Element geprüft werden, ob es kleiner als die Wurzel ist, wenn diese Bedingung nicht mehr erfüllt ist, weiß man, dass der linke Teilbaum abgeschlossen ist und man mit dem rechten fortfahren muss.

 

[Jw456]

Nicht so ganz richtig.
Es wird von der Wurzel ausgehend gehen den Uhrzeigersinn gegangen.


Wenn also nach der Wurzel kein keiner Wert kommt gibt es keine linken Ast von der Wurzel aus.


Regel links WLR

Schaue dir das mal mal an.

 

[Mariexshhx]

Nicht so ganz richtig.
Es wird von der Wurzel ausgehend gehen den Uhrzeigersinn gegangen.


Wenn also nach der Wurzel kein keiner Wert kommt gibt es keine linken Ast von der Wurzel aus.


Regel links WLR

Schaue dir das mal mal an.

ah okay es muss immer rechts links erledigt werden. Deswegen wäre im meinem Beispiel die 25 auch nicht das rechte Kind der 15 sondern der 20.



Wenn das nächste Element im Array kleiner ist, als die Wurzel existiert ein linker Teilbaum. Das habe ich aber geschrieben, dass es nur dann einen linken Teilbau, gibt

 

[Mariexshhx]

ah okay es muss immer rechts links erledigt werden. Deswegen wäre im meinem Beispiel die 25 auch nicht das rechte Kind der 15 sondern der 20.



Wenn das nächste Element im Array kleiner ist, als die Wurzel existiert ein linker Teilbaum. Das habe ich aber geschrieben, dass es nur dann einen linken Teilbau, gibt

heißt das nicht immer wenn ich einen rechten Knoten einfüge, füge ich den an den ersten Knoten der bisher noch keinen rechten Kinderknoten hat. Wie bei meinem Beispiel mit der 25 da sind wir auch zurück zur 20 und haben dort rechts die 25 eingefügt.

 

[Jw456]

Was habe ich in #9 gesagt.

 

[Mariexshhx]

Was habe ich in #9 gesagt.

eig genau das