Algorithmen und Datenstrukturen in PASCAL Teil 4: Binärbäume

In der heutigen Folge von Algorithmen & Datenstrukturen werde ich Ihnen die Datenstruktur der Binärbäume vorstellen. Um es gleich vorwegzunehmen: Es handelt sich hierbei nicht um den Versuch, aus der ST-Computer eine Fachzeitschrift für Botaniker zu machen, sondern um die Bemühung, eines wohlmeinenden Autors, einige Anwendungsprogrammierer arbeitslos zu machen.

Von Bäumen und merkwürdigen Familienverhältnissen

Ganz in diesem Sinne, werde ich zunächst mit einer kleinen botanisch/biologischen Begriffsklärung beginnen.

Da wäre als erstes der Begriff des Baumes. Wie man kaum vermutet, handelt es sich dabei um ein, wie folgt, rekursiv, definiertes Ding:

Ein Baum besteht aus einer Markierung, genannt Knoten (Blatt), und Teilbäumen (?"ste), die wiederrum Bäume sind. Hat dieser Baum maximal zwei Teilbäume, so spricht man von einem Binärbaum. Existiert für die Knoten eine Anordnung, das heißt, es läßt sich entscheiden, ob ein Knoten, gemäß einer Relation, vor, oder nach einem anderen Knoten kommt, so nennt man die Knoten Schlüssel. Ein binärer Suchbaum ist nun ein Binärbaum, dessen Schlüssel, gemäß der Relation, größer als sämtliche Schlüssel im linken Teilbaum, sowie kleiner als sämtliche Schlüssel im rechten Teilbaum, ist. Außerdem müßen noch beide Teilbäume binäre Suchbäume sein.

Speziell mit diesem Ding, also einem binärem Suchbaum, werde ich mich heute befassen.

Doch zuvor noch einige gängige Begriffe:

Der erste Knoten eines Baumes heißt, wie könnte es anders sein, Wurzel. Der direkte Vorgänger eines Knotens heißt Vater, der direkte Nachfolger, Sohn. Die Höhe eines Baumes ist die maximale Anzahl der aufeinanderfolgenden Teilbäume.

Sinn des Ganzen

Wie schon in der letzten Folge angekündigt, handelt es sich bei binären Suchbäumen um eine weitere Struktur zur Datenverarbeitung. Wenn Sie sich diese letzte Folge noch einmal kurz ins Gedächtnis rufen, werden Sie feststellen, daß auf unsere Suchbäume beide Kriterien für datenverarbeitende Strukturen zutreffen:

  1. Die Struktur ist der binäre Baum.
  2. Die Daten werden, gemäß den ihnen zugrunde liegenden Schlüsseln, im linken, oder rechtem Teilbaum, eingeordnet.

Der Sinn, dieser nicht ganz einfachen Struktur, wird klar, wenn Sie sich die Abb.4a ansehen.

Die Abbildung zeigt einen vollständig besetzten Binärbaum. Wie man leicht sieht, lassen sich in einem solchen Baum der Höhe n maximal 2n-1 Elemente einfügen. Diese unscheinbar aussehende Beziehung beinhaltet den großen Vorteil der Binärbäume, oder allgemeiner, der Bäume. Sie bedeutet nämlich, daß es möglich ist 2n-1 Elmente so anzuordnen, daß man auf jedes dieser Elemente in maximal n Schritten zugreifen kann.

Beispiel: Jedes Element eines Datensatzes von 4095 Elementen (212-1) wird mit maximal 12 Vergleichen gefunden.

Im Vergleich zu den, in der letzten Folge behandelten, Listen, wo gegebenenfalls 2n-1 Vergleiche (!) durchgeführt werden mußten, ein gigantischer Vorteil.

Ein Hindernis

Ein Problem, was noch zu lösen wäre, ist die Schlüsselgleichheit, oder konkreter ausgedrückt:

Was macht man, wenn mehrere identische Schlüssel vorliegen ?

Als Problemlösung habe ich hier eine Nachfolgerliste gewählt. Dies bedeutet, daß mehrere Datensätze mit demselben Schlüssel durch einen Representanten im Baum dargestellt werden und das man die anderen Datensätze jeweils über eine Nachfolgerliste erreicht. Werden nun sämtliche Elemente mit einem Schlüssel gesucht, so wird zunächst der Baum bis zu dem Representanten durchlaufen und darauffolgend die Nachfolgerliste. Diese kleine Nuance verkompliziert die Zeigerstruktur geringfügig, sollte aber sofort mit berücksichtigt werden, denn Schlüsselgleichheit kommt sehr häufig vor.

Beispiel: gleiche Nachnamen beim Datensatz Adresse

Die Zeigerstruktur

Genau wie in der letzten Folge, gehe ich auch heute davon aus, daß mein Datensatz in Schlüssel und Restdaten zerfällt. Entsprechend sind hierfür zwei Typen (key_type und data_type) zu vereinbaren (siehe Listing 4a). Die Wurzel eines Binärbaumes ist nun Zeiger auf das erste Binärbaumelement, also ist ein Binärbaum (b_tree) nichts weiter, als Zeiger auf sein erstes Element (^b_element).

{ Listing 4a)

  Datentypen der B-Baeume

  Reservierte Woerter : key_type, data_type, b_tree, b_element, file_type

  programmiert        : Juni 87
  von                 : Dirk Brockhaus
  mit                 : PASCAL+ (CCD)
}

