Universität Ulm - Abteilung Angewandte Informationsverarbeitung
Universität Ulm - Abteilung Angewandte Informationsverarbeitung
Ihr bester Freund ist Leiter einer Firma und speichert die
Gehaltsvorstellungen seiner Mitarbeiter in einem Binarbäum
ab. Den Inhalt des Rootknotens legt er dabei selber fest,
da dies seine persönliche Schmerzgrenze darstellt.
Gehaltsvorstellungen die größer sind als die Schmerzgrenze
kommen auf die rechte Seite, Gehaltsvorstellungen die kleiner
gleich der Schmerzgrenze sind auf die linke Seite. Jeder
Mitarbeiter der mit seinen Gehaltsvorstellungen auf der
rechten Seite des Baumes steht bekommt einen Rüffel. Der
Mitarbeiter mit den höchsten Gehaltsvorstellungen wird sofort
entlassen, derjenige mit den niedrigsten Vorstellungen ebenfalls,
da weder Wahnsinnige noch schlaffe kuschende Gurken in der
Firma erwünscht sind!
Gut, soweit die Tatsachen. Ihr Freund möchte nun die schlaffe Gurke
und den Wahnsinnigen aus dem Baum entfernen (Zusatzaufgabe) und
anschließend berechnen, wie hoch die Gehaltsvorstellungen aller
Mitarbeiter zusammen sind (also alle Knoteninhalte addieren, außer
den Inhalt vom Rootknoten)! So kann er festestellen, ob diese
Vorstellungen mit seinem Budget vereinbar sind!
Teilaufgabe a: (5 Punkte)
Erstellt zunächst ein Programm mit einer Prozedur Init für
die Initialisierung, einer Prozedur Insert zum Einfügen
der Gehaltsvorstellungen und einer Prozedur PrintTree
zur Ausgabe des Baumes. Dabei sollen die Gehaltsvorstellungen
von der Tastatur - wie im folgenden Beispiel dargestellt -
eingelesen werden können.
Geben Sie die Schmerzgrenze ein? 6300 Wieviele Gehaelter wollen sie eingeben? 4 Ihre 1. Gehaltsvorstellung? 7600 Ihre 2. Gehaltsvorstellung? 3500 Ihre 3. Gehaltsvorstellung? 4500 Ihre 4. Gehaltsvorstellung? 8798 3500 4500 6300 7600 8798
Teilaufgabe b: (5 Punkte)
Erweitert nun Euer Programm so, daß zusätzlich auch die Summe
aller Knoten ausgegeben wird (Merke: Hier könnte man auch auf
einfache Art und Weise die Anzahl der Knoten feststellen, da
ja jeder Knoten ,,angefaßt`` werden muß)!
Ist dies geschafft, so müßt Ihr zum Schluß nur noch den
Betrag der Schmerzgrenze von den Gesamtgehaltsvorstellungen
abziehen! Fertig!
Geben Sie die Schmerzgrenze ein? 6300 Wieviele Gehaelter wollen sie eingeben? 4 Ihre 1. Gehaltsvorstellung? 7600 Ihre 2. Gehaltsvorstellung? 3500 Ihre 3. Gehaltsvorstellung? 4500 Ihre 4. Gehaltsvorstellung? 8798 3500 4500 6300 7600 8798 Die Summer der Inhalte aller Knoten ist 30698! Die Summe aller Gehaltsvorstellungen ist 24398!
Zusatzaufgabe: (5 Punkte)
Wie bereits gesagt: Der Chef steht weder auf Wahnsinnige noch
auf schlaffe Gurken. Also sucht den Knoten der ganz links
im Baum bzw. ganz rechts im Baum steht, löscht diese beiden
Knoten aus dem Baum und bildet dann die Summe der Gehaltsvorstellungen!
Ihr schönster Baum ist leider doch noch nicht so ganz der Schönste...
...er ist nämlich nicht ausgeglichen und hängt etwas in der Luft, wie
Abbildung 1 zeigt!
Teilaufgabe a: (3 Punkte)
Hängt nun einen Teilbaum, bestehend aus mind. 2 Knoten so um, daß der
Baum höhen- bzw. gewichtsausgeglichen ist (und Ihr schönster Baum wird).
Ist dies überhaupt möglich bzw. wieviele Teilbäumene müssen umgehängt
werden, damit Höhen- bzw. Gewichtsausgeglichenheit erreicht wird?
Teilaufgabe b: (2 Punkte)
Erweitert den ursprünglichen Baum so, daß der Baum durch Hinzufügen
von möglichst wenig Knoten wiederum zum schönsten Baum wird, also
höhen- bzw. gewichtsausgeglichen ist!
Viel Erfolg!
![\includegraphics[scale=0.22]{Baum1}](img2.png)