Sommer 2003 bei Prof. Rote, FU-Berlin

Baum Zeichnen in der Informatik

: Algorithmus von Walker, Apporption

Die Seminararbeit zum Baum Zeichnen entstand auf Grundlage des Algorithmus von Walker sowie dessen Verbesserung zum schnelleren Baum Zeichnen von Tilford und Reingold sowie Buchheim, Jünger, Leipert, die das Zeichnen von einem Baum nach dem Algorithmus von Walker in linearer Zeit bieten.

Grundlagen des Baum Zeichnens

Bäume sind eine Untermenge der Menge der Graphen, für die sich leichter ästhetische Algorithmen finden lassen als für Graphen im allgemeinen.

U. a. lässt sich jeder Baum planar zeichnen.

mehr: Baum Definition + Baum Zeichnen Grundlagen

Generelle Wünsche

Planare Zeichnungen: keine zwei Kanten kreuzen
Gitter Zeichnungen: Punkte haben integer Koordinaten
Gerade- Linien- Zeichnungen: jede Kante ist eine Gerade
(streng) aufsteigende Zeichnungen: ein Kind muss (streng) unterhalb der Mutter platziert sein
Ordnungerhaltende Zeichnungen: die Kante von der Mutter zum linksten (rechtesten) Kind muss monoton fallend(steigend) sein. Die Kanten aller Kinder sind nach Winkel von links nach rechts sortiert.
Aufgeräumte Zeichnung(tidy drawing): möglichst wenig Platzverbrauch bei ästhetischem Endergebnis.

: HV-Baum

Ästhetische Regeln (nach Tilford und Reingold)

Knoten gleicher Tiefe sollen auf gerade Linie liegen. Diese Linien sollen parallel sein.
Ein linkes Kind soll links von seiner Mutter liegen und ein rechtes Kind rechts. Dieser Wunsch gilt natürlich nur in Binärbäumen
Die Mutter soll über ihren Kindern zentriert werden.
Ein Baum und sein Spiegelbild sollen gleiche Zeichnungen, die nur gespiegelt sind, erzeugen (Isomorphismus). Ein Teilbaum soll immer gleich gezeichnet werden, egal wo er im Baum erscheint.