Binäre Bäume

Wiederholung Listen

Überall in der Informatik treten Baumstrukturen auf, etwa als Verzeichnisbäume eines Betriebssystems. Baumstrukturen können entweder als Erweiterung von Listenstrukturen aufgefasst werden oder sie können mit Hilfe von Listen aufgebaut werden.

Einfache verkettete Liste

Dabei ist ein Knoten ein RECORD der aus dem eigentlichen Listeneintrag (Wert) und einem Zeiger (next) auf den nächsten Knoten besteht. Das Ende der Liste wird durch einen Knoten bestimmt bei dem der Zeiger den Wert NIL hat. Die Liste wird zugänlgich durch einen Zeiger l, der auf den ersten Knoten zeigt. Die Listeneinträge können von beliebige Datentypen sein.

Es müssen zwei neue Datentypen definiert werden: einen Typ für Knoten und einen für Zeiger auf Knoten.

type PKnotentyp = ^Knotentyp;                 {Zeiger auf Knoten}

        Knotentyp= record

                        name    :  string;

                        vorname : string;

                        next    :PKnotentyp;    {Knoten}

                   end;

Ist k eine Variable für einen Knoten vom Typ Knotentyp , dann bezeichnet k.wert den Wert dieses Knotens, k.next den Zeiger auf den Folgeknoten. Dabei ist es möglich, dass k.next den Wert NIL hat, wenn es sich um den letzten Knoten der Liste handelt.

Aufbau einer Liste im einfachsten Fall (schematisch).

Es werden zwei Variablen vom Zeigertyp (PKnotentyp) benötigt:

l steht für den Zeiger auf die aufzubauende Liste, merke steht für einen zwischendrin benötigten Hilfszeiger auf Knoten

Die Liste wird vom Ende her aufgebaut, indem man zunächst mit der leeren Liste beginnt und mit jedem Schritt ein neues

Element vorne an die Liste anfügt. Es werden die folgende Listen schrittweise erzeugt:

Schritte schematisch Erklärung Code
1.
l

NIL

Start : l als leere Liste erzeugen. Der erste Schritt ist fertig.  l repräsentiert jetzt die leere Liste

 l:=nil
2.

l ist noch immer die leere Liste,  Platz für einen neuen Knoten reservieren, und die Adresse für diesen Speicherplatzin der Hilfsvariablen merke festhalten

 new(merke)
 

l ist noch immer die leere Liste

Letztes Listenelement als Wert für den neuen Knoten zuweisen

 merke^.wert:=DS_1
 

l ist noch immer die leere Liste.

Das Ziel von l als next - Zeiger für den erzeugten Knoten definieren. next zeigt  dorthin, wo l hinzeigt (das ist die im vorangehenden Schritt erzeugte Liste)

 merke^.next:=l
 

l jetzt auf den neuen Knoten zeigenlassen: „Zeiger umhängen".

l und merke zeigen gegenwärtig auf den gleichen Speicherplatz.

l repräsentiert jetzt die Liste

 l:=merke
3.

l repräsentiert die Liste [DS_1 ]

Platz für einen neuen Knoten reservieren und die Adresse für diesen Speicherplatz in der Hilfsvariablen merke festhalten

 new(merke)
 

l repräsentiert noch die Liste [DS_1 ]

Nächstes Listenelement als Wert für den neuen Knoten zuweisen

 merke^.wert:=DS_2
 

l repräsentiert noch die Liste [DS_1 ]

Das Ziel von l als next - Zeiger für den erzeugten Knoten definieren. next zeigt dorthin, wo l hinzeigt. 

merke repräsentiert jetzt die Liste [DS_2 , DS_1 ]

 merke^.next:=l
 

Zeiger l „umhängen", so dass l die Liste [DS_2 , DS_1 ] repräsentiert.

 l:=merke

Zugriff auf Listen – LIFO- und FIFO-Strukturen

Repräsentiert ein Zeiger l eine Liste, dann bedeutet

l^.wert das erste Element der Liste, also den Wert  DS_4,

l^.next die Restliste ohne das erste Element der Liste, also die Liste [ DS_3 , DS_2 , DS_1].

Dies zeigt, dass man auf die Elemente eine Liste nur schrittweise zugreifen kann, und zwar über die beiden Operationen „erstes Element der Liste" und „Restliste ohne erstes Element".  Wenn man noch eine Operation hinzu nimmt, die den Prozess zum Listenaufbau durch „vorne Anfügen eines Wertes e an die Liste l" unterstützt, dann sieht man, dass man bei einer Liste auf denjenigen Wert zuerst zugreift, der zuletzt hinzugefügt wurde. 

