Robert Sedgewick: Algorithmen

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


4. Bäume



Traversierung von Bäumen

Nachdem ein Baum konstruiert worden ist, muß man vor allem wissen, wie man ihn traversieren kann, d. h., wie man systematisch jeden Knoten besuchen kann. Diese Operation ist für lineare Listen aufgrund ihrer Definition trivial, doch für Bäume gibt es eine Reihe verschiedener Vorgehensweisen. Diese Methoden unterscheiden sich vor allem hinsichtlich der Reihenfolge, in der die Knoten aufgesucht werden. Wie wir sehen werden, sind für unterschiedliche Anwendungen verschiedene Reihenfolgen der Knoten zweckmäßig.

Zunächst konzentrieren wir uns auf die Traversierung binärer Bäume. Aufgrund der Äquivalenz zwischen Wäldern und binären Bäumen sind die Methoden für Wälder ebenso anwendbar, doch erwähnen wir später auch, wie sich die Verfahren direkt auf Wälder anwenden lassen.

Die erste Methode, die zu betrachten wäre, ist die Preorder-Traversierung, welche zum Beispiel benutzt werden kann, um den durch den Baum von Abbildung 4.4. dargestellten Ausdruck in Prefix-Notation auszugeben. Die Methode wird durch folgende einfache rekursive Regel definiert: »Besuche die Wurzel, besuche dann den linken Unterbaum, besuche dann den rechten Unterbaum.« Für die einfachste Implementation dieses Verfahrens, die von rekursiver Art ist, wird im nächsten Kapitel gezeigt, daß sie eng mit der folgenden, einen Stapel benutzenden Implementation verknüpft ist:

    procedure traverse(t: link);
      begin
      push(t);
      repeat
        t:=pop; 
        visit(t);
        if t<>z then push(t^.r); 
        if t<>z then push(t^.l); 
      until stackempty;
      end;

(Es wird vorausgesetzt, daß der Stapel außerhalb dieser Prozedur initialisiert wird.) Entsprechend der Regel »besuchen« wir einen Unterbaum, indem wir zuerst die Wurzel besuchen. Da wir nicht beide Unterbäume auf einmal besuchen können, speichern wir dann den rechten Unterbaum in einem Stapel und suchen den linken Unterbaum auf. Nachdem der linke Unterbaum traversiert worden ist, befindet sich der rechte Unterbaum an der Spitze des Stapels; nun kann er besucht werden. Die Abbildung 4.9 zeigt den Ablauf dieses Programms bei Anwendung auf den binären Baum von Abbildung 4.2: die Reihenfolge, in der die Knoten traversiert werden, ist P M S A A L E R T E E.

Abbildung 4.9
Abbildung 4.9 Preorder-Traversierung.

Um zu beweisen, daß dieses Programm tatsächlich die Knoten des Baums entsprechend einer Preorder-Traversierung besucht, kann man eine Induktion mit der Induktionsvoraussetzung anwenden, daß die Unterbäume entsprechend einer Preorder-Traversierung besucht werden und der Inhalt des Stapels unmittelbar vor der Traversierung eines Unterbaums der gleiche ist wie unmittelbar danach.

Betrachten wir nunmehr die Inorder-Traversierung, welche zum Beispiel verwendet werden kann, um arithmetische Ausdrücke entsprechend Syntaxbäumen in Infix-Notation zu schreiben (mit einem gewissen zusätzlichen Aufwand, um mit den Klammern zurechtzukommen). In ähnlicher Weise wie bei der Preorder-Traversierung wird die Inorder-Traversierung mit Hilfe der folgenden rekursiven Vorschrift definiert: »Besuche den linken Unterbaum, besuche dann die Wurzel, besuche dann den rechten Unterbaum.« Aus offensichtlichen Gründen wird dies manchmal auch symmetrische Reihenfolge genannt. Die Implementation eines einen Stapel verwendenden Programms für die Inorder-Traversierung ist mit dem obigen Programm nahezu identisch; wir verzichten hier darauf, sie anzugeben, da es sich um eines der Hauptthemen des folgenden Kapitels handelt. Abbildung 4.10 zeigt, wie die Knoten im Baum von Abbildung 4.2 bei einer Inorder-Traversierung besucht werden: Die Knoten werden in der Reihenfolge A S A M P L E T R E E traversiert. Dieses Traversierungsverfahren ist wahrscheinlich das am weitesten verbreitete; zum Beispiel spielt es in den Anwendungen der Kapitel 14 und 15 eine zentrale Rolle.