key_type  = integer;

data_type = integer;

b_tree    = ^b_element;

b_element = RECORD
              key   : key_type;
              data  : data_type;
              left  ,
              right ,
              next  : b_tree;
            END;

file_type = RECORD
              key  : key_type;
              data : data_type;
            END;

Die Elemente (b_element) haben, entsprechend obigen Vorüberlegungen, folgendes Aussehen: Zunächst bestehen sie aus Schlüssel und Restdaten (key & data). Weiterhin muß ein Zeiger auf den rechten und auf den linken Elementnachfolger weisen (right & left). Zusätzlich muß noch ein Zeiger auf den Listennachfolger für gleiche Schlüssel weisen (next). Das dieser ebenfalls ein b_tree ist, sei eine mir gestattete programmtechnische Schludrigkeit, die, bis auf minimale Speichervergeudung für zwei Zeiger, keine tiefergehenden Nachteile besitzt.

Zur Unterhaltung dieser Struktur benötige ich nun einige Operationen, die äußerlich eine gewisse Ähnlichkeit, mit denen der letzten Folge, nicht leugnen können:

  1. create(tree) zum Initialisieren eines Binärbaumes.
  2. insert(tree,key,data) fügt einen, durch key und data, vollständig, beschriebenen Datensatz in einen Binärbaum tree ein.
  3. remove(tree,key) löscht sämtliche Datensätze mit durch key bezeichnetem Schlüssel in tree und teilt den Erfolg dieser    Aktion über den Funktionsreturn mit.
  4. search_first(tree,key,data) sucht in tree nach dem ersten, durch key bezeichnetem, Datensatz data. Der Erfolg, der Suche,    steht ebenfalls im Funktionsreturn.
  5. search_next(data) sucht den nächsten Datensatz mit Schlüsselkey in tree. Zu beachten ist hierbei, daß ein Aufruf von    search_next, an einen vorhergehenden Aufruf von search_first    gekoppelt ist. Andernfalls geschieht Unsinn, oder fachgerech   ter formuliert: 'Der Wert von data wird undefiniert'.
  6. save(tree,filename) speichert den durch tree bezeichneten Baum    in der Datei filename.
  7. load(tree,filename) lädt die durch filename bezeichnete Datei    nach tree.

