Robert Sedgewick: Algorithmen

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


5. Rekursion



Rekursive Traversierung von Bäumen

Wie in Kapitel 4 ausgeführt wurde, führt der vielleicht einfachste Weg für die Traversierung der Knoten eines Baumes über eine rekursive Implementation. Beispielsweise bewirkt das folgende Programm eine Inorder-Traversierung der Knoten eines binären Baumes:

    procedure traverse(t: link);
      begin
      if t<>z then
        begin
        traverse(t^.l);
        visit(t);
        traverse(t^.r);
        end
      end;

Diese Implementation spiegelt exakt die Definition der Inorder-Traversierung wider: »Falls der Baum nicht leer ist, traversiere zuerst den linken Unterbaum, besuche dann die Wurzel, traversiere dann den rechten Unterbaum.« Offensichtlich kann eine Preorder-Traversierung implementiert werden, indem der Aufruf von visit vor die beiden rekursiven Aufrufe gesetzt wird; eine Postorder-Traversierung kann implementiert werden, indem der Aufruf von visit hinter diese Aufrufe gesetzt wird.

Diese rekursive Implementation der Traversierung eines Baumes ist natürlicher als eine Implementation, bei der ein Stapel benutzt wird, weil einerseits Bäume rekursiv definierte Strukturen sind und weil andererseits Preorder, Inorder und Postorder rekursiv definierte Prozesse sind. Im Gegensatz dazu ist anzumerken, daß es keinen geeigneten Weg gibt, um ein rekursives Verfahren für (beispielsweise) eine Level-Order-Traversierung zu implementieren. Auf diese Frage kommen wir in den Kapiteln 29 und 30 zurück, wo wir Algorithmen für die Traversierung von Graphen betrachten, welche wesentlich kompliziertere Strukturen als Bäume darstellen.

Durch einfache Modifikationen des obigen rekursiven Programms und eine geeignete Implementation von visit kann man Programme erhalten, die verschiedene Eigenschaften von Bäumen auf sehr einfache Weise berechnen. Zum Beispiel zeigt das folgende Programm, wie die Koordinaten für die Anordnung der Knoten der binären Bäume in den Abbildungen im vorliegenden Buch berechnet werden könnten. Es wird angenommen, daß der Datensatz für Knoten zwei ganzzahlige Felder für die Koordinaten x und y des Knotens in der Abbildung enthält. (Um Einzelheiten der Wahl des Maßstabs und der Umrechnung zu umgehen, wird angenommen, daß es sich dabei um relative Koordinaten handelt: Falls der Baum N Knoten besitzt und die Höhe h hat, läuft die x-Koordinate von links nach rechts von 1 bis N und die y-Koordinate von oben nach unten von 1 bis h.) Das folgende Programm trägt für jeden Knoten die entsprechenden Werte in diese Felder ein:

    procedure visit(t: link);
      begin x:=x+1; t^.x:=x; t^.y:=y end;
    procedure traverse(t: link);
      begin
      y:=y+1;
      if t<>z then
        begin
        traverse(t^.l);
        visit(t);
        traverse(t^.r)
        end
      y:=y-1;
      end;

In diesem Programm werden zwei globale Variablen x und y verwendet, wobei angenommen wird, daß beide mit 0 initialisiert werden. Die Variable x registriert die Anzahl der Knoten, die bei einer Inorder-Traversierung besucht worden sind; die Variable y speichert die Höhe des Baums. Jedesmal, wenn traverse sich im Baum abwärts bewegt, wird y um 1 erhöht, und bei jeder Bewegung im Baum aufwärts wird y um 1 verringert.

In ähnlicher Weise könnte man rekursive Programme implementieren, um die Weglänge eines Baums zu berechnen, um einen anderen Weg zum Zeichnen eines Baums zu implementieren, um einen Ausdruck auszuwerten, der durch einen Ausdrucks-Baum dargestellt ist usw.


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