Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


4. Bäume



Darstellung binärer Bäme

Die gebräuchlichste Darstellung von binären Bäumen ist eine einfache Benutzung von Datensätzen mit zwei Verkettungen pro Knoten. Im Normalfall verwenden wir für die Verkettungen die Namen l und r (Abkürzungen für »links« und »rechts«), um darauf hinzuweisen, daß die für die Darstellung gewählte Anordnung der Art und Weise entspricht, in der der Baum abgebildet ist. Für manche Anwendungen kann es zweckmäßig sein, zwei verschiedene Typen von Datensätzen zu haben, einen für innere und einen für äußere Knoten; für andere kann es angebracht sein, nur einen Knotentyp zu benutzen und die Verkettungen in äußeren Knoten für einen anderen Zweck zu verwenden.

Als Beispiel für die Benutzung und Konstruktion binärer Bäume wenden wir uns wieder dem einfachen Beispiel aus dem letzten Kapitel zu, welches die Verarbeitung arithmetischer Ausdrücke betraf. Wie Abbildung 4.4 zeigt, besteht eine grundlegende Analogie zwischen arithmetischen Ausdrücken und Bäumen.

Für die Argumente benutzen wir aus einem einzelnen Zeichen bestehende Namen anstelle von Zahlen; der Grund hierfür wird weiter unten klar werden. Der Syntaxbaum für einen Ausdruck wird durch die einfache rekursive Regel definiert: »Man setze den Operator an die Wurzel und setze dann den Baum für den Ausdruck, der dem ersten Operanden entspricht, auf die linke Seite, und den Baum, der dem Ausdruck für den zweiten Operanden entspricht, auf die rechte Seite.« Die Abbildung 4.4 ist folglich der Syntaxbaum für A B C + D E * * F + * (der gleiche Ausdruck in Postfix-Notation); Infix und Postfix sind zwei Arten der Darstellung arithmetischer Ausdrücke, Syntaxbäume sind eine dritte Möglichkeit.

Abbildung 4.4
Abbildung 4.4 Syntaxbaum für A*(((B+C)*(D*E))+F).

Da die Operatoren genau zwei Operanden verwenden, ist ein binärer Baum für diese Art von Ausdrücken geeignet. Kompliziertere Ausdrücke können einen anderen Baumtyp erfordern. Wir werden in Kapitel 21 ausführlicher auf diese Frage zurückkommen; im Moment besteht unser Ziel einfach darin, eine Darstellung eines arithmetischen Ausdrucks in Gestalt eines Baumes zu konstruieren.

Das folgende Programmstück bewirkt den Aufbau eines Syntaxbaumes für einen arithmetischen Ausdruck aus einer Postfix-Eingabe. Es handelt sich um eine einfache Modifikation des im vorangehenden Kapitel angegebenen Programms zur Auswertung von Postfix-Ausdrücken unter Verwendung eines Stapels. Anstatt die Ergebnisse von Zwischenrechnungen im Stapel abzulegen, speichern wir Ausdrucksbäume.

    type link=^node;
         node= record info: char; l,r: link end;
    var x,z: link;
        c: char; 
    begin
    stackinit; 
    new(z); z^.l:=z; z^.r:=z;
    repeat
      repeat read(c) until c<>' ';
      new(x); x^.info:=c; 
      if (c='*') or (c='+') 
        then begin x^.r:=pop; x^.l:=pop end;
        else begin x^.r:=z; x^.l:=z end;
      push(x)
    until eoln;

