Universität Ulm - Abteilung Angewandte Informationsverarbeitung
Die Universität verwaltet zu jedem Studiengang eine Liste, in der alle Studenten mit ihrer Matrikelnummer aufgeführt sind. Die Matrikelnummer dient der eindeutigen Identifikation, da Namen auch doppelt vorkommen können. Ein Beispiel zeigt die folgende Liste:
231243:Sabine Mertens 234512:Martina Werner 954337:Albert Dürer 311212:Joachim Pfeiffer 988838:Uwe Sailer 383772:Sabine Mertens 534332:Julia Jung 234557:Axel Schmid 455883:Albert Dürer
Da solche Listen sehr viele Einträge enthalten können und eine lineare
Suche sehr zeitintensiv ist, sollen die Daten zur Verwaltung in einem
Binärbaum abgelegt werden. Dabei sollen die Knoten des Baumes so
angeordnet werden, daß bei jedem Knoten der linke Unterbaum nur
Daten enthält, die ,,kleiner oder gleich`` (bzgl. einer
vorher definierten Ordnung) der Daten im Knoten selbst
sind. Entsprechend soll der rechte Unterbaum nur Daten enthalten,
die ,,größer`` als die Daten im Knoten selbst sind.
Definieren Sie zunächst eine Struktur für einen binären Suchbaum.
Implementieren Sie anschließend eine Funktion insert, mit der
beliebige Datenstrukturen in den binären Suchbaum eingefügt werden
können. Der Insert-Funktion soll dabei eine
,,Vergleichs``-Funktion (mit Rückgabewert analog zu
strcmp) als Parameter übergeben werden können, die festlegt,
nach welchem Kriterium die Daten in den Baum einsortiert werden.
Die Datensätze sollen von der Standardeingabe eingelesen
und in den den anfänglich leeren Baum eingefügt werden.
Zur Ausgabe soll eine Funktion print implementiert werden,
die, nachdem alle Datensätze eingelesen wurden, die Inhalte der Knoten
des Baumes ,,In Order`` ausgibt.
Ein Ausgabe könnte wie folgt aussehen:
Nach Matrikelnummer sortiert: 231243:Sabine Mertens 234512:Martina Werner 234557:Axel Schmid 311212:Joachim Pfeiffer 383772:Sabine Mertens 455883:Albert Dürer 534332:Julia Jung 954337:Albert Dürer 988838:Uwe Sailer Nach Name sortiert: 954337:Albert Dürer 455883:Albert Dürer 234557:Axel Schmid 311212:Joachim Pfeiffer 534332:Julia Jung 234512:Martina Werner 231243:Sabine Mertens 383772:Sabine Mertens 988838:Uwe Sailer
Hinweis: Im Skript in Kapitel 8.3 ist ein Beispiel zu Funktionszeigern zu finden. Entsprechend sollen die Vergleichsprozeduren an die Insert-Funktion übergeben werden kann.
Viel Erfolg!