Sektion Angewandte Informationsverarbeitung
Übungen zu Systemnahe Software I, Wintersemester 1996/97
Blatt 7
Abgabe: Donnerstag, 19.12.96
Aufgabe 11 (24 Punkte)
Teil a (6 Punkte)
Implementieren Sie einen vollständig ausgeglichenen und nach
inorder-sortierten
Binärbaum in einer dynamischen Datenstruktur,
wobei die Knotenzahl N fest vorgegeben ist. Als Knoteninhalte
sind die Zahlen von 1 bis N einzutragen, und zwar so, daß sie bei
inorder-Traversierung (siehe Teilaufgabe b) aufsteigend geordnet erscheinen.
Mit einer Funktion printTree soll der Baum in zweidimensionaler
Form (z.B. nach links um 90 Grad gedreht) ausgegeben werden.
Funktionen: buildTree und printTree
Teil b (6 Punkte)
Ergänzen Sie das Programm aus a) um drei Funktionen inorder,
preorder und post\%order zur entsprechenden Traversierung des Baumes.
Dabei soll der Knoteninhalt jeweils an stdout geschrieben werden.
Teil c (12 Punkte)
Ergänzen Sie das Programm weiter um eine Funktion insert, die Zahlen,
die über die Standardeingabe eingelesen werden, entsprechend der
preorder-Sortierung in den Baum einfügt. Die Ausgeglichenheit
ist hierbei NICHT zu erhalten. Diese Funktion soll einen
Zeiger auf den neuen bzw. falls der Eintrag bereits enthalten ist, auf diesen
Knoten zurückliefern.
Hinweis: Programmieren II
Damit es nicht zu schwer ist, können Sie im Katalog
/www/thales/ftp/pub/vorlesungen/ws96/soft/blatt7
eine Datei tree.m2
finden, die Modula-2-Funktionen für die Aufgaben a und b
enthält.
Viel Erfolg!
swg