Für eine genaue Liste der Funktionalitäten bemühen Sie bitte den Programmkopf von Listing 4b.

 Zusätzlich zu diesen sieben Operationen, ist es nun noch möglich die Baumelemente in einer gewissen Reihenfolge auszugeben. Anders als bei den Listen, wo nur eine bestimmte Ausgabereihenfolge (Auflisten der Elemente) möglich war, sind hier unter-schiedliche Strategien möglich und nötig. Dazu wird der Binärbaum auf drei Arten durchlaufen:

8.1. Der inorder-Durchlauf besucht zunächst den linken Teilbaum, dann wird das Schlüsselelement ausgegeben, dann erst wird der rechte Teilbaum besucht.
8.2. Der präorder-Durchlauf gibt zunächst das Schlüsselelement aus und besucht darauf die beiden Teilbäume (zunächst      links).
8.3. Der postorder-Durchlauf besucht zuerst die beiden Teilbäume (ebenfalls zunächst links) und gibt dann das Schlüsselelement aus.

Wie Sie sehen werden, finden zwei dieser Durchläufe bei der Implementierung der Binärbäume und der späteren Nutzung der Struktur eine direkte Anwendung.

Die Implementierung der Operationen im einzelnen (Listing 4b):

  1. create(tree)

Die Prozedur create(tree) erledigt die Initialisierung des Baumes tree, indem tree mit nil belegt wird. War tree zuvor besetzt, so werden dessen Elemente ausgehängt und sind nicht mehr zugänglich.

  1. insert(tree,new_key,new_data)

Die Prozedur insert erzeugt zunächst Speicherplatz für ein neues Element (element). Hierauf erfolgt die Initialisierung des Elementes und der Aufruf einer Hilfsfunktion put_in, die das Einfügen eines Elementes in den Baum tree realisiert.

put_in ist nun rekursiv formuliert:

Die Abbruchbedingung für die Rekursion ist, daß der im Moment betrachtete Teilbaum p den Wert nil hat. In diesem Fall wird das element genau an dieser Stelle eingefügt.

Ist dies noch nicht der Fall, hat man zwischen drei Möglichkeiten zu wählen:

2.1 Für den Fall, das unser neuer Schlüssel, new_key, kleiner als     das im Moment betrachtete Baumelement ist, wird im linken Teilbaum nach der Einfügestelle gesucht.

2.2 Für den Fall, das er größer als das im Moment betrachtete     Element ist, im Rechten.

2.3 Im dritten Fall, also bei doppelten Schlüsseln, ist die Nachfolgerliste zu durchlaufen. Angefügt wird in diesem Fall am Ende der Nachfolgerliste.

  1. remove(tree,key)

Das Entfernen sämtlicher, gleicher Schlüssel aus einem Baum, gestaltet sich nicht ganz so einfach, wie das Einfügen. Zunächst ist allerdings ein gleichartiges Problem, wie bei insert zu lösen:

Es wird mit einem rekursiven Aufruf von remove mit seinem Rechts bzw. Linksnachfolger die Stelle gesucht, an der Elemente ausgefügt werden sollen. Gerät man dabei an einen nil-Zeiger, so ist die Suche beendet und das Element ist nicht gefunden worden.

{ Listing 4b)

  Operationen auf B-Baeumen

  Funktionalitaet der Operationen:

   - create        : () --> b_tree
   - insert        : b_tree x key x data --> b_tree
   - remove        : b_tree x key --> b_tree x boolean
  (- search_ptr    : b_tree x key --> b_tree x boolean)
   - search_first  : b_tree x key --> data x boolean
   - search_next   : b_tree x key --> data x boolean
   - save          : b_tree x string --> file
   - load          : file x string --> b_tree

  Lokale Variablen : present_ptr

  Reservierte Woerter : create, insert, remove, search_ptr, search_first,
                        search_next, save, load, present_ptr

  programmiert        : Juni 87
  von                 : Dirk Brockhaus
  mit                 : PASCAL+ (CCD)
}

present_ptr : b_tree;