Solche Strukturen nennt man LIFO-Strukturen als Abkürzung von „Last In, First Out". Listen sind also LIFO-Strukturen. Standardbeispiel für den Einsatz von LIFO-Strukturen ist der in der Informatik häufig gebrauchte Stapel (stack). Man denkt dabei an einen Stapel von Blättern, die man übereinander ablegt. Beim Hinzufügen eines Blattes wird dies oben auf dem Stapel abgelegt, und beim Zugreifen nimmt man das zuletzt abgelegte Blatt als erstes wieder auf.

Unter diesem Aspekt des Anfügens und Zugreifens betrachtet man auch FIFO-Strukturen, Abkürzung von „First In, First Out".Das Modell für diese Struktur ist die Warteschlange (queue), bei der immer derjenige zuerst bedient wird, der zuerst gekommen ist. Diese Struktur entspricht dem einer Liste, bei der Werte hinten angefügt und vorne entnommen werden. Die  Konstruktion einer FIFO-Struktur ist etwas komplizierter als die einer Liste, da man zum Anfügen und zum Entnehmen zwei Zeiger für den Anfang und das Ende der Struktur nötig sind.Ein sehr bekanntes Beispiel für eine FIFO-Struktur ist der Tastaturpuffer eines Computers: Wenn ein Benutzer Zeichen über die Tastatur eingibt, die der Computer nicht unmittelbar verarbeiten kann, dann werden diese in eine Warteschlange gestellt, aus der der Computer die zuerst eingegebenen Zeichen auch zuerst entnimmt, wenn er wieder Zeit dafür hat.

Beispielprogramm für einfachste Listenverarbeitung

 
PROGRAM liste_2;
USES crt;
TYPE
    PKnotentyp = ^Knotentyp;
    Knotentyp  = RECORD
                     wert:longint;
                     next:PKnotentyp;
                 END;
VAR liste:PKnotentyp;
{-------------------------------------------------------------------}
PROCEDURE liste_einlesen (VAR l : PKnotentyp);
VAR merke : PKnotentyp;
    zahl  : longint;
BEGIN
     l:=nil;
     REPEAT
           WRITE('Zahl : ');READLN(zahl);
           IF zahl<>0 THEN
              BEGIN
                   new(merke);
                   merke^.wert:=zahl;
                   merke^.next:=l;
                   l:=merke;
              END;
     UNTIL zahl=0;
END;

{-------------------------------------------------------------------}
PROCEDURE liste_ausgeben(l : PKnotentyp);
{ Zerstoert die Liste l im Hauptprogramm nicht, da l kein Var-Parameter ist }
BEGIN
     WHILE l<>nil DO
           BEGIN
                WRITELN(l^.wert);
                l:=l^.next;
           END;
END;
{-------------------------------------------------------------------}
PROCEDURE liste_loeschen(l :PKnotentyp);
VAR merke:PKnotentyp;
BEGIN
     WHILE l<>nil DO
           BEGIN
                merke:=l^.next;
                dispose(l);   
                l:=merke;
           END;
END;

{------------------------ HAUPTPROGRAMM -----------------------------}
BEGIN
     clrscr;
     WRITELN(sizeOf(Knotentyp));
     WRITELN('Heap : ',MemAvail);
     liste_einlesen(liste);
     liste_ausgeben(liste);
     WRITELN('Heap : ',MemAvail);
     liste_loeschen(liste);
     WRITELN('Jetzt Liste wieder geloescht : ');
     WRITELN('Heap : ',MemAvail);
     READLN;
END.

Mit "dispose" kann der Speicherplatz (und der zugehörige Datensatz) wieder dem System zur Verfügung gestellt werden, auf den der Zeiger <zeigervariable> zeigt. Durch die Verwendung von "dispose" bekommt der Heap aber "Löcher". Diese Löcher werden durch erneute Anwendung von "new" wieder aufgefüllt, bevor neuer Platz im HEAP angefordert wird.

sizeOf

Die Funktion SizeOf(variable) / SizeOf(datentyp) ist allgemein verwendbar und liefert die Größe einer Variablen oder eines Daten-typs.
Beispiel: Write(SizeOf(s1^));
In Verbindung mit dynamischen Variablen ist es wichtig zu wissen, dass ab Turbo-Pascal Version 6.0 der belegte Speicher im Heap-Speicher immer auf volle 8-Byte-Gruppen aufgefüllt wird. In der Regel wird also mehr Speicher reserviert, als tatsächlich benötigt wird. Besteht z.B. ein dynamischer Rekord aus zwei Real-Feldern (je 6 Byte), so liefert SizeOf 12, reserviert werden aber 16 Byte im Heap-Speicher. Auf diesen Umstand ist bei der Ermittlung der maximalen Anzahl der Daten im Heap durch eigene programmtechnische Maßnahmen einzugehen, da SizeOf alleine im allgemeinen ein falsches Ergebnis liefert.

Weiter Binäre Bäume