Prof. Franz Schweiggert Abteilung Angewandte Informationsverarbeitung 22. November 2002
Christian Ehrhardt Blatt 6






Allgemeine Informatik 3 (WS 2002/2003)


Abgabetermin 2.12.2002

Namensbäume (10 Punkte)

In diesem Blatt soll eine Liste von Namen (eine Folge von maximal 30 Klein- und Großbuchstaben) mit Nummern versehen werden. Der erste Name bekommt die Nummer 0, der zweite die Nummer 1 usw. Ein Name der schon früher in der Liste aufgetaucht ist bekommt keine neue Nummer. Statt dessen soll eine Meldung ausgegeben werden, daß der Name mehrmals vorkommt und welche Nummer er beim ersten Mal bekommen hat.
Es gibt verschiedene mögliche Datenstrukturen für dieses Problem, hier soll ein alphabetisch sortierter Binärbaum für die Namen verwendet werden. Am Ende sollen drei Dinge ausgegeben werden:

• Die Tiefe des Baums, d.h. die maximale Anzahl von Knoten auf dem Weg von der Wurzel zu einem Blatt.
• Die Zahl der Elemente im Baum.
• Die kleinstmögliche Tiefe, die ein Binärbaum mit dieser Zahl von Elementen haben kann.

Zum testen gibt es einige Eingabedateien. Von diesen sollte Euer Programm die ersten 4 in erträglicher Zeit verarbeiten können. Warum ist die letzte Datei so viel Zeitaufwendiger als die anderen?