PROCEDURE create(VAR tree : b_tree);

  BEGIN {create}
    tree:=nil;
  END;  {create}

PROCEDURE insert(VAR tree     : b_tree;
                     new_key  : key_type;
                     new_data : data_type);

  VAR element : b_tree;

  PROCEDURE put_in(    element : b_tree;
                   VAR p       : b_tree);

    BEGIN {put_in}
       IF p=nil THEN
         p:=element
       ELSE
         IF new_key<p^.key THEN
           put_in(element,p^.left)
         ELSE
           IF new_key>p^.key THEN
             put_in(element,p^.right)
           ELSE
             put_in(element,p^.next);
    END;  {put_in}

  BEGIN {insert}
    new(element);
    WITH element^ DO
      BEGIN
        key:=new_key;
        data:=new_data;
        right:=nil;
        left:=nil;
        next:=nil;
      END;
    put_in(element,tree);
  END;  {insert}

FUNCTION remove(VAR tree : b_tree;
                    key  : key_type) : boolean;

  PROCEDURE put_out(VAR old : b_tree);

    VAR copy_old       ,
        daddy_max_left ,
        max_left       : b_tree;

    BEGIN {put_out}
      copy_old:=old;
      IF copy_old^.right=nil THEN
        old:=copy_old^.left
      ELSE
        IF copy_old^.left=nil THEN
          old:=copy_old^.right
        ELSE
          BEGIN
            daddy_max_left:=copy_old^.right;
            IF daddy_max_left^.left=nil THEN
              BEGIN
                daddy_max_left^.left:=copy_old^.left;
                old:=daddy_max_left;
              END
            ELSE
              BEGIN
                max_left:=daddy_max_left^.left;
                WHILE max_left^.left<>nil DO
                  BEGIN
                    daddy_max_left:=max_left;
                    max_left:=daddy_max_left^.left;
                  END;
                max_left^.left:=copy_old^.left;
                daddy_max_left^.left:=max_left^.right;
                max_left^.right:=copy_old^.right;
                old:=max_left;
              END;
          END;
    END;  {put_out}

  BEGIN {remove}
    IF tree<>nil THEN
      IF key<tree^.key THEN
        remove:=remove(tree^.left,key)
      ELSE
        IF key>tree^.key THEN
          remove:=remove(tree^.right,key)
        ELSE
          BEGIN
            remove:=true;
            put_out(tree);
          END
    ELSE
      remove:=FALSE;
  END;  {remove}

FUNCTION search_ptr(    tree : b_tree;
                        key  : key_type;
                    VAR list : b_tree) : boolean;

  BEGIN {search_ptr}
    IF tree<>nil THEN
      IF key<tree^.key THEN
        search_ptr:=search_ptr(tree^.left,key,list)
      ELSE
        IF key>tree^.key THEN
          search_ptr:=search_ptr(tree^.right,key,list)
        ELSE
          BEGIN
            search_ptr:=true;
            list:=tree;
          END
    ELSE
      search_ptr:=false;
  END;  {search_ptr}

FUNCTION search_first(    tree : b_tree;
                          key  : key_type;
                      VAR data : data_type) : boolean;

  VAR found : boolean;

  BEGIN {search_first}
    found:=search_ptr(tree,key,present_ptr);
    IF found THEN
      data:=present_ptr^.data;
    search_first:=found;
  END;  {search_first}

FUNCTION search_next(VAR data : data_type) : boolean;

  VAR found : boolean;

  BEGIN {search_next}
    present_ptr:=present_ptr^.next;
    found:=present_ptr<>nil;
    IF found THEN
      data:=present_ptr^.data;
    search_next:=found;
  END;  {search_next}

