Binärer Baum
Aufgabe 1:
Der dargestellte Baum soll gezeichnet werden. Mit Stufe sei die Anzahl der Äste
von der Wurzel bis zu einer Spitze bezeichnet.
Hinweise zur Lösung:
- An der Wurzel stehend hat die Turtle das Problem, einen Baum mit z.B der Stufe
10 zu zeichnen.
- Wenn sie den Stamm gezeichnet hat, hat sie das ursprüngliche Problem
um eine Stufe vereinfacht. Jetzt muss sie sich nur noch geeignet drehen,
zwei "Bäume" mit einer um 1 verringerten Stufe und kleinerer Stammlänge
zeichnen und an ihren Startpunkt zurückkehren.
- In der gleichen Situation ist sie bei jedem Ast.
In diesem Sinne ist das Problem rekursiv, also bietet sich eine rekursive
Lösung an.
- Ein ähnliches Problem hatten wir, als Kara ein Mobile durchsuchen sollte.
Damals haben wir das Problem rekursiv gelöst. Allerdings traten damals
noch keine Parameter für die Methode auf.
- Formuliere eine Methode baum(int stufe, double laenge),
die durch den Aufruf baum(10, 100) im Hauptprogrammteil zeichne()
den angegebenen Baum zeichnet. Der Baum hat dann 10 Äste von der
Wurzel bis einer Spitze und 100 sei die Länge des ersten Stammes.
In den folgenden Stufen soll die Astlänge jeweils halbiert werden.
Zusatzbemerkungen:
- Der dargestellte Baum hat eine fraktale Struktur, d.h. im Kleinen tritt die gleiche
Struktur wie im Großen auf, was auch in der Natur häufig vorkommt.
- Der Baum heißt auch binärer Baum und tritt
als Struktur in der Informatik häufig auf.
Beispiel: Durch Ja/Nein-Antworten (binär) soll ein Benutzer zum gewünschten Ziel
geführt werden. Dies kann man als Bewegung von der Wurzel zu den Astspitzen
ansehen.
- Kompliziertere Baumstrukturen mit mehr als zwei Verzweigungen kommen in der Informatik
noch häufiger vor. Beispiele: Dateisysteme mit Unterverzeichnissen;
Datenbanken, in denen nach bestimmten Merkmalen gesucht werden muss;
Suchmaschinen im Internet; und vieles andere mehr...
Aufgabe 2:
Der Baum soll mit unterschiedlichen Astlängen gezeichnet werden.
Dies bietet viele Möglichkeiten, verschiedene Strategien auszuprobieren,
um dem Baum ein pflanzenähnliches Aussehen zu geben.
- Die linken Äste können kürzer als die rechten Äste sein.
- Die Äste können mit verschiedenen Verkürzungsfaktoren gezeichnet
werden.
- Die Astlängen können zufällig gewählt werden.
Die Methode double Math.random() aus der Klasse Math,
die eine Zufallszahl zwischen 0.0 und 1.0 liefert,
kann dazu benutzt werden.
Aufgabe 3:
Der Baum ist jetzt nicht mehr binär, sondern hat drei Äste
mit unterschiedlichen Astlängen. Der Stamm habe die Länge laenge.
- Stamm mit der Länge laenge zeichnen.
- Um 60 Grad nach rechts drehen und Ast der Länge laenge/2 zeichnen.
- Um 50 Grad nach links drehen und Ast der Länge laenge*4/5 zeichnen.
- Um 50 Grad nach links drehen und Ast der Länge laenge/2 zeichnen.
- Um 40 Grad nach rechts drehen und um laenge zurückgehen.
Achtung: Es entsteht eine sehr schöne Graphik!
Lösung zu Aufgabe 1:
Applet zum binären Baum
Quelltext: BinBaum.java
Lösung zu Aufgabe 2:
Applet zum binären Baum mit unterschiedlichen Astlängen
Quelltext: BinBaumUngleich.java
Lösung zu Aufgabe 2:
Applet zur Aufgabe 3
Quelltext zur Aufgabe 3