0 Daumen
144 Aufrufe

Aufgabe

"Rekonstruieren Sie die geordneten binären Bäume, die zu den folgenden Pre- und Inorder-Traversierungen gehören, oder begründen Sie warum es keinen solchen Baum geben kann. Hinweis: Ein geordneter Baum ist nicht notwendigerweise ein Suchbaum.

a)

Preorder: 8,5,9,6,3,4

Inorder: 3,9,6,8,4,5

b)

Preorder:5,4,7,6,9,2

Inorder:5,6,7,4,2,9

Ansatz

a) Hier wäre 8 auf jeden Fall die Wurzel da Preorder mit der Wurzel startet. Da Inorder mit den linkesten Kind des linkesten Teilbaums startet, würde 3 das linkeste Kind des linkesten Teilbaums werden. Leider komme ich ab hier nicht weiter. Würde man auf die Preorder-Reihenfolge achten, wäre "5" jetzt die Wurzel des linkesten Kindes. Aber in Inorder taucht die 5 ganz zum Schluss auf, also müsste sie doch zu dem rechten Kind gehören. Ich bin verwirrt

b) Hier würd ich sagen, dass es diesen Baum nicht gibt, da sowohl Pre- als auch Inorder mit 5 starten und die 5 ja nicht gleichzeitig Wurzel und linkestes Kind sein kann.


Liebe Grüße,

Marceline, The Vampire Queen

von

1 Antwort

+1 Daumen

Ein binärer Baum kann mit der Methode Preorder oder Inorder dargestellt werden. Die beiden Methoden beschreiben denselben Baum, nur die Reihenfolge der Elemente ist unterschiedlich.

Beispiel:

Unbenannt.png
Bei Preorder wird zuerst der Knoten dargestellt, dann der linke und dann der rechte Baum.
A - B - D - E - C - F - G

Bei Inorder wird zuerst der linke Baum dargestellt, dann der Knoten selbst und anschließend der rechte Baum.
D - B - E - A - F - C - G

Die Rekonstruktion wird klar, wenn man sich die beiden Schemata

Preorder: { K,L,R }
Inorder:  { L,K,R }

vor Augen führt. "K" ist der Knoten und besteht immer nur aus einer einzigen Zahl. "L" und "R" sind die jeweiligen Äste, wobei die sortierten Mengen Inorder-L und Preorder-L übereinstimmen müssen, ebenso Inorder-R und Preorder-R.

Um diese (unsortierten) Mengen besser zu unterscheiden, schreibt man

Preorder: { K,Lp,Rp }
Inorder:  { Li,K,Ri }

Die Mengen Li,K,Ri sind über K eindeutig bestimmbar.
Die Mengen Lp,Rp ergeben sich einfach aus der Anzahl der Elemente von Li und Ri, denn die Anzahl der Elemente muss identisch sein.

Weil Lp und Rp wieder vom Typ { K,L,R } sind, muss das erste Element von Lp/Rp der linke/rechte Kind-Knoten von K sein.

Im nächsten Schritt teilt sich das Schema in zwei unabhängige Äste,

Preorder linker Ast: { K,L,R } = { Lp }
Inorder linker Ast:  { L,K,R } = { Li }

Preorder rechter Ast: { K,L,R } = { Rp }
Inorder rechter Ast:  { L,K,R } = { Ri }

usw. rekursiv.
_________________________________________________________________________
Aufgabe a)
Preorder 8,5,9,6,3,4
Inorder 3,9,6,8,4,5

K=8
Li=3,9,6 Ri=4,5
Lp=5,9,6 Rp=3,4

Die Mengen Li und Lp (ebenso Ri und Rp) stimmen nicht überein. Fehler !

_________________________________________________________________________
Aufgabe b)
Preorder 5,4,7,6,9,2
Inorder 5,6,7,4,2,9

K=5
Li=leer Ri=6,7,4,2,9
Lp=leer Rp=4,7,6,9,2

Der linke Kind-Knoten von 5 ist leer (Pivot-Element von Lp).
Der rechte Kind-Knoten von 5 ist die 4 (Pivot-Element von Rp).

_________________________________________________________________________
Die neue Preorder (links) ergibt sich aus Lp = leer
Die neue Inorder (links) ergibt sich aus Li = leer
Die neue Preorder (rechts) ergibt sich aus Rp = 4,7,6,9,2
Die neue Inorder (rechts) ergibt sich aus Ri = 6,7,4,2,9

rechts K=4
Li=6,7 Ri=2,9
Lp=7,6 Rp=9,2

Der linke Kind-Knoten von 4 ist die 7 (Pivot-Element von Lp).
Der rechte Kind-Knoten von 4 ist die 9 (Pivot-Element von Rp).

