Satellit

Anleitung

Stell dir vor, du musst einen Binärbaum zu einem Satelliten übertragen, der sich Alpha Centauri nähert, und du hast nur eine begrenzte Bandbreite. Da der Baum keine wiederholten Elemente enthält, lässt er sich eindeutig durch seine Preorder- und Inorder-Traversierung darstellen.

Schreibe die Software für den Satelliten, damit er den Baum aus den Traversierungen rekonstruiert.

Eine Preorder-Traversierung liest den Wert des aktuellen Knotens, bevor (daher „pre“) sie den linken Teilbaum in Preorder liest. Danach wird der rechte Teilbaum in Preorder gelesen.

Eine Inorder-Traversierung liest zuerst den linken Teilbaum in Inorder, dann den aktuellen Knoten und schließlich den rechten Teilbaum in Inorder. Also in der Reihenfolge von links nach rechts.

Zum Beispiel ist die Preorder-Traversierung dieses Baums [a, i, x, f, r]. Die Inorder-Traversierung dieses Baums ist [i, a, f, x, r]

  a
 / \
i   x
   / \
  f   r

Hinweis: Das erste Element der Preorder-Traversierung ist immer die Wurzel.