52. Bäume I

Ein Baum ist eine Datenstruktur, die aus Knoten besteht. Dabei hat genau ein Knoten (die Wurzel) keinen Vorgänger, alle anderen Knoten haben genau einen Vorgänger (es also keine Verweise von Ast zu Ast oder zurück – eine Datenstruktur, bei der das vorkommen darf, heißt Graph) und null oder mehr Nachfolger. Knoten ohne Nachfolger heißen Blätter.

Bäume sind Brot- und Butter-Datenstrukturen der Informatik und sind – durchaus nicht nur in ihrer Inkarnation als Ableitungsbäume – auch in der Computerlinguistik ausgesprochen häufig. Der Hauptgrund, warum wir das hier machen, ist jedoch die Vorbereitung auf die Vorlesung Algorithmen und Datenstrukturen. Dort wird, z.B. zum Aufbau von Listen und eben Bäumen, gern mit Pointern gearbeitet, also Verweisen auf Daten.

In vielen Programmiersprachen braucht man für solche Verweise eigene Datentypen, in Python ist jedoch jede “Variable” lediglich so ein Verweis, eben eine Referenz. Würde man Python-Variablen in C simulieren wollen, wären sie am ehesten void *. Meine Hoffnung ist, dass nach diesem Kapitel klar wird, wie Datenstrukturen, wie sie in der Informatik-Vorlesung dargestellt werden, in Python implementiert werden können.

Ein Baum, in dem jeder Knoten maximal zwei Nachfolger hat, heißt binärer Baum – für viele Anwendungen sind sie ausreichend, weshalb wir unsere Untersuchungen auf sie beschränken.

Ein Knoten muss wissen, welcher Wert in ihm steht und was seine rechten und linken Kinder sind. Das realisiert folgende Python-Klasse:

class BinaryTree:                     def setLeft(self, node):
  def __init__(self, value):            self.left = node
    self.value = value
    self.right = self.left = None     def getRight(self):
                                        return self.right
  def getValue(self):
    return self.value                 def getLeft(self):
                                        return self.left
  def setRight(self, node):
    self.right = node

Dabei ist die Idee, dass left und right auf None stehen, solange der Knoten noch keine Nachfolger hat, und eine andere Klasse oder Funktion nach Bedarf weitere BinaryTrees über die setLeft und setRight-Methoden einhängt.

Wir haben hier sowohl einen Knoten als auch einen Baum modelliert. Das ist möglich, weil ein Baum eine selbstähnliche Datenstruktur ist – an jedem seiner Knoten beginnt eine neuer Baum, bis hinunter zu den Blättern, die letztlich Bäume mit nur einem Wurzelknoten sind.

Es wäre durchaus denkbar (und manchmal ist das auch sinnvoll), den Baum und die Knoten zu trennen, vor allem dann, wenn der ganze Baum andere Eigenschaften hat als ein Teilbaum (bei den Sortierbäumen wird das so sein) – aber wir haben hier die Designentscheidung getroffen, dass ein Knoten eben immer auch die Wurzel eines Baumes sein soll. Hauptgrund für die Entscheidung hier ist, dass ein paar Dinge im Code einfacher aussehen, Hauptnachteil ist, dass die Identität von Baum und Knoten etwas kontraintuitiv sein mag.

Zunächst: Arithmetische Ausdrücke in Bäumen: z.B. (5 - 3)∕(2 × (5 + 4)). Der Ausdrucksbaum dazu:

Zur Auswertung kann man den Baum runterlaufen und von unten anfangend den Wert an jedem Knoten mit einem Operator bestimmen: