Universität Ulm - Abteilung Angewandte Informationsverarbeitung

 


8. Übungsblatt zur Vorlesung Allgemeine Informatik II


Abgabetermin: 4. Juli 2002



Aufgabe 1:    Binärbäume     (15 Punkte)



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!


Abbildung: Verschiedene Binäre Bäume
\includegraphics[scale=0.22]{Baum1}



Viel Erfolg!



Hans Braxmeier