Abbildung 4.10
Abbildung 4.10 Inorder-Traversierung.

Der dritte Typ einer rekursiven Traversierung, Postorder-Traversierung genannt, wird natürlich mit Hilfe der folgenden rekursiven Vorschrift definiert: »Besuche den linken Unterbaum, besuche dann den rechten Unterbaum, besuche dann die Wurzel.« Abbildung 4.11 zeigt, wie die Knoten des Baumes von Abbildung 4.2 bei einer Postorder-Traversierung besucht werden: Die Knoten werden in der Reihenfolge A A S M T E E R E L P traversiert. Die Traversierung des in Abbildung 4.4 dargestellten Baumes nach dem Postorder-Prinzip liefert, wie zu erwarten war, den Ausdruck A B C + D E * * F + *. Die Implementation eines einen Stapel benutzenden Programms für eine Postorder-Traversierung ist komplizierter als für die beiden anderen Methoden, denn es muß gewährleistet werden, daß die Wurzel und der rechte Unterbaum gespeichert sind, während der linke Unterbaum traversiert wird, und daß die Wurzel gespeichert ist, während der rechte Unterbaum traversiert wird. Die Einzelheiten dieser Implementation werden dem Leser als Übung überlassen.

Abbildung 4.11
Abbildung 4.11 Postorder-Traversierung.

Die vierte Traversierungs-Strategie, die wir betrachten, ist überhaupt nicht rekursiv: Wir traversieren einfach die Knoten so, wie sie in der Abbildung erscheinen, indem wir von oben nach unten und von links nach rechts lesen. Dies wird als Level-Order-Traversierung bezeichnet, weil alle Knoten einer jeden Ebene gemeinsam und der Reihe nach erscheinen. Abbildung 4.12 zeigt, in welcher Reihenfolge die Knoten des Baumes von Abbildung 4.2 bei einer Level-Order-Traversierung aufgesucht werden.

Abbildung 4.12
Abbildung 4.12 Level-Order-Traversierung.

Bemerkenswert ist, daß eine Level-Order-Traversierung realisiert werden kann, indem das obige Programm für eine Preorder-Traversierung mit einer Schlange anstelle eines Stapels benutzt wird:

    procedure traverse(t: link);
      begin
      put(t);
      repeat
        t:=get; 
        visit(t);
        if t<>z then put(t^.l); 
        if t<>z then put(t^.r); 
      until queueempty;
    end;

Einerseits ist dieses Programm mit dem obigen scheinbar identisch; der einzige Unterschied ist die Verwendung einer Datenstruktur vom Typ FIFO, während das andere Programm eine Datenstruktur vom Typ LIFO verwendet. Andererseits verarbeiten diese Programme Bäume nach grundsätzlich unterschiedlichen Verfahren. Diese Programme verdienen ein sorgfältiges Studium, da aus ihnen das Wesen des Unterschieds zwischen Stapeln und Schlangen sichtbar wird. In Kapitel 30 kommen wir auf diese Frage zurück.

Preorder-, Postorder- und Level-Order-Traversierung lassen sich ebenso auch für Wälder definieren. Um widerspruchsfreie Definitionen zu erhalten, stelle man sich einen Wald als einen Baum mit einer imaginären Wurzel vor. Dann lautet die Regel für die Preorder-Traversierung: »Besuche die Wurzel und besuche dann jeden der Unterbäume.« Die Regel für die Postorder-Traversierung lautet: »Besuche jeden der Unterbäume und besuche dann die Wurzel.« Die Regel für die Level-Order-Traversierung ist die gleiche wie für binäre Bäume. Zu beachten ist, daß die Preorder-Traversierung für einen Wald mit der Preorder-Traversierung für den oben definierten entsprechenden binären Baum übereinstimmt, und daß die Postorder-Traversierung für einen Wald mit der Inorder-Traversierung für den binären Baum übereinstimmt, während die Level-Order-Traversierungen nicht übereinstimmen. Direkte Implementationen unter Verwendung von Stapeln und Schlangen sind unmittelbare Verallgemeinerungen der oben angegebenen Programme für binäre Bäume.


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