Shaw’s grundsatz:

Shaw’s Grundsatz:
11.4. Bäume
Von allen Datenstrukturen, die man mit Hilfe von Pointern darstellen kann, sind Bäume wahrscheinlich die schöns- ten! Ein „Knoten“ (auch: „root“, „Wurzel“) an der Spitze des Baumes zeigt den Weg zu keinem, einem oder mehreren verschiedenen Knoten. Jeder von diesen Knoten kann wieder auf eine verschiedene Gruppe von Knoten Wenn Sie genau hinschauen, sehen Sie einen ganzen Wald von Bäumen. Jeder gezeichnete Knoten hat einen oder mehrere Unterbäume. Wichtig ist, dass jeder Unterbaum seine eigenen Knoten hat; sie müssen sich von denen der anderen Teilbäume unterscheiden. Zwei Unterbäume können sich also nicht einen Knoten „teilen“. Diese Einschränkung macht Bäume zu rekursiv definierten Pointer-Strukturen: Jeder Baum lässt sich definieren als Element, das mit einem, mehreren oder keinem Baum verkettet ist.
Den obersten Knoten eines Baumes bezeichnet man als seine Wurzel. Die Knoten, auf die jedes Ele- ment zeigt, nennt man seine Nachfolger. Ein Knoten, der keine Nachfolger hat, wird als Blatt bezeich- Begrenzt man die Anzahl der Nachfolger bei jedem Knoten auf zwei, dann hat ein Knoten höchstens zwei Unter- bäume. Einen solchen Baum bezeichnet man als Binärbaum. Die Struktur „Binärbaum“ soll nun kurz untersucht Die Definition eines Typs für einen Knoten des BinärBaumes entspricht der für ein Element einer doppelt-verkette- LinksNachfolger, RechtsNachfolger : KnotenPointer Bäume sind rekursiv definiert; daher eignen sich rekursive Verfahren für Operationen auf Baumstrukturen. Dabei geht es beispielsweise um das Durchsuchen von Bäumen oder das Hinzufügen von Knoten.
Ein rekursiver Algorithmus für das Durchsuchen eines Baumes kann umgangssprachlich so formuliert werden: (»AktuellerKnoten« zeigt zu Beginn auf die Wurzel *) 1. Wenn »LinkerNachfolger« des aktuellen Knotens nicht den Wert »NIL« hat, dann rückt man den Hilfspointer »AktuellerKnoten« auf den linken Nachfolger und durchsucht den Baum.
2. Wenn »RechterNachfolger« des aktuellen Knotens nicht den Wert »NIL« hat, dann rückt man den Hilfspointer »AktuellerKnoten« auf den rechten Nachfolger und durchsucht den Baum.
3. Gib den Wert aus, der im aktuellen Knoten gespeichert ist.
Bei der Bearbeitung werden jedes mal, wenn man zu Aktion 1. zurückkehrt, d. h., wenn erneut rekursiv aufgerufen wird, die Werte des aktuellen Knotens zusammen mit allen unerledigten Aktionen gespeichert.
Verwendet man Rekursion, dann ist ein Backtracking ohne Rückwärtssprung möglich.
Der Algorithmus für das Durchsuchen eines Baumes wurde als rekursive Prozedur »DurchsucheBaum« PROCEDURE DurchsucheBaum (AktuellerKnoten : KnotenPointer); (* sucht jeden Knoten eines BinärBaumes *) IF AktuellerKnoten^.LinksNachfolger <> NIL THEN DurchsucheBaum (AktuellerKnoten^.LinksNachfolger); IF AktuellerKnoten^.Rechtsnachfolger <> NIL THEN DurchsucheBaum (AktuellerKnoten^.RechtsNachfolger); Die Wirkung der Prozedur »DurchsucheBaum« lässt sich so beschreiben: Gehe den Baum soweit wie möglich nach unten durch, versuche dabei nach links zu gehen, gehe aber wenn nötig nach rechts. Gib den Wert des erreichten Knotens aus. Gehe einen Knoten zurück und ver- suche nach der beschriebenen Strategie (nach links, wenn möglich; - nach rechts, wenn nötig) erneut nach unten zu gehen, bis ein Blatt oder ein Knoten, den man schon besucht hat, erreicht wird.
Untersuche diesen Knoten und wiederhole dann den Suchvorgang.
Wenn keine Knoten mehr vorhanden sind, die man aufsuchen muss, ist man wieder bei der Wurzel an- gekommen und hat den ganzen Baum durchsucht.
Wenn Sie Schwierigkeiten haben, sich den Ablauf einer rekursiven Prozedur vorzustellen, hilft es Ihnen bestimmt, wenn Sie sich das Durchsuchen an einem Beispielbaum klarmachen. Es ist darüber hinaus auch nützlich, sich die Grenzfälle an einem großen Baum anzuschauen: Wenn man den abgebildeten Baum mir der Prozedur »DurchsucheBaum« durchgeht, dann ergibt sich die Dies ist eine für Sie schwer durchschaubare Schreibweise eines arithmetischen Terms. Er ist in Postfix-Notation - sie wird auch umgekehrte polnische Notation genannt - geschrieben. Darin wird der Operator hinter die Operanden gesetzt. Die Summe von A und B wird A B + statt A + B geschrieben.
Dass sich der Term in dieser Schreibweise ergibt, liegt an der Strategie des Durchsuchens: man geht erst zum linken Nachfolger, dann zum rechten und erst zum Schluss zur Wurzel des Baumes.
Man bezeichnet dieses Durchlaufverfahren daher auch als LRW-Durchlaufen.
Aufgabe:
Nehmen Sie an, dass die drei Anweisungen der Prozedur »DurchsucheBaum« wie folgt umgeordnet werden.
Wird die Prozedur weiterhin funktionieren? IF AktuellerKnoten^. LinksNachfolger <> NIL THEN DurchsucheBaum (AktuellerKnoten^.LinksNachfolger); IF AktuellerKnoten^. RechtsNachfolger <> NIL THEN DurchsucheBaum (AktuellerKnoten^.RechtsNachfolger); IF AktuellerKnoten^. LinksNachfolger <> NIL THEN DurchsucheBaum (AktuellerKnoten^.LinksNachfolger); IF AktuellerKnoten^. RechtsNachfolger <> NIL THEN DurchsucheBaum (AktuellerKnoten^.RechtsNachfolger); Lösung zu Seite 296:
Die Variationen laufen korrekt, aber sie verändern die Reihenfolge beim Durchsuchen.
Die erste Variation bezeichnet man als WLR-Durchsuchen. Dabei kommt die Wurzel zuerst und dann erst die Für den Beispielbaum erhält man folgende Ausgabe: Die zweite Variation liefert ein LWR-Durchsuchen.
Der linke Unterbaum wird durchsucht, dann die Wurzel und schließlich der rechte Unterbaum.
Das ist die Ihnen vertraute Schreibweise (Infix) eines arithmetischen Terms.
11.4.1. Programmieren von Binärbäumen Lynch’s Gesetz:
Die Anwendungsmöglichkeiten für Binärbäume sind unerwartet vielfältig. Schauen Sie sich den folgenden Baum an: Können Sie sich vorstellen, was er darstellt? Vielleicht hilft Ihnen die folgende Typdefinition weiter: Wie Sie vermutlich erraten haben, soll der Baum das Morsealphabet darstellen. Die folgende Prozedur »Deco- diere« verwendet den Baum mit dem Code, um einen durch Morsezeichen verschlüsselten Text zu decodieren. Die Prozedur hat die Parameter »WurzelPointer«, der auf die Wurzel des gespeicherten Baumes verweist, und »DatenFile«, einen Textfile, der Punkte, Striche und Leerzeichen enthält. Da an keiner Stelle zu- rückzugehen ist, braucht man keinen Stapel. Daher ist die Prozedur »Decodiere« auch nicht rekursiv ge- schrieben. Es ist jedoch wichtig, den Pointer zur Wurzel des Baumes festzuhalten, um für jeden neuen Buchstaben den Baum von der Wurzel an durchlaufen zu können.
PROCEDURE decodiere (WurzelPointer : FolgeKnoten; VAR DatenFile : Text); (* decodiert Morsetext; Buchstaben sind durch Leerzeichen getrennt *) ´.´ : AktuellerPointer := AktuellerPointer^.Punkt; ´-´ : AktuellerPointer := AktuellerPointer^.Strich; Die Information für das Entschlüsseln von Morsetexten kann in einem Binärbaum gespeichert werden, da dieser Punkt/Strich-Code im wesentlichen nur eine Serie von Ja / Nein - Antworten ist. Es mag vielleicht überraschen, dass die meisten Daten mit Hilfe von Binärbäumen gespeichert und wiedergeholt werden können. Ein schönes Beispiel dafür ist ein Computerspiel mit dem Namen „Animal“, das ein Spieler mit dem Computer als Spielpartner spielt: Der Computer versucht den Namen eines Tiers, an das der Spieler denkt, zu erraten. Obgleich ein Tier ja bekanntlich viele charakteristische Merkmale hat, soll gleichzeitig nur ein Merkmal betrachtet werden. Auf die gestellten Fragen wie „Hat das Tier einen Pelz?“ „Hat es Hörner?“ antwortet der Spieler entweder mit „Ja“ oder „Nein“. Die Beschreibung für ein Tier wird dadurch auf eine Reihe von Entscheidungsfragen Ein Ausgabebeispiel soll Ihnen eine Vorstellung davon geben, wie das Spiel abläuft: C: Denke an ein Tier! Hat es einen Pelz? Antworte mit Ja oder Nein! Grundlage für das Spiel „Animal“ sind zwei Sorten von Daten: zum einen die Merkmale und zum anderen die Na- men von Tieren. Die entscheidenden Informationen, die Beziehung zwischen Kennzeichen und Name eines Tieres, sind in einem Binärbaum gespeichert. Das Programm startet bei der Wurzel des Baumes und stellt die Frage, die als String in einem Knoten gespeichert ist. Ob als nächstes der nachfolgende linke oder rechte Knoten untersucht wird, hängt von der Antwort des Spielers ab. Es kann sein, dass eine weitere Frage notwendig ist und der Frage- vorgang wiederholt sich. Gelangt man zu einem Blatt des Baumes, hat man den Namen des gesuchten Tiers ge- funden oder aber der Rechner kennt das Tier noch nicht.
Der Rechner kann während des Spielablaufs weitere Tiere kennen lernen. Wenn beim Programmablauf ein Blatt erreicht wurde, ohne das der Rechner den richtigen Namen ausgegeben hat, wenn er also falsch geraten hat, kann der folgende Dialog zwischen dem Computer und dem Spieler beginnen: C: Ich habe falsch geraten. An welches Tier hattest Du gedacht? C: Gib eine zusätzliche Frage ein, die ich noch hätte stellen müssen.
Intern wird nun dem Baum ein neuer Knoten hinzugefügt, der die Information enthält, das ein Wildschwein streng Bei Baumstrukturen ist es oft schwierig zu erkennen, wie Daten gespeichert wurden und wie man sie wieder zu- rückholen kann. Dies trifft besonders dann zu, wenn ein von Hand gezeichneter Baum mit gespeicherten Daten auf den ersten Blick keine Ordnung erkennen lässt. Schauen Sie sich den folgenden Baum an: Der Baum speichert den folgenden Satz von Goethe in alphabetischer Ordnung der Wörter. Dabei wurde kein Unterschied zwischen Groß- und Kleinschreibung gemacht und Satzzeichen wurden nicht gespeichert: Geh den Weibern zart entgegen, du gewinnst sie auf mein Wort. Das erste Wort „Geh“ wird zur Wurzel des Baumes. Das zweite Wort „den“ steht in der alphabetischen Ordnung vor dem ersten Wort und wird daher in dem linken Nachfolger der Wurzel gespeichert. Das dritte Wort „Weibern“ wird, da es in der Ordnung nach dem Wort im Wurzelknoten kommt, im rechten Nachfolger gespeichert. Das vierte Wort „zart“ steht in der Ordnung nach dem Wort im Wurzelknoten und nach dem Wort im rechten Nachfolger des Wurzelknotens und wird daher im rechten Nachfolger des rechten Nachfolgers der Wurzel gespeichert. Der Speicherplatz innerhalb des Baumes wird bestimmt, während man den Baum durchläuft. Man geht entspre- chend der alphabetischen Ordnung nach links oder nach rechts und erstellt dann einen neuen Knoten. Wenn Sie den Baum nach dem LWR-Verfahren durchlaufen, erhalten Sie die Wörter in alphabetischer Reihenfolge.
Wie Sie sich vorstellen können, lässt sich der Algorithmus für den Aufbau des geordneten Baumes rekursiv for- Man baut einen alphabetisch geordneten Baum .
1. Wenn der aktuelle Knoten den Wert »NIL« hat, speichere das neue Wort dort und halte an.
2. Wenn das neue Wort alphabetisch vor dem Wort im aktuellen Knoten steht, verweise auf den linken Nachfolger des Knotens und baue einen alphabetisch geordneten Baum.
3. Wenn das neue Wort alphabetisch nach dem Wort im aktuellen Knoten steht, verweise auf den rechten Nachfolger des Knotens und baue einen alphabetisch geordneten Baum.
4. Wenn das neue Wort und das Wort im aktuellen Knoten gleich sind, halte an.
In der folgenden Prozedur sind diese Schritte programmiert worden. Das letzte »ELSE«, das für den vierten Schritt steht, ist nicht notwendig und kann weggelassen werden. Es sollte hier nur gezeigt werden, wie man alle mögli- TYPE String15 = PACKED ARRAY [1 . 15] OF CHAR; (* weitere Definitionen und Deklarationen *) PROCEDURE OrdneWortEin (VAR Aktuell : WortPointer; NeuesWort : String15); (* fügt ein Wort in einen alphabetisch geordneten Baum ein *) »OrdneWortEin« ist wahrscheinlich die komplizierteste rekursive Prozedur, die bisher im gesamten Skript vor- kam. Beachten Sie, dass es sich um eine End-Rekursion handelt. Der Stapel wird nicht benutzt, um Werte oder unerledigte Anweisungen zu halten. Die Prozedur ließe sich daher auch leicht iterativ schreiben. Wir werden darauf gleich zurückkommen.
Man ist angenehm überrascht, wenn sich herausstellt, wie eine recht schwierig erscheinende Aufgabe nun ganz leicht zu lösen ist. Es geht darum, die Inhalte eines geordneten Baum geordnet auszugeben. Dafür lässt sich eine der möglichen Variationen der Prozedur »DurchsucheBaum« einsetzen, die zum Durchsuchen eines Binär- Baumes geschrieben wurde (vgl. Skript S. 296). Die folgende Version von dieser Prozedur gibt die Namen in alphabetischer Ordnung aus. Gehen Sie davon aus, dass »Aktuell« zu Beginn auf die Wurzel „Geh“ des obigen Beispielbaumes zeigt.
PROCEDURE GeordneteAusgabe (Aktuell : WortPointer); (* gibt die Wörter des Baum alphabetisch geordnet aus *) auf den du entgegen Geh gewinnst mein sie Weibern Wort zart Aufgabe:
Gehen Sie davon aus, dass die Prozedur »OrdneWortEin« angewendet wird, um die Wörter der beiden folgen- den Satzgebilde in einem alphabetisch geordneten Binärbaum zu speichern. Wie sehen die Bäume aus? a.) „Zypresse“ „Yasmin“ „Xerxes“ „Wumpus“ „Venezuela“ b.) „Alle begabten Chinesen danken Egon“ Lösung zur Aufgabe S. 301:
Man entdeckt schnell, dass die Beispielsätze in alphabetischer bzw. in umgekehrter Reihenfolge stehen. Sie er- zeugen daher degenerierte Bäume, die man nicht von gewöhnlichen Listen unterscheiden kann:
Damit wollen wir das Kapitel „Bäume“ abschließen. Ziel dieses Abschnitts war es nicht, Sie vollständig zu befähi- gen, Binärbäume zu programmieren. Es sollte lediglich eine der vielfältigen Anwendungsgebiete der „abstrakte Datenstrukturen“ gezeigt und etwas näher erläutert werden.
Wenn Sie ein weiterführendes Interesse an diesem Themengebiet haben, so lesen Sie bitte in der einschlägigen Als Anregung für besonders Interessierte sei die letzte Aufgabe zum Themenkreis „abstrakte Datenstrukturen“ Ein altes Rätsel handelt von einem Schiff, dass in einen fürchterlichen Sturm geraten ist. An Bord waren 30 Passa- giere, aber nur für 15 von ihnen war Platz in den Rettungsbooten. Um keinen an Bord zurückzulassen, beschloss der Kapitän, die Hälfte der Passagiere über Bord zu werfen, bevor die andere Hälfte die Rettungsbote besteigen Über 15 der Passagiere war der Kapitän ohnedies verärgert, da sie auf der Reise nicht am Kapitänstisch Platz genommen hatten. Dafür wollte er sich nun revanchieren. Er stellte alle Passagiere auf Deck im Kreis auf und warf jeden n-ten über Bord. Die 15 Dinner-Freunde des Kapitäns konnten anschließend die Rettungsbote besteigen; der Kapitän selbst ging mit seinem Schiff unter.
Mit welcher Zahl n hat der Kapitän abgezählt? Verwenden Sie eine Ringliste, um den schrecklichen Zählprozess zu simulieren und herauszufinden, welche Zahl n das gewünschte Ergebnis liefert (Hinweis: sie ist kleiner als 30). Die Aufstellung in der Startliste sehen Sie unten: Die mit X markierten Passagiere gehen über Bord, die mit o in die Rettungsboote. Der Pfeil zeigt auf die Stelle, an der man mit dem Zählen beginnt.

Source: http://netzker.eu/resources/Block070.pdf