Einführung Baumzeichnen

Was ist ein Baum? Was gilt Beim Baum Zeichnen?

Ein Baum ist ein zusammenhängender, azyklischer Graph. In der Regel hat ein Baum T einen Knoten r aus T, der Wurzel genannt wird.
Man geht davon aus, das alle Kanten von der Wurzel weg gerichtet sind. Die Wurzel ist der einzige Knoten ohne ankommende Kanten. Es gibt von der Wurzel zu jedem Knoten genau einen Weg.
Für eine gerichtete Kante (u,v) heißt u Mutter und v Kind. Kein Knoten kann mehr als eine Mutter haben.
Ein Knoten heißt Blatt, wenn er keine Kinder hat.
Die Tiefe eines Knotens ist die Anzahl der Kanten, um ihn von der Wurzel aus zu erreichen.
In einem m-ären Baum hat jeder Knoten maximal m Kinder.
In einem geordneten Baum ist die Ordnung der Kinder eines Knotens entscheidend.
In einem geordneten Binärbaum ist jedes Kind eines Knotens entweder ein rechtes oder linkes Kind. Das heißt, wenn ein Knoten nur ein Kind hat, muss dieses nach rechts oder links gezeichnet werden(Man denke an binäre Suchbäume!) In einem m-ären Baum wird ein einziges Kind direkt unter die Mutter gezeichnet.
Ein Teilbaum mit Wurzel v ist der Teilgraph mit allen Knoten, die auf gerichteten Wegen von v aus erreicht werden können.
Ein freier Baum (ohne spezifizierte Wurzel) kann wie ein gewurzelter Baum gezeichnet werden, indem man eine Wurzel wählt. Ideal ist es die Wurzel so zu wählen, dass die Höhe des Baumes minimal wird:
hat der Baum 1 oder 2 Knoten, so ist das die Mitte.
sonst entferne alle Blätter und wiederhole.

Generelle Wünsche an das Baum Zeichnen

Der Baum wird planar geuzeichnet: keine zwei Kanten kreuzen sich inder Zeichnung des Baumes

  • Gitter Zeichnung des Baumes: Knoten des Baumes haben in der Zeichnung integer Koordinaten
  • Gerade- Linien- Zeichnungen: jede Kante des Baumes ist eine Gerade
  • (streng) aufsteigende Zeichnungen: ein Kind muss (streng) unterhalb der Mutter plaziert sein
  • Ordnungerhaltende Zeichnungen: die Kante von der Mutter zum linkesten (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 Platztverbrauch bei ästhetischem Endergebnis.

Ästhetische Regeln zum Baum Zeichnen (nach Tilford und Reingold)

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