TU Wien:Algorithmen und Datenstrukturen 1 VU (Raidl)/Übungen SS09/Beispiel 16

Bei einer In-Order-Traversierung eines gegebenen binären Baumes ergibt sich folgende Knotenliste:

0, 1, 2, 3, 7, 6, 8, 10, 11, 15, 20, 25

Bei einer Pre-Order-Traversierung des gleichen Baumes ergibt sich:

8, 3, 1, 0, 2, 7, 6, 11, 10, 20, 15, 25

Zeichnen Sie den zugrundeliegendenBaum und tragen Sie die entsprechenden Knotenwerte ein.

Lösung

Es gibt zwar einen binären Baum, der diese Werte erfüllt, allerdings hat dieser ein ungültiges Element!

Hinweis:

• Bei der In-Order-Traversierung wird zuerst der linke Teilbaum aufgebraucht, dann die Wurzel, und dann der rechte Teilbaum.
• Bei der Pre-Order-Traversierung wird zuerst die Wurzel, dann der linke Teilbaum und dann der rechte Teilbaum aufgebraucht.

Herangehensweise

Da in der Pre-Order-Traversierung W,L,R - aufgebraucht wird, muss das erste Element (die 8) die Wurzel sein, und das zweite (die 3) die Wurzel des linken Teilbaums sein (siehe Bild1). Wenn man nun die In-Order-Traversierung (L,W,R) betrachtet, müssen die Elemente davor im linken Teilbaum, die dannach im rechten Teilbaum sein.

Der fertige Baum sieht dann folgendermaßen aus:

beachte, da es kein Suchbaum ist, gibt es keine Bedingung, dass das rechte Kind größer und das linke Kind kleiner als der Vater sein muss!!