Algorithmus von Walker

Der Algorithmus von Walker zum ästhetischen Baumzeichnen in (nahezu) linearer Zeit

Baum Zeichnen nach Walker

Walkers Algorithmus zum Baumzeichnen

Grundlage des Algorthmus von Walker und aller darauf basierenden Baum Zeichnungen ist die geschichtete Baum Zeichnung (Layered Drawings) bei der die Y-Koordinate eines jeden Knoten des Baumes sich direkt aus der Tiefe des Knotens ergibt. Daher muss der Algorithmus von Walker beim Baumzeichnen nur die X-Koordinate des jeweiligen Baumknotens in der Zeichnung bestimmen.

Dieses lässt sich leicht in O(n) Zeit erledigen.

Wetherell und Shannon stellten eine verbesserte Version des Algorithmus von Walker zum Baum Zeichnen vor:

Der Algorithmus von Wetherell und Shannon funktioniert nur mit Binärbäumen. Er beachtet
nicht die 4. ästhetische Regel (Isomorphismus)
Der Algorithmus produziert zum Teil Ergebnisse, deren Platzanforderung nach den 3
beachteten ästhetischen Regeln nicht minimal ist (Bsp siehe unten).
firstWalk{
  für (alle Knoten in post-Order){
    Falls (Knoten hat n Kinder){
      n == 0: Knoten.x <- nächst mögliche Position
      n == 1: Knoten.x <- 1 Einheit rechts/links von Kind
      n == 2: zentriere Knoten über Kindern
    }
    wenn (Knoten.x < nächst mögliche Position)
      Knoten.x <- nächst mögliche Position
    Teilbäume geschifftet
  }
}
Wäre der Knoten, auf den der Pfeil zeigt, weiter
links, wäre der Platzbedarf des Baumes kleiner bei
weiterer Beachtung aller Regeln.