A.3 Rekursive Grafiken mit der Turtle A.3.1 Binärer Baum |
|
Download: EinT.java |
Nachdem
wir beim Aufbau der Klasse Mathematik lernten, wie man rekursive Methoden
implementiert wollen wir uns dem reizvollen Thema der rekursiven Grafiken
zuwenden. Wir werden dazu wieder unsere Turtle verwenden. Zuerst wollen
wir die Turtle einen binären Baum (oder Binärbaum) zeichnen lassen. Zur Einübung zeichnen wir mit der Turtle ein T, das auf dem Kopf steht.
Die Methode zeichne() in unserer Turtlevorlage ist sehr einfach: public void zeichne() { t1.jumpTo(0,150); t1.forward(-100); t1.right(90); t1.forward(100); t1.forward(-200); } |
Aus dem auf dem Kopf stehenden T bekommen wir einen Binärbaum, wenn wir an die Enden des Balkens wieder auf dem Kopf stehende Ts, allerdings jetzt kleiner, ansetzen und dieses Vorgehen immer weiter wiederholen. Wir erhalten: | |
|
|
Die
entstandene Figur zeigt eine interessante Eigenschaft: Wählen wir aus dem
Bild geschickt einen Teilbereich heraus und zoomen ihn größer, so entsteht
eine Figur, die von der ganzen nicht zu unterscheiden ist. Wir können auch
sagen, in einer Teilfigur steckt die ganze Information für die
Gesamtfigur. Solche Figuren nennt der Mathematiker selbstähnlich. Wie aber
programmieren wir einen solchen Baum? Eine Methode zeichne() mit der
folgenden Gestalt würde uns gefallen:public void zeichne() { double l = 100; t1.jumpTo(0,150); t1.zeichneBinaerBaum(l); } |
|
API-der Turtle | In einer
Variable l
legen wir die Länge der Teilstrecken des ersten Ts fest und zeichnen den
Binärbaum, in dem wir die Methode
zeichneBinaerBaum(
double l) für
unser Turtle-Objekt t1
aufrufen. Aber halt! Wie ein Blick in die API-der Klasse
Turtle
zeigt, gibt es diese Methode in der Klasse Turtle nicht. Also müssen wir
sie selbst implementieren. Das ist aber nicht so einfach, denn die Turtle
ist in einem Paket und ihr Quelltext ist uns nicht zugänglich. Uns bleibt
nur der Weg, den wir schon einmal in
10.1
Die Klasse MeineTurtle erbt von Turtle gegangen sind: Wir schreiben
uns eine Klasse, die von der Klasse
Turtle
erbt und in die wir unsere Methoden für grafische Rekursionen unterbringen
wollen. Wir nennen diese Klasse deshalb:
RekursionsTurtle. |
import turtle.*; public class RekursionsTurtle extends Turtle{ public RekursionsTurtle(TurtleWindow tWin){ super(tWin); } public void zeichneBinaerBaum(double l){ if (l>1){ forward(-l); right(90); forward(l); left(90); zeichneBinaerBaum(l/2); right(90); forward(-2*l); left(90); zeichneBinaerBaum(l/2); right(90); forward(l); left(90); forward(l); } } } |
|
Download: RekursionsTurtle. class Binaerbaum.java |
Uns
wundert nicht, dass wir unsere Methode, wegen der Selbstähnlichkeit
rekursiv aufbauen: Wie der rekursive Aufruf zeigt, wird bei jedem Schritt tiefer in die Rekursion, die Länge der T-Strecken halbiert. Den Basisfall haben wir erreicht, wenn die Länge (sie ist eine Fließkommazahl) kleiner als 1 wird. Vergleichen wir unsere Methode mit der zeichne()-Methode in EinT: Wir sehen zunächst die gleichen Turtle-Methode, sie sind gelb unterlegt. Statt der festen Schrittlänge 100 haben wir allerdings die Schrittlänge l. An den Enden des T-Querbalkens setzen wir die kleineren Ts an in dem wir die Methode zeichneBinaerBaum(double l) mit halber Schrittlänge rekursiv aufrufen. Die rekursiven Aufrufe sind grün unterlegt. Vor dem rekursiven Aufruf muss unsere Turtle aber in die richtige Richtung für das T-zeichnen ausgerichtet und nach dem rekursiven Aufruf wieder in die richtige 'Wanderrichtung' zurückgesetzt werden. Deshalb die Aufrufe left(90) vor und right(90) nach dem rekursiven Aufruf (blau unterlegt). Schließlich muss die Turtle in ihren Ausgangspunkt zurückgeführt werden: forward(l); left(90); forward(l) (weiß unterlegt). Um sich klar zu machen, warum im Gegensatz zum Zeichnen des einfachen Ts dieses Rückführen wichtig ist, lassen man diese drei Anweisungen einfach mal weg. |
Bemerkung zum Testprogramm |
import turtle.*; import java.awt.*; /** * Turtle-Projekt: Binaerbaum.java * @version 1.0 vom 14.12.2003 * @author Michael Pohlig */ public class Binaerbaum extends TurtleFrame { RekursionsTurtle t1; public Binaerbaum(String title) { super(title); t1 = new RekursionsTurtle(tWin); } public void zeichne() { double l = 100; t1.jumpTo(0,150); t1.zeichneBinaerBaum(l); } public static void main (String[] args) { new Binaerbaum("Binärbaum"); } } |
Damit
t1
über die neue Methode
zeichneBinaerBaum(double l)
verfügt muss sie ein
RekursionsTurtle-Objekt sein.
Der neue Konstruktor muss angepasst werden: Über
super(titel)
rufen wir den alten Konstruktor von Turtle auf, so ist gewährleistet, dass
unser Binaerbaum-Objekt
auch über die Funktionalität der Klasse
TurtleFrame
verfügt. |
|
zu | A.3.2 Sierpinski-Dreieck |
zur Startseite | www.pohlig.de (C) MPohlig 2007 |