Universität Ulm - Abteilung Angewandte Informationsverarbeitung
Durch folgende Typvereinbarung sei ein binärer Baum und ein Array gegeben:
TYPE Tree = POINTER TO Node; Node = RECORD; content: INTEGER; right: Tree; left: Tree; END; Values = ARRAY 12 OF INTEGER;
Weiterhin seien folgende Variablen definiert:
VAR root: Tree; valis: Values; number, index: INTEGER;
... und die folgenden Werte im Array values gespeichert:
5, 8, 7, 10, 1, 11, 12, 9, 3, 6, 4, 2
In Anlehnung an die Vorlesung wird mit folgender Prozedur ein ausgeglichener binärer Baum aufgebaut:
PROCEDURE InsertBalanced(number: LONGINT; VAR index: INTEGER): Tree; VAR tmp: Tree; BEGIN IF (number = 0) THEN RETURN NIL; ELSE NEW(tmp); index := index + 1; tmp.content := values[index]; tmp.right := InsertBalanced(number DIV 2, index); tmp.left := InsertBalanced(number - (number DIV 2) - 1, index); RETURN tmp; END; END InsertBalanced;
Initialisierung und Aufruf der Prozedur InsertBalanced geschieht folgendermaßen:
root := NIL; index := -1; root := InsertBalanced(LEN(values), index);
Teilaufgabe a: (5 Punkte)
Erklärt Eurem Tutor wie der Baum in der Prozedur InsertBalanced
Schritt für Schritt aufgebaut wird (also 12 Einzelbilder aufzeichnen,
nix programmieren)!
Teilaufgabe b: (2 Punkte)
In Abbildung 1 sind 5 binäre Bäume dargestellt.
Bestimmt nun, welche der Bäume nach Höhe bzw. Gewicht ausgeglichen
sind. Gibt es eine vorteilhafte Vorgehensweise bei der Bestimmung von
Höhe und Gewicht? Erklärt Eurem Tutor, wie Höhe und Gewicht eines Baumes
definiert sind!
Teilaufgabe c: (3 Punkte)
Bestimmt nun den Grad und die Höhe der grau markierten Knoten sowie den
Grad und die Höhe aller Bäume.
Teilaufgabe d: (5 Punkte)
Wiederholt den Inhalt der Vorlesung aus den letzten 3 Wochen
und stellt Eurem Tutor konkrete und schlaue Fragen zum Thema
Zeiger. Schlau heißt NICHT: Was ist ein Zeiger??? Dafür gibt's
nen Punkt abzug!!! Für jede wirklich SCHLAUE Frage dagegen
verteilt der Tutor 1 Punkt an Euch; leider können bei Teilaufgabe
d) max. 5 Punkte erreicht werden... aber noch mehr fragen schadet
trotzdem nicht!
Viel Erfolg!