Diese Übung ist nur für SE-GY!

Theorie Icon

Lernziele
Sie können...
  • den Aufbau von komplexen dynamischen Datenstrukturen analysieren.
  • Methoden und Funktionen für die Datenstruktur Binärbaum implementieren.

Aufgabe 1 - Algorithmen auf Binärbäumen

Binärbaum

Binärbaum - Von Nomen4Omen - Eigenes Werk (Originaltext: self-made), CC BY-SA 3.0 de, https://commons.wikimedia.org/w/index.php? curid=13351847

Binärbäume sind in der Informatik die am häufigsten verwendete dynamische Datenstruktur. Im Gegensatz zu anderen Arten von Baumstrukturen können die Knoten eines Binärbaumes nur höchstens zwei direkte Nachkommen haben (binär).

  • Ein Binärbaum ist entweder leer,
  • oder er besteht aus einer Wurzel mit einem linken und rechten Teilbaum, die wiederum Binärbäume sind.
  • Ist ein Teilbaum leer, bezeichnet man den entsprechenden Kindknoten als fehlend.

Aufgabe Icon

A1: Algorithmen auf und mit Binärbäumen

Die Aufgabe ist es, Algorithmen auf einem Binärbaum zu implementieren. Eine Python-Implementierung eines Binärbaumes ist im OPAL verfügbar.

  1. Implementiere die Funktion _searchRek(self, node, value), die rekursiv nach einem Blatt mit einem festgelegten Wert sucht und diesen zurückliefert. Erweitere die passende Hilfsfunktionen.
  2. Implementiere die Funktion _addAllRek(self, node), die die Werte aller Blätter des Binärbaumes addiert und das Ergebnis zurückliefert. Erweitere die passende Hilfsfunktionen.
  3. Implementiere die Funktion _searchIterativ, die iterativ nach einem Blatt mit einem festgelegten Wert sucht und diesen zurückliefert.
  4. Implementiere die Funktion _addAllIterativ, die die Werte aller Blätter des Binärbaumes iterativ addiert und das Ergebnis zurückliefert.

Aufgabe 2 - Vertiefungsaufgaben zu Binärbäumen

Dies sind reine Wiederholungsaufgaben zur Übung!

Aufgabe Icon

A2a: Die Datenstruktur Binärer Baum implementieren

Implementiere die Datenstruktur Binärer Baum ohne die Lösung der Aufgabe 1 zu Hilfe zu nehmen.

  1. Implementiere die Klasse Node (Knoten/Blatt) mit einer value und einem rechten und linken Kindknoten.
  2. Implementiere die Klasse binTree (Binärbaum), die einen Wurzelknoten als Attribut hat und Methoden zum Suchen und Einfügen von Werten im Binärbaum zur Verfügung stellt.
  3. Implementiere eine Testfunktion, die eine feste Menge beliebiger Werte zum Binärbaum hinzufügt und anschließend alle Elemente sortiert nach der Größe ausgibt.

Aufgabe Icon

A2b: Die Datenstruktur Binärer Baum erweitern
  1. Erweitere die Datenstruktur aus Aufgabe 1 oder 2 so, dass jeder Knoten jetzt drei Kinderknoten hat. Lege dafür eine neue Klasse nodeTr und tertTree an.
  2. Passe die Methoden und Funktionen entsprechend an.
  3. Nutze das Package time um die Suche in den Bäumen bei 100, 1000 und 10000 randomisierten hinzugefügten Werten nach einem bestimmten Element zu vergleichen. Beide Bäume sollten dabei natürlich die gleichen Werte beinhalten.