PROCEDURE save(tree     : b_tree;
               filename : string);

  VAR t : FILE OF file_type;

  PROCEDURE put_praeorder(tree : b_tree);

    VAR help : b_tree;

    BEGIN {put_praeorder}
      IF tree<>nil THEN
        BEGIN
          help:=tree;
          REPEAT
            t^.key:=help^.key;
            t^.data:=help^.data;
            help:=help^.next;
            put(t);
          UNTIL help=nil;
          put_praeorder(tree^.left);
          put_praeorder(tree^.right);
        END;
    END;  {put_praeorder}

  BEGIN {save}
    rewrite(t,filename);
    put_praeorder(tree);
  END;  {save}

PROCEDURE load(VAR tree     : b_tree;
                   filename : string);

  VAR t : FILE OF file_type;

  BEGIN {load}
    create(tree);
    reset(t,filename);
    WHILE NOT eof(t) DO
      BEGIN
        insert(tree,t^.key,t^.data);
        get(t);
      END;
  END;  {load}

Im anderen Fall, also beim Auffinden eines Schlüssels, wird mit der Prozedur put_out(old) der Zeiger old aus dem Baum entfernt. Dazu wird zunächst eine Kopie des Zeigers old angelegt, mit Namen copy_old. Hierauf sind drei Fälle zu unterscheiden:

3.1 Ist der Rechtsnachfolger von copy_old, copy_old^.right=nil,     dann wird old ersetzt durch seinen Linksnachfolger.

3.2 Im anderen Fall, also copy_old^.right<>nil besteht noch die     Möglichkeit, daß der Linksnachfolger,copy_old^.right=nil ist. In diesem Fall wird old durch seinen Rechtsnachfolger ersetzt.

3.3 Der letzte und (all)gemeinste Fall, des Ausfügens eines Knotens Q mit zwei Nachfolgern <>nil, ist ungleich komplizierter.

Deshalb betrachten Sie bitte zunächst Abb.4b.

Q stellt den Knoten dar, der ausgefügt werden soll. In diesem Fall ist Q durch den maximalen Linksnachfolger (S) seines rechten Sohnes (P) zu ersetzen. Eine recht imposante Formulierung, die man sich anhand der Abbildung zunächst verdeutlichen sollte. Für die Ersetzbarkeit von Q durch S ist es notwendig einzusehen, daß S die Funktion von Q vollständig übernehmen kann, daß S also größer als alle Elemente im rechten Teilbaum von Q und kleiner als alle Elemente im linken Teilbaum von Q (ohne S) ist.

Im else-Zweig der zweiten Abfrage von put_out findet man nun genau die algorithmische Beschreibung dieses Vorgangs wieder. Zunächst ist allerdings noch ein Spezialfall abzuhandeln, nämlich, daß P nur einen Linksnachfolger hat. Ist dies nicht der Fall, kommen wir sofort zur oben beschriebenen Gegebenheit. Zunächst wird dazu der Linksnachfolger, genannt max_left, und sein Vater, genannt daddy_max_left, ermittelt (WHILE-Schleife). Hierauf bekommt max_left als Nachfolger die beiden Söhne von old zugewiesen, gleichzeitig muß aber der Vater von max_left den rechten Sohn von max_left (S), N adoptieren. 'Last but not least', wird old durch max_left ersetzt.

Wie Sie sicher zugeben werden, recht verzwickte Familienverhältnisse.

  1. search_first(tree,key,data)

Die Funktion search_first greift zurück auf eine globale Vari-able, present_ptr, und eine Hilfsfunktion, search_ptr, deren Funktion ich zuerst erläutern möchte.

Die Funktion search_ptr(tree,key,list) berechnet den Zeiger auf den Baumrepresentanten der Nachfolgerliste von key. Dieser Zeiger wird dem aufrufenden Programmteil über die Variable list mitgeteilt. Der generelle Erfolg, der Suche, wird über den Funktionsreturn von search_ptr mitgeteilt. Die Arbeitsweise von search_ptr dürfte Ihrem, durch insert und remove geschultem, Auge sofort klar sein: Es ist die übliche rekursive Suche in Bäumen, nur das hier am Ende der Suche keine Datenausgabe, sondern eine Zeigerrückgabe erfolgt.

