i

Strukturierung: Rekursive Datenstrukturen

Rekursive Datenstrukturen

In vielen Fällen ist es wichtig, die Beziehungen zwischen einzelnen Daten abbilden zu können, beispielsweise bei den verschiedenen Spezies in einem Stammbaum. Um dies zu ermöglichen, nutzen wir spezielle Strukturen zur Darstellung der Daten: Rekursive Datenstrukturen.

Rekursive Datenstrukturen sind Datenstrukturen, die in ihrer Definition auf sich selbst verweisen. Damit ermöglichen sie es, Beziehungen zwischen einzelnen Daten darzustellen.


So beinhaltet beispielsweise unsere Record-Definition speciesA sich selbst als Datentyp für das Feld speciesA-ancestor.

(define-record speciesA
  make-speciesA
  (speciesA-name string)
  (speciesA-ancestor (mixed speciesA unbekannt)))

Der Selbstverweis einer rekursiven Datenstruktur kann jedoch problematisch werden, wenn Daten vom Typ der Datenstruktur keine entsprechenden Daten haben, auf die diese verweisen können. In unserem Beispiel entsprach dies dem ersten Eintrag des Stammbaums A. afarensis, für den kein Vorfahre im Baum existiert. Wir brauchen daher ein Element, welches wir an diesen Stellen referenzieren können. Wir nennen dies den Basisfall einer rekursiven Datenstruktur.

Für die Record-Definition speciesA definieren wir als Basisfall die Record-Definition unbekannt. Um in Racket anzugeben, dass Daten verschiedener Datentypen akzeptiert werden, nutzen wir den Typ‑Operator mixed.

(define-record unbekannt
  make-unbekannt
  unbekannt?)

(define-record speciesA
  make-speciesA
  (speciesA-name string)
  (speciesA-ancestor (mixed speciesA unbekannt)))

Aufgabe 1: Spezies als Baumstruktur

Bestehende Datei - rekursiveDatenstrukturen.rkt

Mit unseren Definitionen der Records vom Typ speciesA haben wir bereits sämtliche Namen und Verbindungen zwischen den einzelnen Spezies des Stammbaums abgebildet. Einige Fragestellungen lassen sich anhand der Definitionen bisher jedoch nicht automatisiert beantworten. Stammbaum des Menschen

Angenommen, wir möchten Funktionen schreiben, die die folgenden Fragestellungen beantworten:

  1. Wie viele Elemente hat der Stammbaum?
  2. Ist eine Spezies Teil des Stammbaums?
  3. Wie viele Nachfahren stammen von einer Spezies ab?
(a) Erkläre, warum diese Fragestellungen in unserer bisherigen Record-Struktur nicht beantwortbar sind und überlege dir, welche Infos die Records beinhalten müssten, um diese Fragen beantwortbar zu machen.


Eine alternative und in der Praxis gängige Möglichkeit, Stammbäume zu repräsentieren, ist die Nutzung einer rekursiven Baumstruktur. Eine klassische solche Baumstruktur stellt ein Binärbaum dar. Eine Möglichkeit, diesen zu beschreiben, ist die folgende:

;Ein nicht-leerer Binärbaum ist definiert durch:
;einen Wurzelknoten

;Ein Wurzelknoten ist definiert durch:
;einen Wert
;einen linken Nachfolger
;einen rechten Nachfolger

;Ein Nachfolger ist entweder:
;ein nicht-leerer Binärbaum
;oder leer

(b) Schreibe anlog zur Beschreibung eines nicht-leeren Binärbaums, eine Beschreibung für einen Stammbaum. Ersetze hierfür die Begrifflichkeiten des Binärbaums durch die geeigneten Anlogen: Stammbaum, Spezies, Speziesname, Nachfahre, unbekannt.

(c) Schreibe eine Record-Definition speciesB, die eine entsprechende Darstellung einer Spezies ermöglicht.

(d) Definiere unter dem Definitionsnamen speciestree den vollständigen Record der Spezies "A. afarensis". Erkläre anschließend, warum dieser Record den gesamten Stammbaum darstellt.


Verarbeitung rekursiver Datenstrukturen

Möchten wir rekursive Datenstrukturen mit Funktionen verarbeiten, so gilt fast immer, dass auch diese Funktionen rekursiv definiert sein müssen.

Verarbeiten wir beispielsweise Stammbäume, muss die Funktion meist nicht nur auf einer Spezies, sondern auch auf deren Vorfahren/Nachfahren angewandt werden. Wir benötigen einen Rekursionsschritt. Der Rekursionsschritt kann so lange auf der rekursiven Datenstruktur wiederholt werden, bis ein Basisfall erreicht wurde. Beispielsweise wenn kein bekannter Vorfahre/Nachfahre mehr vorhanden ist oder die gesuchte Spezies erreicht wurde.


Aufgabe 2: Rekursive Verarbeitung der Spezies-Baumstruktur

Bestehende Datei - rekursiveDatenstrukturen.rkt

Tipp: Überlege dir für die folgenden Aufgaben jeweils explizit, wie der Basisfall aussieht und durch welche Rekursionsschritte dieser erreicht werden kann.

(a) Schreibe eine Funktion elemente-in-baum, die für einen übergebenen Baum mit Records des Typs SpeciesB die Anzahl aller Elemente im Baum bestimmt.

(b) Schreibe eine Funktion get-elem, die dir für einen übergebenen Speziesnamen den Record der Spezies aus dem Baum zurückliefert.

(c) Schreibe eine Funktion anzahl-nachfahren, die für eine Spezies bestimmt, wie viele im Baum vertretene Spezies von ihr abstammen.

Suche

v
100.137.4.2.1.2 Strukturierung: Rekursive Datenstrukturen
Kopieren durch Anklicken

Rückmeldung geben