Zum Abschluß dieser Einführung in die Programmiersprache Pascal soll noch ein einziges Beispiel für eine nichtlineare dynamische Datenstruktur mit Zeigern gegeben werden: Ein Baum ist (in der Graphentheorie) ein Graph mit einem Eingang, in dem jeder Knoten auf genau einem Weg vom Eingang aus erreicht werden kann (s. Bild 99).
Bild 99: Ein Baum
Bäume zeichnet man üblicherweise mit der Wurzel (dem Eingang) nach oben. Jeder Knoten besitzt eine gewisse Tiefe, das ist die Distanz zum Eingang (hier also Knoten 1). Knoten ohne Nachfolger bezeichnet man als Blätter. Jeder innere Knoten hat eine gewisse Anzahl an direkten Nachfolgern, die selbst Wurzeln von Teilbäumen sind. So besitzt der Wurzelknoten (1) zwei direkte Nachfolger (2 und 3), wobei z.B. 3 die Wurzel des Teilbaumes aus den Knoten 3, 6, 7, 9, 10, 11 und 12 bildet. Die Maximalanzahl der direkten Nachfolger, die ein Knoten in einem Baum besitzt, heißt der Grad des Baumes.
Bild 99 zeigt einen binären Baum, also einen Baum des Grades 2, da jeder Knoten nur 0,1 und 2 direkte Nachfolger besitzt. Knoten mit mindestens einem Nachfolger, die also nicht Blätter sind, heißen innere Knoten. Außerdem läßt sich eine Ordnung auf den Knoten des Baumes definieren, indem man für jeden Knoten K im Baum folgende Relationen vereinbart:
O1. Alle Knoten im linken Teilbaum mit der Wurzel K sind kleiner als K.
O2. Alle Knoten im rechten Teilbaum mit der Wurzel K sind größer als K.
Mit diesen Regeln ergibt sich in Bild 99 für die Wurzel folgende Relation:
2, 4, 5, 8, 13 < 1 < 3, 6, 7, 9, 10, 11, 12
Wendet man diese Regeln (rekursiv) auch auf alle Knoten in den Teilbäumen an, so erhält man eine vollständige Ordnung:
4 < 2 < 8 < 13 < 5 < 1 < 9 < 6 < 10 < 3 < 11 < 7 < 12
Nun sind alle Begriffe definiert, um zu erläutern, wie sich die Kundenverwaltung des letzten Abschnittes in einem binären Baum effizient organisieren läßt. Wiederum sollen alle Kunden alphabetisch sortiert gespeichert werden, um ohne Nachsortieren eine nach Namen sortierte Liste auszugeben. Vor allen Dingen wird die oben beschriebene Ordnung auch benutzt, um einen Kunden mit möglichst wenigen Vergleichen über seinen Namen zu finden.
Bild 100: Baum mit Kundenrecords
Einfüge- und Löschoperationen sollen so erfolgen, daß eine Datenstruktur wie in Bild 100 entsteht. Diese Struktur läßt sich durch die folgende Typ- und Variablendeklaration in Pascal erzeugen:
TYPE KUNDENZEIGER = ^ KUNDE;
KUNDE = RECORD
NAME : STRING[10];
KNUMMER : INTEGER;
L,R : KUNDENZEIGER;
END;
VAR WURZEL : KUNDENZEIGER;
Die Knoten des Baumes werden also durch Records des Typs KUNDE dargestellt. Die Datenfelder NAME und KNUMMER sind wie bei der Kundenliste im letzten Abschnitt definert. Jedoch erhält jeder Kunde nun zwei Nachfolger. Die Felder L und R enthalten deshalb Zeiger auf den linken und den rechten Nachfolger im Baum. Existiert einer der beiden Nachfolger nicht, so wird das entsprechende Feld mit dem Wert NIL belegt.
Die Operationen mit dieser Datenstuktur sind in Bild 101 ausführlich kommentiert wiedergegeben. Bevor Sie weiterlesen, sollten Sie das Programmlisting studieren, um sich mit dem Problem vertraut zu machen.
Am Programmanfang sind noch keine Kunden gespeichert und der Baum ist leer:
WURZEL:= NIL
Beim Einfügen muß die alphabetische Reihenfolge im Baum erhalten bleiben. Hierzu durchläuft man den Baum von der Wurzel ausgehend zu den Blättern. Dabei wird in jeder Tiefe der Name des neuen Kunden mit dem im Knoten gespeicherten Namen verglichen. Ist der Name größer, so muß die Einfügung im rechten Teilbaum ausgeführt werden, sonst wird der Zeiger zum linken Teilbaum verfolgt.
Um »KUNZE« in den Baum von Bild 100 einzufügen, bestimmt man in der Prozedur EINFUGEN den folgenden Weg:
KUNZE < MUELLER gehe links KUNZE > BREHM gehe rechts KUNZE > KONRAD gehe rechts
Da kein rechter Nachfolger von »KONRAD« existiert, das heißt der Zeiger R im Record ist NIL, kann man jetzt »KUNZE« als rechten Nachfolger von »KONRAD« einfügen.
Diese Strategie beschreibt die rekursive Prozedur EINFUEGEN. Sie wird mit zwei Parametern aufgerufen. NEU ist ein Record vom Typ KUNDE, um den der Baum erweitert werden soll. Der Variablenparameter Z ist ein Zeiger auf die Wurzel des Teilbaumes, in den NEU eingefügt werden soll. Bitte beachten Sie, daß hier ein Variablenparameter erforderlich ist, um bei einer Einfügung (Z = NIL) den Zeiger auf das neue Element in der aufrufenden Umgebung zu ändern.
Bei der Suche fällt auf, daß man im Idealfall die Größe des noch zu durchsuchenden Teilbaumes in jedem Schritt halbiert. Somit hat man in einem Baum mit N Knoten nach log(N) Schritten die Einfügeposition bestimmt. Natürlich muß man dafür sorgen, daß der entstehende Baum ausgeglichen bleibt, so daß jeder innere Knoten möglichst gleich viele linke wie rechte Nachfolger besitzt. Würde man zum Beispiel ständig Einfügungen am rechten Blatt vornehmen, so hätte der entstehende Baum die Form einer Liste, die über das Feld R verkettet ist. Dann beträgt die Tiefe des Baumes N statt log(N) im Falle des ausgeglichenen Baumes.
Zur Ausgabe der alphabetisch geordneten Tabelle muß man den Baum in der durch die Regeln O1 und O2 definierten Ordnung durchlaufen. Dies geschieht am elegantesten mit der rekursiven Prozedur INORDER. Der Parameter Z gibt die Wurzel des Teilbaumes an, der gedruckt werden soll. Die oben beschriebene Ordnung verlangt eine Ausgabe in der folgenden Reihenfolge:
Da die Wurzel in der Ordnung zwischen dem linken und dem rechten Teilbaum liegt, heißt diese Ordnung inorder (im Gegensatz zu postorder und preorder).
Löschungen eines inneren Knotens im geordneten binären Baum erfordern etwas genauere Überlegungen, damit die Ordnung zwischen den übrigbleibenden Knoten erhalten bleiben. Zunächst wird wie beim Einfügen das zu löschende Element in der Prozedur ENTFERNE rekursiv gesucht. Beim Löschen von Z^ müssen nun folgende zwei Fälle unterschieden werden:
Bei der Operation (2) wird die rekursive Prozedur HOLEHOCH verwendet. Den größten Wert in einem Teilbaum findet man offensichtlich, indem man bei jedem inneren Knoten nach rechts geht. Damit ist Z1 entweder ein Blatt oder ein Knoten, der nur einen linken Nachfolger besitzt, so daß sich Z1 selbst leicht löschen läßt.
Sollten Sie Interesse an solchen Datenstrukturen und Algorithmen gefunden haben, können Sie sich, ausgerüstet mit den Kenntnissen aus diesem Buch, unbesorgt der Fachliteratur über Systematische Programmierung [2], [5], [6], [7], [8] (s. Anhang E) zuwenden. Dort finden Sie viele weitere Anregungen und vollständige Algorithmen, die effizient in Pascal realisiert werden können.
Bild 101: Kundenverwaltung in einem Baum
1. Versuchen Sie, eine Kundenliste ohne leere Records am Anfang und Ende der Liste zu verwalten. Sollte die Programmlänge dabei um mehr als dreißig Zeilen anwachsen, haben Sie zumindest den Sinn dieser Hilfsrecords erkannt.
2. Alternativ können Sie die Kundenliste alphabetisch sortiert und doppelt verkettet anlegen. Dann können Sie auch die Prozedur VORHANDEN so ändern, daß sie einen Zeiger auf das alphabetisch größere Element liefert, da Sie immer einen Zeiger auf den Vorgänger besitzen. Eventuell können Sie auch auf die leeren Records am Anfang und Ende der Liste verzichten.
3. Um zu prüfen, ob Sie die Operationen in Bild 101 im großen und ganzen verstanden haben, sollten Sie das Programm so ändern, daß die Records nach Kundennummer sortiert im Baum gespeichert werden.
4. Schreiben Sie eine rekursive Prozedur REVERSE, die eine Liste invertiert, so daß der letzte Record als erster in der neuen Liste erscheint. (Diese rekursive Lösung ist nur für kurze Listen geeignet!)
5. Schreiben Sie eine rekursive Prozedur SWAP, die in einem binären Baum den linken und rechten Nachfolger jedes inneren Knotens vertauscht. Bild 102 zeigt das Ergebnis dieser Operation für den Baum aus Bild 99:
Bild 102: Wirkung der Prozedur SWAP
6. Schreiben Sie eine Prozedur MERGE, die zwei sortierte Listen A und B zu einer sortierten Liste C zusammenfügt (s. Programm MERGE zum Sortieren von Files!.
PROCEDURE MERGE(A,B: KUNDENZEIGER; VAR C: KUNDENZEIGER);
Beispiel:
A = (Alpha, Brehm, Konrad, Mueller, Vogel, Zeiser)
B = (Bauer, Friedrich, Schnidt, Schulze)
C = (Alpha, Bauer, Brehm, Friedrich, Konrad, Mueller,
Schmidt, Schulze, Vogel, Zeiser)
7. Ersetzen Sie die Prozedur INORDER durch die Prozedur PREORDER, die die Knoten eines Baumes in der folgenden Reihenfolge druckt:
PROCEDURE PREORDER(Z: KUNDENZEIGER);
BEGIN
IF Z<>NIL THEN
BEGIN
DRUCKE(Z);
PREORDER(Z^.L);
PREORDER(Z^.R);
END
END; (* PREORDER *)
Verdeutlichen Sie sich die Reihenfolge der Ausgabe an einigen Beispielen! Anschließend wird es Ihnen sicher leichtfallen, die Prozedur POSTORDER in Pascal zu definieren, die den Wurzelknoten bei der Ausgabe zuletzt nennt.