Mit dieser Hilfsfunktion gestaltet sich nun die Formulierung von search_first sehr einfach. Nach einmaligem Aufruf der Hilfsfunktion, steht der Zeiger present_ptr, soweit vorhanden, auf dem entsprechenden Baumelement. Die bool'sche Variable found beinhaltet den Erfolg/Mißerfolg der Suche. Ist sie true, so kann auf present_ptr^.data zugegriffen werden und unser erster Datensatz ist gefunden.

  1. search_next(data)

Die Weiterführung der Suche nach neuen Elementen, mit durch search_first bezeichnetem Schlüssel, besteht nun einfach aus dem durchgehen der Nachfolgerliste, des mit present_ptr bezeichneten Elementes.

  1. save(tree,filename)

Nach der schreibenden Eröffnung der Datei filename, werden nun die Baumelemente, durch die Hilfsprozedur put_praeorder, in ihrer Präorderabfolge in die Datei geschrieben. Für die Gründe dieser speziellen Elementabfolge, verweise ich auf die Beschreibung der X-order-Durchläufe (siehe unten).

Eingeschachtelt im Präorderdurchlauf, findet noch ein Durchlaufen der Elementnachfolgerlisten statt, um die Daten mehrfach belegter Schlüssel zu speichern.

  1. load(tree,filename)

Nach der Initialisierung des durch tree bezeichneten Baumes, mit create(tree), wird die Datei filename, mit lesendem Zugriff, eröffnet. Die Elemente werden bis zum Dateiende (eof) in den Baum tree eingefügt.

  1. X-order-Durchläufe

Wie schon unter save erwähnt, kommt den X-order-Durchläufen unter bestimmten Bedingungen eine besondere Funktion zu. Allen voran ist hier der inorder-Durchlauf zu erwähnen, welcher eine sortierte Liste der Baumelemente erstellt.

Auch der präorder-Durchlauf hat bei der Implementierung der Prozedur save eine große Bedeutung gespielt. Es läßt sich nämlich feststellen, daß aus der Präorderreihenfolge der zugrunde liegende Baum wiedergewonnen werden kann.

Um ein Beispiel für die Baumstruktur, welche aus einer gewissen Eingabesequenz entsteht und den daraus resultierenden X-order-Durchläufen zu geben, habe ich die Abb.4c angefertigt. Hier sehen Sie den, aus einer Eingabesequenz, entstehenden Binärbaum und die zugehörigen X-order-Sequenzen.

{ Listing 4c)

  Programm test_b_trees liefert eine Testumgebung zu den b_tree Modulen.
  Es wird ein Baum verwaltet, in dem

   - eingefuegt und geloescht werden kann
   - eine Suche nach Daten gleichen Schluessels durchgefuehrt werden kann
   - dateioperationen moeglich sind

  Weiterhin koennen, zusaetzlich zu den Modulfunktionen prae-, post-, und
  inorder Durchlaeufe gemacht werden.

  programmiert : Juni 87
  von          : Dirk Brockhaus
  mit          : PASCAL+ (CCD)
}

PROGRAM test_b_trees (input,output);

TYPE {$i baum_typ.pas}

VAR tree     : b_tree;
    key      : key_type;
    data     : data_type;
    str      : string;
    question : char;

{$i baum.pas}

PROCEDURE drucke_daten(liste : b_tree);

  BEGIN {drucke_daten}
    WHILE liste<>nil DO
      BEGIN
        write(' ',liste^.data);
        liste:=liste^.next;
      END;
  END;  {drucke_daten}

PROCEDURE inorder(tree : b_tree);

  BEGIN {inorder}
    IF tree<>nil THEN
      BEGIN
        inorder(tree^.left);
        write(' Schluessel: ',tree^.key,' Daten: ');
        drucke_daten(tree);
        writeln;
        inorder(tree^.right);
      END;
  END;  {inorder}

