Inordnungs-Traversierung ◦ Zusammenfassung ◦ ?

Wir implementieren für Aufgabe a) des Wörterbuch-Projekts die beiden Methoden OErster und ONächster als Ersatz für die For Each ... Next-Schleife (vgl. Beispiel "Wörterbuch Standard"). Das Funktionspaar gibt die Elemente eines sortieren Binärbaumes in sortierter Reihenfolge, also nach der Inordnungs-Vorschrift zurück. Das folgende Programmskelett skizziert noch einmal das Arbeiten mit diesen zwei Funktionen:

    Dim Knoten As CEintrag
    ...
    Set Knoten = BuchDeEn.OErster()
    Do While Not Knoten Is Nothing
      ...
      Set Knoten = BucheDeEn.ONächster(Knoten)
    Loop

Um das erste Element zu finden, beginnt man bei der Wurzel und folgt den linken Ästen solange, bis man auf einen Knoten stösst, der keinen linken Nachfolger hat. Damit ist das gesuchte Element bereits gefunden. Der folgende Entwurfscode formuliert diese Vorschrift rekursiv. Zwei Fälle brechen die Rekursion ab: Wenn der Baum leer ist, existiert kein erstes Element. Wenn ein Knoten keinen linken Nachfolger hat, dann ist der aktuelle Knoten der Gesuchte. Die Reduktion folgt jeweils dem linken Ast.

    OErsterRekursiv(Baum)
      '-- Abbruchbedingung
      Falls Baum leer ist
        gib Nothing zurück
      Sonst falls Baum KEINEN linken Nachfolger hat
        gib Baum zurück
      '-- Reduktion
      Sonst
        gibt ersten Eintrag von linkem Teilbaum von Baum zurück

Beim Aufruf der Prozedur muss der Baum übergeben werden. In der folgenden Implementation ruft die Funktion OErster die Funktion OErsterRekursiv auf und übergibt dabei die Wurzel und damit den gesamten Baum. Jeder rekursive Aufruf übergibt mit einem Knoten jeweils einen Teilbaum.

Klassenmodul cWörterbuch

    Public Function OErster() As CEintrag
      Set OErster = OErsterRekursiv(Wurzel)
    End Function

    Private Function OErsterRekursiv(Baum As CEintrag) As CEintrag
      '-- Abbruchbedingungen
      If Baum Is Nothing Then
        Set OErsterRekursiv = Nothing
      ElseIf Baum.KindLinks Is Nothing Then
        Set OErsterRekursiv = Baum
      '-- Reduktionen
      Else
        Set OErsterRekursiv = OErsterRekursiv(Baum.KindLinks)
      End If
    End Function

Die Vorschrift, die zu einem gegebenen Knoten das nächst grössere Element findet, muss zwei Fälle unterscheiden. Entweder der Knoten hat einen rechten Teilbaum, oder er hat keinen. Ein allfälliger linker Teilbaum kann ignoriert werden, da sich dort gemäss Definition eines sortierten Baumes nur kleinere Knoten befinden können.

Hat der betrachtete Knoten einen rechten Teilbaum, so ist sein Nachfolger der erste Knoten in diesem rechten Teilbaum. Anderenfalls muss der Nachfolger oberhalb des betrachteten Knotens liegen; es muss also in Richtung Wurzel zurück geklettert werden. Der erste Knoten, der einen grösseren Inhalt hat als der aktuelle, ist der Gesuchte. Die Situation tritt immer ein, wenn alle Knoten eines linken Teilbaumes ausgegeben wurden. Nach der Inordnungs-Vorschrift muss dann als nächstes der Knoten selbst zurück gegeben werden, bevor man mit dem rechten Teilbaum fortfährt.

Der folgende Entwurfscode formuliert die Vorschrift iterativ. Sie berücksichtigt, dass man eventuell beim Hochklettern keinen Knoten mit grösserem Inhalt findet. In diesem Fall gibt es keinen Nachfolger mehr und der Algorithmus antwortet mit Nothing.

    ONächster(Knoten)
      Falls Knoten einen rechten Teilbaum hat
        gib ersten Eintrag des rechten Teilbaumes zurück.
      sonst
        beginne bei Knoten
        Wiederhole bis Begriff > Begriff in Knoten
          klettere einen Knoten hoch
          Falls neuer Knoten leer ist
            gibt Nothing zurück
            brich ab.
        gib aktuellen Knoten zurück.

Bei der Implementation des Hochkletterns kommen die Rückwärtsverweise zum Einsatz.

Klassenmodul cWörterbuch

    Public Function ONächster(Knoten As CEintrag) As CEintrag
      If Not Knoten.KindRechts Is Nothing Then
        Set ONächster = OErsterRekursiv(Knoten.KindRechts)
      Else
        Set ONächster = Knoten
        Do Until ONächster.Begriff > Knoten.Begriff
          Set ONächster = ONächster.Vater  'klettere hoch
          If ONächster Is Nothing Then
            Exit Do
          End If
        Loop
      End If
    End Function

Inordnungs-Traversierung

©abo