Probleme mit Bäume

[therocker]

Hallo es ist heute meine Premiere im Forum.

Ich komme bei einer ganz bestimmten Aufgabenstellung nicht mehr weiter und wollte fragen ob mir jemand Anregungen geben könnte.

Die Aufgabenstellung lautet:

Sie erhalten zwei Folgen von Zahlen: die Preorder- und die Inorder-Reihenfolge der Knoten
eines Binärbaums. Können Sie aus den beiden Zahlenfolgen den Binärbaum eindeutig
rekonstruieren? Begründen Sie Ihre Antwort anschaulich und geben Sie mindestens ein
Beispiel an.




Ich brauche es nicht auszuprogrammieren sondern nur ein Verfahren entwickeln
Kann mir jemand weiterhelfen? Bitte keine allgemeinen Bäume infos sondern wenn möglich konkrete Lösungsanregungen.

Vielen Dank im Voraus!

 

[Gorcky]

Poste doch einfach mal die preorder- und inorder-Ansicht, dann könne wir ja gucken.

 

[squeaker]

Ja, geht

Pre-Order: Wurzel - Links - Rechts
In-Order: Links - Wurzel - Rechts

Damit sollte es gehen - mal schaun ob ich das zusammenbekomme.

Beispielbaum:

In: B C A F E G D I H
Pre: A B C D E F G H I

OK, damit ist A die Wurzel (siehe Pre-Order) und aus der In-Order folgt dann:

BC ist linker Teilbaum, FEGDIH rechter Teilbaum.

Ich klammer mal die Bäume:

In: (BC)A(FEGDIH)
Pre: A(BC)(DEFGHI)

und das ganze dann rekursiv weiter für jeden Teilbaum, also rechts:
D ist die Wurzel, damit folgt aus In-Order:
FEG - D - IH sind die Teilbäume

erneut Klammern:

(FEG)D(IH)
D(EFG)(IH)

Damit sollte es klar sein. Ordentlich aufgeschrieben geht das als Beweis und sollte die Lösung für deine Aufgabe sein.

 

[Jack]

Ja auf jeden Fall!

Vielen Dank nochmals für die ausführliche Antwort. Das war genau die Info die ich gesucht habe!