PROCEDURE praeorder(tree : b_tree);

  BEGIN {praeorder}
    IF tree<>nil THEN
      BEGIN
        write(' Schluessel: ',tree^.key,' Daten: ');
        drucke_daten(tree);
        writeln;
        praeorder(tree^.left);
        praeorder(tree^.right);
      END;
  END;  {praeorder}

PROCEDURE postorder(tree : b_tree);

  BEGIN {postorder}
    IF tree<>nil THEN
      BEGIN
        postorder(tree^.left);
        postorder(tree^.right);
        write(' Schluessel: ',tree^.key,' Daten: ');
        drucke_daten(tree);
        writeln;
      END;
  END;  {postorder}

BEGIN {main}
  writeln('Test der B-B„ume');
  writeln;
  create(tree);
  REPEAT
    writeln('<1> Einfgen');
    writeln('<2> L”schen eines Schlssels');
    writeln('<3> Suchen nach Schlsselkriterium');
    writeln('<4> Inorder Baumdurchlauf');
    writeln('<5> Pr„order Baumdurchlauf');
    writeln('<6> Postorder Baumdurchlauf');
    writeln('<7> Baum speichern');
    writeln('<8> Baum laden');
    writeln('<9> Baum initialisieren');
    writeln('<0> Beenden');
    write(' > ');
    read(question);
    writeln;
    CASE question OF
      '1' : BEGIN
              write(' Schlssel > ');
              readln(key);
              write(' Daten > ');
              readln(data);
              insert(tree,key,data);
            END;
      '2' : BEGIN
              write(' Schlssel > ');
              readln(key);
              IF NOT remove(tree,key) THEN
                BEGIN
                  writeln(' Dieser Schlssel existierte nicht.');
                  readln;
                END;
             END;
      '3' : BEGIN
              write(' Schlssel > ');
              readln(key);
              IF search_first(tree,key,data) THEN
                BEGIN
                  writeln(' Schlsselliste : ',key);
                  writeln;
                  writeln(' Daten: ');
                  writeln(' ',data);
                  WHILE search_next(data) DO
                    writeln(' ',data);
                END
              ELSE
                writeln(' Schlssel nicht gefunden!');
            END;
      '4' : BEGIN
              writeln(' inorder-Durchlauf:');
              inorder(tree);
              readln;
            END;
      '5' : BEGIN
              writeln(' pr„order-Durchlauf:');
              praeorder(tree);
              readln;
            END;
      '6' : BEGIN
              writeln(' postorder-Durchlauf:');
              postorder(tree);
              readln;
            END;
      '7' : BEGIN
              write(' Dateiname > ');
              readln(str);
              save(tree,str);
            END;
      '8' : BEGIN
              write(' Dateiname > ');
              readln(str);
              load(tree,str);
            END;
      '9' : create(tree);
    END;
  UNTIL question='0';
END.  {main}

Anwendung & Testumgebung

Die Testumgebung für die Module 4a & 4b macht auch gleich die Anwendung plausibel:

Vorausschau

In der nächsten Folge von Algorithmen & Datenstrukturen, werde ich die obige Struktur etwas verfeinern. Ein Stichwort, in diesem Zusammenhang, ist der Begriff des AVL-Baumes.

Demjenigen, dem dies etwas sagt, der hat sicher auch bereits gemerkt, daß ich heute an einer Stelle ein wenig gemogelt habe. Wer also ernsthaft mit den Binärbäumen Daten verarbeiten möchte, der sollte noch bis zum nächsten Monat warten.

Für heute bleibt mir nur noch, mich an dieser Stelle für Ihre Aufmerksamkeit zu bedanken.


Dirk Brockhaus



Links

Copyright-Bestimmungen: siehe Über diese Seite
Classic Computer Magazines
[ Join Now | Ring Hub | Random | << Prev | Next >> ]