Übungsaufgaben 13

Klassen und Bäume

Bäume sind rekursive Datenstrukturen. Übungen 13.01, 13.02 und 13.03 dienen auch als Wiederholung und Vertiefung rekursiver Funktionen bzw. Methoden (vgl. Vorlesungsskript 19 und Übungsaufgaben 07).

Übungsaufgabe 13.01: Traversierung

Erstellen Sie eine Python-Datei mit der Klasse Tree aus Vorlesungsskript 28. Fügen Sie Methoden preorder und postorder entsprechend den gleichnamigen Funktionen aus Vorlesungsskript 26 hinzu.

Übungsaufgabe 13.02: Gorn-Adressen

Jeder Knoten in einem Baum hat eine „Adresse“, die Gorn-Adresse (benannt nach ihrem Erfinder). Wir stellen Gorn-Adressen hier als Python-Listen dar. Die Adresse der Wurzel ist immer []. Die Gorn-Adresse des ersten Kindes der Wurzel ist [1]. Die Gorn-Adresse des zweiten Kindes der Wurzel ist [2]. Die Gorn-Adresse des ersten Kindes des zweiten Kindes der Wurzel ist [2, 1]. Und so weiter.

Fügen Sie der Tree-Klasse eine Methode get_subtree hinzu, der man eine Gorn-Adresse übergibt und die den Unterbaum zurückgibt, dessen Wurzel an der gegebenen Gorn-Adresse liegt. Zum Beispiel:

>>> tree = Tree('a', Tree('b', Tree('c'), Tree('d', Tree('e'))), Tree('f'))
>>> tree.get_subtree([1, 2])
Tree('d', Tree('e'))

Übungsaufgabe 13.03: Pretty-Printing

Fügen Sie der Tree-Klasse eine Methode pretty_print hinzu, die die Etiketten der Knoten des Baums entsprechend der Baumstruktur eingerückt ausgibt. Zum Beispiel:

>>> tree = Tree('a', Tree('b', Tree('c'), Tree('d', Tree('e'))), Tree('f', Tree('g'), Tree('h')))
>>> tree.pretty_print()
a
  b
    c
  d
     e
  f
    g
    h

Übungsaufgabe 13.04: Klassen definieren und nutzen

Definieren Sie eine Klasse Word, deren Objekte part-of-speech-getaggte Wörter repräsentieren. Die Klasse sollte zwei Attribute haben: form (die Wortform) und pos (das Part-of-Speech-Tag). Geben Sie der Klasse einen passenden Konstruktor und eine __repr__-Methode.

Schreiben Sie eine Funktion, die einen Pfad zu einer zweispaltigen Textdatei als Argument nimmt, wobei in der ersten Spalte Wortformen und in der zweiten Spalte Part-of-Speech-Tags stehen. Die Funktion soll ein Iterable von entsprechenden Word-Objekten zurückgeben.

Ein Beispiel für eine solche Datei finden Sie hier: hirsch.txt. Achtung: Zeilen, die mit # beginnen, sind Kommentare und sollten von Ihrer Funktion ignoriert werden.