_________________________________________________________________________
Die neue Preorder (links) ergibt sich aus Lp = 7,6
Die neue Inorder (rechts) ergibt sich aus Li = 6,7

Die neue Preorder (rechts) ergibt sich aus Rp = 9,2
Die neue Inorder (rechts) ergibt sich aus Ri = 2,9

links K=7
Li=6 Ri=leer
Lp=6 Rp=leer

Der linke Kind-Knoten von 7 ist die 6 (Pivot-Element von Lp).
Der rechte Kind-Knoten von 7 ist leer (Pivot-Element von Rp).

rechts K=9
Li=2 Ri=leer
Lp=2 Rp=leer

Der linke Kind-Knoten von 9 ist die 2 (Pivot-Element von Lp).
Der rechte Kind-Knoten von 9 ist leer (Pivot-Element von Rp).

_________________________________________________________________________
Der Baum sieht so aus

Unbenannt2.png

von

Danke für die Antwort. Hat geholfen.

Eine Frage noch: Woran erkennt man jetzt genau, wie der Baum gezeichnet werden muss.Fangen wir unten an, sehen wir das K = 9 der Knoten ist und auf jeden Fall links von 9 der Knoten 2 hängen muss.

Gehen wir hoch zu K = 6, wisen wir, dass Links von 6 nichs mehr sein darf. Und die 9 befindet sich auf jeden Falls rechts von der 6. Und da wir ja die Pre-Order Reihenfolge (6,9,2) hatten, wissen wir, dass wir 6 nicht an die 9 hängen dürfen. Sind also erstmal zwei unterschiedliche Knoten.

Gehen wir hoch zu K = 7. Wir wissen dass links vom Knoten 7 auf jeden Fall der Knoten 6 angehängt wird da wir die In-Order-Reihenfolge (6,7,2,9) haben. Rechts befindet sich der Knoten 9. Aber woher wissen wir jetzt z.b, dass wir den Knoten 9 nicht rechts an die 7 anhängen dürfen? Wer hindert uns daran?

Habe meine Antwort überarbeitet. Eventuell ist es so verständlicher.

Vielen Dank, mathe53.

Zur Überarbeitung: War es in der alten Version nicht so, dass bevor K = 9 betrachtet wird, erst noch K = 6 angeguckt wird. In der alten Version hast du die K's nach Pre-Order-Reihenfolge gewählt ( K war zuerst 5, danach K = 4, dann K = 7, dann K = 6, dann K = 9 und zum Schluss K = 2. Zufall oder beabsichtigt?)

D.h. nach K = 7 müsste doch eigentlich erst K = 6 angeschaut werden, oder?

Bei K = 7 schreibst du jetzt zudem, dass Ri und Rp beide leer seien. Dabei ist doch die Pre-Order 7,6,9,2 und die Postorder 6,7,2,9. Demzufolge wäre Ri = 2,9 und Rp = 9,2.

Vor meiner Überarbeitung lag ein Fehler vor. Ein gefundener Knoten kann nicht einfach aus beiden Sequenzen gelöscht werden.

Das Verfahren zerlegt die Sequenzen Preorder und Inorder immer in einen linken und einen rechten Ast. Diese beiden Äste kann man unabhängig betrachten. Die Reihenfolge spielt keine Rolle. Jedenfalls in einem Binärbaum, weil verschiedene Knoten keine identischen Kind-Knoten aufweisen können.

Vor der Betrachtung von K=7 ergaben sich folgende linke/rechte Äste

Die neue Preorder (linker Ast) ergibt sich aus Lp = 7,6
Die neue Inorder (linker Ast) ergibt sich aus Li = 6,7

Die neue Preorder (rechter Ast) ergibt sich aus Rp = 9,2
Die neue Inorder (rechter Ast) ergibt sich aus Ri = 2,9

Es spielt keine Rolle, ob man zuerst den linken Ast

Preorder 7,6
Inorder 6,7

oder den rechten Ast

Preorder 9,2
Inorder 2,9

löst. Beginnt man beim linken Ast :

Preorder 7,6
Inorder 6,7

dann ist

K=7

Inorder-Links = 6, Inorder-Rechts = leer

Preorder-Links = 6, Preorder-Rechts = leer

Somit kat K=7 nur einen linken Ast K=6

__________________________________________

Das ist zugegeben verwirrend, aber mach Dir klar, dass Du aufgrund des Schemas

Preorder {K,L,R}

Inorder {L,K,R}

die Mengen K,L,R immer eindeutig bestimmen kannst. Weil die gefundenen Mengen L und R für sich alleine betrachtet wieder genau das gleiche Schema repräsentieren, kann man rekursiv durch alle Äste wandern.

Ok alles klar. Vielen Dank für die Darstellung.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community
...