Prof. Franz Schweiggert Abteilung Angewandte Informationsverarbeitung 26. November 2004
Christian Ehrhardt Blatt 6






Allgemeine Informatik 3 (WS 2004/2005)


Abgabetermin 7.12.2004

Bäume (10 Punkte)

Gegeben sei die folgende Grammatik (Non-Terminal Symbole sind in Großbuchstaben geschrieben, Terminalsymbole stehen in Anführungszeichen):

ROOT	::=	TREE
LEFT	::=	TREE
RIGHT	::=	TREE
TREE	::=	``('' ``)''
TREE	::=	``('' CHAR ``)''
TREE	::=	``('' CHAR ``,'' LEFT ``)''
TREE	::=	``('' CHAR ``,'' LEFT ``,'' RIGHT``)''
CHAR	::=	ein beliebiges Zeichen außer ``(''und ``)''

Ein Satz dieser Grammatik beschreibt einen Binärbaum, der in jedem Knoten ein einzelnes Zeichen enthält. Wenn ein (Teil-)Baum (TREE) nicht leer ist und nicht nur aus einem Zeichen (CHAR) besteht, so folgt auf das Zeichen zuerst der linke und dann ggf. der rechte Teilbaum. Das Startsymbol ist ROOT.
Schreibt ein Programm, das einen Satz dieser Grammatik einliest und den Baum im Speicher konstruiert. Anschließend soll der Baum zunächst inorder und dann postorder durchlaufen werden. Dabei soll bei jedem Knoten das dort gespeicherte Zeichen ausgegeben werden.