Einordnung

  • Interaktionsmodus: funktionsdefinition
  • geschätzter Zeitaufwand:
    • Programmierneulinge: 4 - 5 Stunden
    • Sprachneulinge: 2 - 3 Stunden
    • Spracherfahrene: ca. 1 Stunde

Aufgabe

Implementiert einen Datentyp zur Repräsentation eines binären Baumes. Ein Baum ist hierbei definiert als eine Datenstruktur definiert durch einen Knoten, der sowohl einen rechten als auch einen linken Nachfolger hat. Es handelt sich bei einem Knoten um ein Blatt wenn es keine Nachfolger besitzt. Zusätzlich enthält jeder Knoten ein label (String).

Hierzu definiert folgende Funktionen:

  • left(Baum) bzw. Baum.left() liefert den linken Nachfolger-Knoten.
  • right(Baum) bzw. Baum.right() liefert den rechten Nachfolger-Knoten.
  • insert_left(Baum, Knoten) bzw. Baum.insert_left(Knoten)
  • insert_right(Baum, Knoten) bzw. Baum.insert_right(Knoten)
  • serialize(Baum) bzw. Baum.serialize() liefert eine String-Repräsentation des Baums im sogenannten Dot-Format.

Dot-Format

Das Dot-Format wird in den Grundzügen gut in der englischen Wikipedia beschrieben. Die offizielle Sprachdefinition legt u.A. Einschränkungen bezüglich möglicher Bezeichner fest.

Der Baum kann als gerichteter (digraph) oder ungerichteter (graph) Graph dargestellt werden, die Knoten müssen eindeutig bezeichnet werden und können optional mit einem Label versehen werden. Im Folgenden sei ein Beispielgraph gegeben.

graph tree {
  // Definition der Knoten (nur notwendig, wenn label != Bezeichner)
  a [label="#1"]
  b [label="#2"]
  c [label="Blatt 1"]
  d [label="Blatt 2"]
  e [label="Blatt 3"]

  // Definition der Kanten
  a--c
  a--b
  b--d
  b--e
}

Erzeugt unter Aufruf von dot -Tpng -O <filename> die folgende PNG. mit dot erzeugte Grafik