Die Prozeduren stackinit, push und pop beziehen sich hierbei auf den Stapel-Code aus Kapitel 3, mit dem Unterschied, daß sie anstelle von ganzen Zahlen Verkettungen (links) im Stapel ablegen. Auf den Code dafür wird hier verzichtet. Jeder Knoten besitzt ein Zeichen und zwei Verkettungen zu anderen Knoten. Jedesmal, wenn ein neues nichtleeres Zeichen vorgefunden wird, wird unter Verwendung des Pascal- Befehls new ein Knoten dafür erzeugt. Wenn es sich um einen Operator handelt, befinden sich Unterbäume für seine Operanden an der Spitze des Stapels, genau wie bei der Auswertung von Postfix-Ausdrücken. Wenn es ein Operand ist, so sind seine Verkettungen Null. Anstatt Verkettungen mit dem Wert Null zu verwenden, wie bei Listen, benutzen wir einen Pseudoknoten z, dessen Verkettungen auf ihn selbst zeigen. In Kapitel 14 betrachten wir ausführlich, wie sich dadurch gewisse Operationen mit Bäumen vereinfachen lassen. Abbildung 4.5 zeigt die Zwischenstufen bei der Konstruktion des Baumes in Abbildung 4.4.

Abbildung 4.5
Abbildung 4.5 Konstruktion des Syntaxbaumes für A B D + D E ** F +*.

Dieses recht einfache Programm kann dahingehend abgeändert werden, daß es die Behandlung komplizierterer Ausdrücke ermöglicht, einschließlich solcher, bei denen die Operatoren ein einzelnes Argument enthalten, wie etwa Potenzen. Der Mechanismus ist jedoch sehr allgemein: Genau der gleiche Mechanismus wird zum Beispiel verwendet, um die Syntaxanalyse bei der Kompilierung von Pascalprogrammen vorzunehmen. Wenn der Syntaxbaum erst einmal erstellt worden ist, kann er für viele Zwecke verwendet werden, wie etwa für die Auswertung des Ausdrucks oder die Erzeugung von Programmen zur Auswertung des Ausdrucks. In Kapitel 21 werden allgemeine Verfahren zum Aufbau von Syntaxbäumen behandelt. Später werden wir sehen, wie der Baum selbst benutzt werden kann, um den Ausdruck auszuwerten. Für die Zwecke des vorliegenden Kapitels interessieren wir uns jedoch vor allem für die Mechanismen zur Konstruktion des Baumes.

Wie bei verketteten Listen gibt es stets die Alternative, anstelle von Zeigern und Datensätzen parallele Felder zu verwenden, um die Datenstruktur des binären Baumes zu implementieren. Wie dort ist dies besonders dann von Nutzen, wenn die Anzahl der Knoten im voraus bekannt ist. Und ebenfalls wie im o.g. Fall wird diese Alternative für den Spezialfall benötigt, daß die Knoten für einen bestimmten anderen Zweck in einem Feld gespeichert werden müssen.

Die oben benutzte Darstellung binärer Bäume mit zwei Verkettungen erlaubt es, am Baum abwärts zu gehen, doch man hat keine Möglichkeit, sich am Baum aufwärts zu bewegen. Die Situation entspricht der Gegenüberstellung von einfach verketteten Listen und doppelt verketteten Listen: Man kann jedem Knoten eine weitere Verkettung hinzufügen, um mehr Bewegungsfreiheit zu ermöglichen, jedoch auf Kosten einer komplizierteren Implementation. Bei höher entwickelten Datenstrukturen stehen verschiedene andere Möglichkeiten zur Verfügung, um die Bewegung innerhalb des Baumes zu erleichtern, doch ist für die Algorithmen im vorliegenden Buch die Darstellung mit zwei Verkettungen im allgemeinen ausreichend.

Im obigen Programm verwendeten wir einen »Pseudoknoten« anstelle von äußeren Knoten. Wie bei verketteten Listen erweist sich das in den meisten Situationen als günstig. Allerdings ist es nicht immer zweckmäßig, und es gibt zwei weitere Lösungen, die dann gewöhnlich zur Anwendung kommen. Eine Möglichkeit ist, für äußere Knoten einen anderen Knotentyp zu benutzen, einen ohne Verkettungen. Eine andere Methode besteht darin, die Verkettungen in irgendeiner Weise zu markieren (um sie von anderen Verkettungen im Baum zu unterscheiden) und sie dann im Baum woandershin zeigen zu lassen; eine Möglichkeit hierfür wird noch erörtert werden. In den Kapiteln 14 und 17 werden wir uns nochmals dieser Frage zuwenden.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]