• Increase font size
  • Default font size
  • Decrease font size

Der Reingold - Tilford Algorithmus

Der nebenstehende Baum ist komplex und auf einer Oberfläche schwer zu zeichnen. Einfache Algorithmen geben ein verzerrtes Bild wieder. Da jedes Blatt eines Baumes von der Wurzel aus gesehen eine Höhe hat, kann diese trivial als y- Wert verwendet werden. Traversiert man den Baum nach Inorder Logik und vergibt jedem Knoten von eins beginnend einen Wert, so könnte dieser als x - Wert verwendet werden. Es wäre so möglich, einen Baum zu zeichnen der keine Kollisonen aufweist, allerdings einen weit verzogenen, der dem links stehenden nicht entspricht.

 

 

 

Die Vorgehensweise beim vorgestellten Algorithmus beruht auf der Bewertung der einzelnen Knoten. So werden diese am Anfang mit (-1) bzw. (+1) gewertet, je nachdem in welchem Baum sich der Knoten befindet. Das darüber liegende Elternteil erhält aufgrund der notwendigen Zentrierung den Wert null.

In einem Postorderdurchlauf werden für jeden Knoten die Konturen bestimmt und diese in einer z.B. Liste separiert. Eine geeignete Möglichkeit wäre ein Levelorderdurchlauf bei Bäumen, da hier alle Knoten einer Ebene entsprechend ihrer Ebene und ihrer Baumzugehörigkeit erfasst werden können. Nachstehend sind die Konturen für 2 Knoten dargestellt.

Mittels dieser Konturen ist es möglich, den Versatz des Baumes zu bestimmen um ein entsprechendes Bild zu erhalten. Eine etwas detailiertere Beschreibung des Vorgehens findet man in nachfolgendem Script.

   Der Reingold-Tilford Algorithmus

 

 

 

(c) g-ymnasium.de 2006 - 2013 + Administrator