[SOLVED] CS Java Programmierung Rekursion

Programmierung Rekursion
auf der Basis von Folien v. V Gruhn
Michael Goedicke
[email protected]
paluno

Rekursion: Aufrufstack
Jedes Programm besitzt zur Laufzeit einen Aufrufstack.
Ein Stack ist eine Datenstruktur, die einem Stapel Bucher ahnelt: man kann ein Buch oben auf den Stapel legen oder von oben ein Buch herunternehmen.
Ein Buch kann aber nicht aus der Mitte des Stapels herausgezogen werden. Das unterste Buch kann ebenfalls nicht weggenommen werden.
Dieses Prinzip nennt man LIFO (Last In First Out).
Last In First Out
M. Goedicke Programmierung WiSe 2019/2020 2
paluno

Rekursion: Aufrufstack
Wenn eine Methode aufgerufen wird, dann wird die entsprechende Methodeninstanz auf den Aufrufstack gelegt.
Eine Methodeninstanz besteht aus den dynamischen Daten der Methode: aus den Parametern, den lokalen Variablen und der Rucksprungadresse.
Die Rucksprungadresse gibt an, an welcher Stelle das Programm nach Abarbeitung der Methode fortgesetzt wird.
Jede Methodeninstanz definiert einen eigenen Namensraum fur die Parameter und lokalen Variablen der zugrunde liegenden Methode.
Wahrend der Ausfuhrung eines JAVA-Programms liegt immer eine Instanz der main(String[])-Methode auf dem Aufrufstack:
methode2()
methode1()
main()
methode1()
main()
methode1()
main()
main()
main()
Definition: Eine Methode, die sich direkt oder indirekt selbst aufruft, nennt man rekursiv.
M. Goedicke Programmierung WiSe 2019/2020 3
paluno

Rekursion: Fakultat
Fur eine naturliche Zahl n > 1 sei f(n) = n f(n-1). Zudem sei f(1) = 1. Dann heit f Fakultatsfunktion und man schreibt f(n) = n!.
Diese Definition lasst sich leicht in eine JAVA-Methode umsetzen:
public int fakultaet(int n) { if (n == 1) {
return 1;
} else {
return n * fakultaet(n 1); }
}
Wir uberlegen uns nun, wie sich der Aufrufstack beim Aufruf von fakultaet(4) verhalt, wobei wir auf die Widergabe der main()-
Methode verzichten.
M. Goedicke Programmierung WiSe 2019/2020 4
paluno

Rekursion: Fakultat
Zuerst wird der Namensraum fur den Methodenaufruf mit dem Parameter n = 4 aufgebaut und der Ausdruck 4 * fakultaet(3)
ausgewertet.
fakultaet(4)
return 4 * fakultaet(3)
fakultaet(4)
M. Goedicke Programmierung WiSe 2019/2020 5
paluno

Rekursion: Fakultat
Anschlieend wird der Namensraum fur den Methodenaufruf mit dem Parameter n = 3 aufgebaut und der Ausdruck 3 * fakultaet(2)
ausgewertet.
fakultaet(3)
return 3 * fakultaet(2)
fakultaet(4)
return 4 * fakultaet(3)
fakultaet(3)
fakultaet(4)
fakultaet(4)
M. Goedicke Programmierung WiSe 2019/2020 6
paluno

Rekursion: Fakultat
Anschlieend wird der Namensraum fur den Methodenaufruf mit dem Parameter n = 2 aufgebaut und der Ausdruck 2 * fakultaet(1)
ausgewertet.
fakultaet(2)
return 2 * fakultaet(1)
fakultaet(3)
return 3 * fakultaet(2)
fakultaet(4)
return 4 * fakultaet(3)
fakultaet(2)
fakultaet(3)
fakultaet(3)
fakultaet(4)
fakultaet(4)
fakultaet(4)
M. Goedicke Programmierung WiSe 2019/2020 7
paluno

Rekursion: Fakultat
Anschlieend wird der Namensraum fur den Methodenaufruf mit dem Parameter n = 1 aufgebaut. Da an dieser Stelle n = 1 gilt, wird 1
zuruckgegeben.
fakultaet(1)
return 1
fakultaet(2)
return 2 * fakultaet(1)
fakultaet(3)
return 3 * fakultaet(2)
fakultaet(4)
return 4 * fakultaet(3)
fakultaet(2)
fakultaet(1)
fakultaet(2)
fakultaet(3)
fakultaet(3)
fakultaet(3)
fakultaet(4)
fakultaet(4)
fakultaet(4)
fakultaet(4)
M. Goedicke Programmierung WiSe 2019/2020 8
paluno

Rekursion: Fakultat
Anschlieend springt das Programm zu der Auswertung des Ausdruck 2 * fakultaet(1) zuruck, wobei fakultaet(1) durch den Wert 1 ersetzt und daher 2 zuruckgegeben wird.
fakultaet(2)
return 2 * 1
fakultaet(3)
return 3 * fakultaet(2)
fakultaet(4)
return 4 * fakultaet(3)
fakultaet(1)
fakultaet(2)
fakultaet(2)
fakultaet(2)
fakultaet(3)
fakultaet(3)
fakultaet(3)
fakultaet(3)
fakultaet(4)
fakultaet(4)
fakultaet(4)
fakultaet(4)
fakultaet(4)
M. Goedicke Programmierung WiSe 2019/2020 9
paluno

Rekursion: Fakultat
Anschlieend springt das Programm zu der Auswertung des Ausdruck 3 * fakultaet(2) zuruck, wobei fakultaet(2) durch den Wert 2 ersetzt und daher 6 zuruckgegeben wird.
fakultaet(3)
return 3 * 2
fakultaet(4)
return 4 * fakultaet(3)
fakultaet(1)
fakultaet(2)
fakultaet(2)
fakultaet(2)
fakultaet(3)
fakultaet(3)
fakultaet(3)
fakultaet(3)
fakultaet(3)
fakultaet(4)
fakultaet(4)
fakultaet(4)
fakultaet(4)
fakultaet(4)
fakultaet(4)
M. Goedicke Programmierung WiSe 2019/2020 10
paluno

Rekursion: Fakultat
Abschlieend springt das Programm zu der Auswertung des Ausdruck 4 * fakultaet(3) zuruck, wobei fakultaet(3) durch den Wert 6 ersetzt und daher 24 zuruckgegeben wird.
fakultaet(4)
return 4 * 6
fakultaet(1)
fakultaet(2)
fakultaet(2)
fakultaet(2)
fakultaet(3)
fakultaet(3)
fakultaet(3)
fakultaet(3)
fakultaet(3)
fakultaet(4)
fakultaet(4)
fakultaet(4)
fakultaet(4)
fakultaet(4)
fakultaet(4)
fakultaet(4)
M. Goedicke Programmierung WiSe 2019/2020 11
paluno

Rekursion: StackOverflowError
Das Fakultatsbeispiel zeigt, dass der Aufrufstack bei der Abarbeitung rekursiver Methoden stark anwachsen kann.
Daher sind rekursive Losungen eines Problems in der Regel weniger performant als iterative Losungen; rekursive Losungen sind aber oft einfacher zu verstehen.
Da die Groe des Aufrufstacks durch den zur Verfugung stehenden Speicherplatz beschrankt ist, kann es bei der Abarbeitung rekursiver Methoden zu einem StackOverflowError kommen:
public int doofeFakultaet(int n) {
return n * doofeFakultaet(n 1);
}
Exception in thread main java.lang.StackOverflowError at Rekursion.doofeFakultaet(Rekursion.java:4)
at Rekursion.doofeFakultaet(Rekursion.java:4)
at Rekursion.doofeFakultaet(Rekursion.java:4)
.. .
M. Goedicke Programmierung WiSe 2019/2020 12
paluno

Rekursion: Terminierungsbedingung
Der Aufruf der Methode doofeFakultaet() fuhrt zu einem StackOverflowError, da keine Terminierungsbedingung angegeben wurde.
Wenn die Terminierungsbedingung einer rekursiven Methode erfullt ist, dann muss der Ruckgabewert der Methode ohne Rekursion berechnet werden.
Jeder Aufruf einer rekursiven Methode muss im Verlauf seiner Auswertung die Terminierungsbedingung erreichen.
Terminierungsbedingung
public int fakultaet(int n) { if (n == 1) {
return 1;
} else {
return n * fakultaet(n 1); }
}
M. Goedicke Programmierung WiSe 2019/2020 13
paluno

Rekursion: Rekursive Datenstrukturen
Man kann neben Methoden auch Datenstrukturen rekursiv definieren.
Eine lineare Liste kann man durch die folgenden Eigenschaften definieren:
Wenn a ein Element ist, dann ist[a] eine Liste.
Wenn a ein Element und L eine Liste ist, dann ist auch[a|L] eine Liste.
Beispiel: [2] und [1|[2]] sind Listen. Statt [1|[2]] kann man auch [1,2] schreiben.
Die rekursive Definition einer Liste kann man leicht in eine Klasse umsetzen:
public class RekursiveListe { public T element;
public RekursiveListe liste; }
RekursiveListe
T
+element:T +liste:RekursiveListe
M. Goedicke Programmierung WiSe 2019/2020 14
paluno

Zur Notation
Wir wollen im Folgenden diese Notation verwenden, wenn wir uns nicht festlegen, was fur ein Typ das Element (hier element) hat,
Dokument, Person, Buch, Auto
Wie das im Detail funktioniert, wird spater beschrieben. Java (ab Version 5) unterstutzt diesen Mechanismus
public class RekursiveListe { public T element;
public RekursiveListe liste; }
T
RekursiveListe
+element:T +liste:RekursiveListe
M. Goedicke Programmierung WiSe 2019/2020
15
paluno

Rekursion: Rekursive Datenstrukturen
Methoden, die auf rekursiven Datenstrukturen operieren, sind in der Regel ebenfalls rekursiv.
Fur ein Element a und eine Liste L soll mem(a,L) den Wert true haben, wenn a in L enthalten ist. Andernfalls soll mem(a,L) den Wert false haben. Es gilt also:
mem(a,L)=truefurL=[a]oderL=[a|L],
mem(a,L)=mem(a,L)furL=[x|L]unda=xsowie mem(a,[x])=falsefura=x.
public boolean isMember(T x) {
if (x.equals(element)) {
return true;
} else if (liste != null) {
return liste.isMember(x);
} else {
return false; }
}
T
RekursiveListe
+element:T +liste:RekursiveListe
+isMember(T):boolean
M. Goedicke Programmierung WiSe 2019/2020 16
paluno

Rekursion: Rekursive Datenstrukturen
Ein Binarbaum besteht aus einem Element und kann einen linken oder einen rechten Teilbaum besitzen. Wenn also leftTree und rightTree Binarbaume sind, dann gilt:
(a,null,null) ist ein Binarbaum ohne Teilbaume.
(a,leftTree,null) ist ein Binarbaum mit einem linken Teilbaum.
(a,null,rightTree) ist ein Binarbaum mit einem rechten Teilbaum.
(a,leftTree,rightTree) ist ein Binarbaum mit einem linken und einem rechten Teilbaum.
Beispiel: (a,(b,(c,null,null),(d,null,null)),(e,null,(f,null,
null))) ist ein Binarbaum mit sechs Elementen.
a
b
e
c
d
f
M. Goedicke Programmierung WiSe 2019/2020 17
paluno

Rekursion: Rekursive Datenstrukturen
Die rekursive Definition eines Binarbaums kann man unmittelbar in ein Klasse umsetzen:
Wir nehmen an, dass jedes Element des Binarbaums aus einem Schlussel key und einem Wert value besteht.
public class BinaryTree {
private BinaryTree leftTree; private BinaryTree rightTree;
public BinaryTree(S key, T value) {
this.key = key;
this.value = value;
}
// Methoden
}
private S key; private T value;
S,T
BinaryTree
-key:S
-value:T -leftTree:BinaryTree -rightTree:BinaryTree
+BinaryTree(S,T)
M. Goedicke Programmierung WiSe 2019/2020 18
paluno

Rekursion: Rekursive Datenstrukturen
Man kann den Wert eines Elements anhand seines Schlussels suchen:
public T findValue(S key) { T value = null;
if (key.equals(this.key)) value = this.value;
if (value == null && leftTree != null) value = leftTree.findValue(key); if (value == null && rightTree != null) value = rightTree.findValue(key); return value;
}
4
26
T1 = (4,(2,(1,null,null),(3,null,null)),(6,(5,null,nul l),(7,null,null)))
1357
T1.findValue(3)
M. Goedicke Programmierung WiSe 2019/2020 19
paluno

Rekursion: Rekursive Datenstrukturen
Man kann den Wert eines Elements anhand seines Schlussels suchen:
public T findValue(S key) { T value = null;
if (key.equals(this.key)) value = this.value;
if (value == null && leftTree != null) value = leftTree.findValue(key); if (value == null && rightTree != null) value = rightTree.findValue(key); return value;
}
4 == 3 ? 4 T1 = (4,(2,(1,null, null),(3, null, null)),(6,(5, null, null),(7, null, null)))
26
1357
T1.findValue(3)
M. Goedicke Programmierung WiSe 2019/2020 20
paluno

Rekursion: Rekursive Datenstrukturen
Man kann den Wert eines Elements anhand seines Schlussels suchen:
public T findValue(S key) { T value = null;
if (key.equals(this.key)) value = this.value;
if (value == null && leftTree != null) value = leftTree.find(key); if (value == null && rightTree != null) value = rightTree.find(key); return value;
}
2
13
T1 = (4,(2,(1, null, null),(3, null, null)),(6,(5, null, null),(7, null, null))) T2 = (2,(1, null, null),(3, null, null))
4
6
5
7
T2.findValue(3)
T1.findValue(3)
T1.findValue(3)
M. Goedicke Programmierung WiSe 2019/2020 21
paluno

Rekursion: Rekursive Datenstrukturen
Man kann den Wert eines Elements anhand seines Schlussels suchen:
public T findValue(S key) { T value = null;
if (key.equals(this.key)) value = this.value;
if (value == null && leftTree != null) value = leftTree.findValue(key); if (value == null && rightTree != null) value = rightTree.findValue (key); return value;
}
2
13
2 == 3 ?
T1 = (4,(2,(1, null, null),(3, null, null)),(6,(5, null, null),(7, null, null))) T2 = (2,(1, null, null),(3, null, null))
4
6
5
7
T2.findValue(3)
T1.findValue(3)
T1.findValue(3)
M. Goedicke Programmierung WiSe 2019/2020 22
paluno

Rekursion: Rekursive Datenstrukturen
Man kann den Wert eines Elements anhand seines Schlussels suchen:
public T findValue(S key) { T value = null;
if (key.equals(this.key)) value = this.value;
if (value == null && leftTree != null) value = leftTree.find(key); if (value == null && rightTree != null) value = rightTree.find(key); return value;
}
T1 = (4,(2,(1, null, null),(3, null, null)),(6,(5, null, null),(7, null, null))) T2 = (2,(1, null, null),(3, null, null)) T3 = (1, null, null)
4
2
6
1
3
5
7
T3.findValue(3)
T2.findValue(3)
T1.findValue(3)
T2.findValue(3)
T1.findValue(3)
T1.findValue(3)
M. Goedicke Programmierung WiSe 2019/2020 23
paluno

Rekursion: Rekursive Datenstrukturen
Man kann den Wert eines Elements anhand seines Schlussels suchen:
public T findValue(S key) { T value = null;
if (key.equals(this.key)) value = this.value;
if (value == null && leftTree != null) value = leftTree.find(key); if (value == null && rightTree != null) value = rightTree.find(key); return value;
}
1 == 3 ?
1
T1 = (4,(2,(1, null, null),(3, null, null)),(6,(5, null, null),(7, null, null))) T2 = (2,(1, null, null),(3, null, null)) T3 = (1, null, null)
4
2
6
3
5
7
T3.findValue(3)
T2.findValue(3)
T1.findValue(3)
T2.findValue(3)
T1.findValue(3)
T1.findValue(3)
M. Goedicke Programmierung WiSe 2019/2020 24
paluno

Rekursion: Rekursive Datenstrukturen
Man kann den Wert eines Elements anhand seines Schlussels suchen:
public T findValue(S key) { T value = null;
if (key.equals(this.key)) value = this.value;
if (value == null && leftTree != null) value = leftTree.find(key); if (value == null && rightTree != null) value = rightTree.find(key); return value;
}
2
13
T1 = (4,(2,(1,null, null),(3, null, null)),(6,(5, null, null),(7, null, null)))
T2 = (2,(1, null, null),(3, null, null))
T3 = (1, null, null)
4
6
5
7
T3.findValue(3)
T2.findValue(3)
T1.findValue(3)
T2.findValue(3)
T1.findValue(3)
T2.findValue(3)
T1.findValue(3)
T1.findValue(3)
M. Goedicke Programmierung WiSe 2019/2020 25
paluno

Rekursion: Rekursive Datenstrukturen
Man kann den Wert eines Elements anhand seines Schlussels suchen:
public T findValue(S key) { T value = null;
if (key.equals(this.key)) value = this.value;
if (value == null && leftTree != null) value = leftTree.find(key); if (value == null && rightTree != null) value = rightTree.find(key); return value;
}
T1 = (4,(2,(1, null, null),(3, null, null)),(6,(5, null, null),(7, null, null))) T2 = (2,(1, null, null),(3, null, null)) T3 = (1, null, null)
T4 = (3, null, null)
4
2
6
1
3
5
7
T3.findValue(3)
T2.findValue(3)
T1.findValue(3)
T4.findValue(3)
T2.findValue(3)
T1.findValue(3)
T2.findValue(3)
T1.findValue(3)
T2.findValue(3)
T1.findValue(3)
T1.findValue(3)
M. Goedicke Programmierung WiSe 2019/2020 26
paluno

Rekursion: Rekursive Datenstrukturen
Man kann den Wert eines Elements anhand seines Schlussels suchen:
public T findValue(S key) { T value = null;
if (key.equals(this.key)) value = this.value;
if (value == null && leftTree != null) value = leftTree.find(key); if (value == null && rightTree != null) value = rightTree.find(key); return value;
}
3==3?
T1 = (4,(2,(1, null, null),(3, null, null)),(6,(5, null, null),(7, null, null))) T2 = (2,(1, null, null),(3, null, null)) T3 = (1, null, null)
T4 = (3, null, null)
4
2
6
1
3
5
7
T3.findValue(3)
T2.findValue(3)
T1.findValue(3)
T4.findValue(3)
T2.findValue(3)
T1.findValue(3)
T2.findValue(3)
T1.findValue(3)
T2.findValue(3)
T1.findValue(3)
T1.findValue(3)
M. Goedicke Programmierung WiSe 2019/2020 27
paluno

Rekursion: Rekursive Datenstrukturen
Wenn ein neues Element in einen Binarbaum eingefugt werden soll, dann muss entschieden werden, ob man das Element in den linken oder in den rechten Teilbaum einfugt.
Im folgenden nehmen wir daher an, dass eine Ordnung auf der Menge der Schlussel der potentiellen Elementen definiert ist:
public class BinaryTree , T> { private S key;
private T value;
// weitere Attribute, Konstruktoren und Methoden
}
erlaubt: Die Klasse String implementiert das Comparable-Interface
BinaryTree t1 =
new BinaryTree<>(Skywalker, Luke);
Kompilierfehler: Die Klasse Object implementiert das Comparable-Interface nicht
BinaryTree t2 =
new BinaryTree<>((Object) Vader, Darth);
M. Goedicke Programmierung WiSe 2019/2020 28
paluno

Zur Notation
Die Angabe
BinaryTree , T> bedeutet
S extends Comparable
dass die Klasse S die Spezifikation Comparable erfullt.
Das bedeutet hier, dass auf der Klasse S die Operation compareTo implementiert ist, die eine Ordnung (eine Relation < ) auf der Klasse definiertpublic class BinaryTree , T> { private S key;
private T value;
// weitere Attribute, Konstruktoren und Methoden
}
M. Goedicke Programmierung WiSe 2019/2020 29
paluno

Rekursion: Rekursive Datenstrukturen
Wir wenden nun folgendes Verfahren an, um ein neues Element b in einen Binarbaum Tree = (a,,) einzufugen:
Fall 1: Sei b.key a.key.
Wenn Tree = (a, null,) gilt, dann ersetzen wir null durch (b,
null, null).
Wenn Tree = (a,leftTree,) gilt, dann fugen wir b in den
Binarbaum leftTree ein.
Fall 2: Sei b.key > a.key.
Wenn Tree = (a,, null) gilt, dann ersetzen wir null durch (b, null, null).
Wenn Tree = (a,,rightTree) gilt, dann fugen wir b in den Binarbaum rightTree ein.
4
6
2
7
5
3
1
4
M. Goedicke Programmierung WiSe 2019/2020 30
paluno

Rekursion: Rekursive Datenstrukturen
Wir wenden nun folgendes Verfahren an, um ein neues Element b in einen Binarbaum Tree = (a,,) einzufugen:
Fall 1: Sei b.key a.key.
Wenn Tree = (a,null,) gilt, dann ersetzen wir null durch
(b,null,null).
Wenn Tree = (a,leftTree,) gilt, dann fugen wir b in den
Binarbaum leftTree ein.
Fall 2: Sei b.key > a.key.
Wenn Tree = (a,,null) gilt, dann ersetzen wir null durch (b,null,null).
Wenn Tree = (a,,rightTree) gilt, dann fugen wir b in den Binarbaum rightTree ein.
6
2
7
5
3
1
4
6>4
6
M. Goedicke Programmierung WiSe 2019/2020 31
paluno

Rekursion: Rekursive Datenstrukturen
Wir wenden nun folgendes Verfahren an, um ein neues Element b in einen Binarbaum Tree = (a,,) einzufugen:
Fall 1: Sei b.key a.key.
Wenn Tree = (a,null,) gilt, dann ersetzen wir null durch
(b,null,null).
Wenn Tree = (a,leftTree,) gilt, dann fugen wir b in den Binarbaum
leftTree ein.
Fall 2: Sei b.key > a.key.
Wenn Tree = (a,,null) gilt, dann ersetzen wir null durch (b,null,null).
Wenn Tree = (a,,rightTree) gilt, dann fugen wir b in den Binarbaum rightTree ein.
2
7
5
3
1
2<4426 M. Goedicke Programmierung WiSe 2019/2020 32 paluno Rekursion: Rekursive Datenstrukturen Wir wenden nun folgendes Verfahren an, um ein neues Element b in einen Binarbaum Tree = (a,…,…) einzufugen: Fall 1: Sei b.key a.key. Wenn Tree = (a,null,…) gilt, dann ersetzen wir null durch(b,null,null). Wenn Tree = (a,leftTree,…) gilt, dann fugen wir b in denBinarbaum leftTree ein. Fall 2: Sei b.key > a.key.
Wenn Tree = (a,,null) gilt, dann ersetzen wir null durch (b,null,null).
Wenn Tree = (a,,rightTree) gilt, dann fugen wir b in den Binarbaum rightTree ein.
7
5
3
1
7>47>6
4
2
6
7
M. Goedicke Programmierung WiSe 2019/2020 33
paluno

Rekursion: Rekursive Datenstrukturen
Wir wenden nun folgendes Verfahren an, um ein neues Element b in einen Binarbaum Tree = (a,,) einzufugen:
Fall 1: Sei b.key a.key.
Wenn Tree = (a,null,) gilt, dann ersetzen wir null durch
(b,null,null).
Wenn Tree = (a,leftTree,) gilt, dann fugen wir b in den
Binarbaum leftTree ein.
Fall 2: Sei b.key > a.key.
Wenn Tree = (a,,null) gilt, dann ersetzen wir null durch (b,null,null).
Wenn Tree = (a,,rightTree) gilt, dann fugen wir b in den Binarbaum rightTree ein.
5
3
1
5>45<642657 M. Goedicke Programmierung WiSe 2019/2020 34 paluno Rekursion: Rekursive Datenstrukturen Wir wenden nun folgendes Verfahren an, um ein neues Element b in einen Binarbaum Tree = (a,…,…) einzufugen: Fall 1: Sei b.key a.key. Wenn Tree = (a,null,…) gilt, dann ersetzen wir null durch(b,null,null). Wenn Tree = (a,leftTree,…) gilt, dann fugen wir b in denBinarbaum leftTree ein. Fall 2: Sei b.key > a.key.
Wenn Tree = (a,,null) gilt, dann ersetzen wir null durch (b,null,null).
Wenn Tree = (a,,rightTree) gilt, dann fugen wir b in den Binarbaum rightTree ein.
3
1
3<43>2
4
2
6
3
5
7
M. Goedicke Programmierung WiSe 2019/2020 35
paluno

Rekursion: Rekursive Datenstrukturen
Wir wenden nun folgendes Verfahren an, um ein neues Element b in einen Binarbaum Tree = (a,,) einzufugen:
Fall 1: Sei b.key a.key.
Wenn Tree = (a,null,) gilt, dann ersetzen wir null durch
(b,null,null).
Wenn Tree = (a,leftTree,) gilt, dann fugen wir b in den Binarbaum
leftTree ein.
Fall 2: Sei b.key > a.key.
Wenn Tree = (a,,null) gilt, dann ersetzen wir null durch (b,null,null).
Wenn Tree = (a,,rightTree) gilt, dann fugen wir b in den Binarbaum rightTree ein.
1
1<41<2 M. Goedicke Programmierung WiSe 2019/2020 364261357 paluno Rekursion: Rekursive Datenstrukturen Dieses Verfahren kann man leicht in die Methode insert(S,T) umsetzen:public void insert(S key, T value) { if (key.compareTo(this.key) <= 0) {if (leftTree != null) leftTree.insert(key, value);else leftTree = new BinaryTree (key, value); } else {
if (rightTree != null) rightTree.insert(key, value);
else rightTree = new BinaryTree (key, value); }
}
Die Struktur des Binarbaums hangt von der Reihenfolge ab, in der die Elemente eingefugt wurden:
1
2
3
1
M. Goedicke Programmierung WiSe 2019/2020 37
paluno

Rekursion: Rekursive Datenstrukturen
Dieses Verfahren kann man leicht in die Methode insert(S,T) umsetzen:
public void insert(S key, T value) { if (key.compareTo(this.key) <= 0) {if (leftTree != null) leftTree.insert(key, value);else leftTree = new BinaryTree (key, value); } else {
if (rightTree != null) rightTree.insert(key, value);
else rightTree = new BinaryTree (key, value); }
}
Die Struktur des Binarbaums hangt von der Reihenfolge ab, in der die Elemente eingefugt wurden:
2
3
2>1
M. Goedicke Programmierung WiSe 2019/2020 38
1
2
paluno

Rekursion: Rekursive Datenstrukturen
Dieses Verfahren kann man leicht in die Methode insert(S,T) umsetzen:
public void insert(S key, T value) { if (key.compareTo(this.key) <= 0) {if (leftTree != null) leftTree.insert(key, value);else leftTree = new BinaryTree (key, value); } else {
if (rightTree != null) rightTree.insert(key, value);
else rightTree = new BinaryTree (key, value); }
}
Die Struktur des Binarbaums hangt von der Reihenfolge ab, in der die Elemente eingefugt wurden:
3
3>13>2
M. Goedicke Programmierung WiSe 2019/2020 39
1
2
3
paluno

Rekursion: Rekursive Datenstrukturen
Dieses Verfahren kann man leicht in die Methode insert(S,T) umsetzen:
public void insert(S key, T value) { if (key.compareTo(this.key) <= 0) {if (leftTree != null) leftTree.insert(key, value);else leftTree = new BinaryTree (key, value); } else {
if (rightTree != null) rightTree.insert(key, value);
else rightTree = new BinaryTree (key, value); }
}
Die Struktur des Binarbaums hangt von der Reihenfolge ab, in der die Elemente eingefugt wurden:
2
1
3
2
M. Goedicke Programmierung WiSe 2019/2020 40
paluno

Rekursion: Rekursive Datenstrukturen
Dieses Verfahren kann man leicht in die Methode insert(S,T) umsetzen:
public void insert(S key, T value) { if (key.compareTo(this.key) <= 0) {if (leftTree != null) leftTree.insert(key, value);else leftTree = new BinaryTree (key, value); } else {
if (rightTree != null) rightTree.insert(key, value);
else rightTree = new BinaryTree (key, value); }
}
Die Struktur des Binarbaums hangt von der Reihenfolge ab, in der die Elemente eingefugt wurden:
1
3
1<2 M. Goedicke Programmierung WiSe 2019/2020 412 1 paluno Rekursion: Rekursive Datenstrukturen Dieses Verfahren kann man leicht in die Methode insert(S,T) umsetzen:public void insert(S key, T value) { if (key.compareTo(this.key) <= 0) {if (leftTree != null) leftTree.insert(key, value);else leftTree = new BinaryTree (key, value); } else {
if (rightTree != null) rightTree.insert(key, value);
else rightTree = new BinaryTree (key, value); }
}
Die Struktur des Binarbaums hangt von der Reihenfolge ab, in der die Elemente eingefugt wurden:
3
3>2
M. Goedicke Programmierung WiSe 2019/2020 42
2
1
3
paluno

Rekursion: Rekursive Datenstrukturen
Wenn man einen Binarbaum mit Hilfe der insert(S,T)-Methode aufbaut, dann erhalt man einen Suchbaum:
(a,null,null) ist ein Suchbaum.
(a,leftTree,null) ist ein Suchbaum, wenn fur alle Elemente b von
leftTree stets b.key a.key gilt.
(a,null,rightTree) ist ein Suchbaum, wenn fur alle Elemente c von
rightTree stets a.key < c.key gilt. (a,leftTree,rightTree) ist ein Binarbaum, wenn fur alle Elemente b von leftTree stets b.key a.key gilt und wenn fur alle Elemente c von rightTree stets a.key < c.key gilt. In einem Suchbaum kann effizienter gesucht werden:public T lookUp(S key) {int temp = key.compareTo(this.key);if (temp == 0) return value;if (temp < 0) return leftTree == null ? null : leftTree.lookUp(key); return rightTree == null ? null : rightTree.lookUp(key);}M. Goedicke Programmierung WiSe 2019/2020 43 paluno Rekursion: Rekursive Datenstrukturen Die Anzahl der von der lookUp(S)-Methode durchgefuhrten Schlusselvergleiche hangt von der Hohe des Baums ab: height(a,null,null) = 0. height(a,leftTree,null) = height(leftTree) + 1. height(a,null,rightTree) = height(rightTree) + 1. height(a,leftTree,rightTree) = max(hleft + 1,hright + 1) mit hleft = height(leftTree) und hright = height(rightTree). Die Definition lasst sich unmittelbar in die Methode getHeight() umsetzen:public int height() {if (leftTree != null && rightTree != null)return Math.max(leftTree.height(), rightTree.height()) + 1; else if (leftTree != null) return leftTree.height() + 1;else if (rightTree != null) return rightTree.height() + 1; else return 0;}M. Goedicke Programmierung WiSe 2019/2020 44 paluno Rekursion: Rekursive DatenstrukturenHohe des Baums: 0 Hohe des Baums: 1 Hohe des Baums: 1444 2Hohe des Baums: 2 Hohe des Baums: 2 Hohe des Baums: 22644626264 113 Ein Binarbaum mit der Hohe 2 enthalt mindestens 3 = 2 + 1 und hochstens 7 = 23 – 1 Elemente. Ein Binarbaum mit der Hohe h enthalt mindestens h + 1 und hochstens 2h+1 – 1 Elemente. Fur die Hohe h eines Binarbaums mit m Elementen gilt also stets die Ungleichung log2(m) < h + 1 m.2 M. Goedicke Programmierung WiSe 2019/2020 45 paluno Rekursion: Rekursive Datenstrukturen Mit Hilfe eines Suchbaums kann man eine Menge von Elementen nach ihren Schlusseln sortieren. Um die Elemente sortiert auszugeben, muss man den Suchbaum in der richtigen Reihenfolge durchlaufen. Einen Binarbaum kann man mit einer Tiefensuche oder mit einer Breitensuche durchlaufen. Man unterscheidet verschiedene Varianten der Tiefensuche:PreOrder: Bei der Bearbeitung von (a,leftTree,rightTree) bearbeitet man zuerst a. Anschlieend bearbeitet man leftTree rekursiv. Danach bearbeitet man rightTree rekursiv.InOrder: Bei der Bearbeitung von (a,leftTree,rightTree) bearbeitet man zuerst leftTree rekursiv. Anschlieend bearbeitet man a. Danach bearbeitet man rightTree rekursiv.PostOrder: Bei der Bearbeitung von (a,leftTree,rightTree) bearbeitet man zuerst leftTree rekursiv. Anschlieend bearbeitet man rightTree rekursiv. Danach bearbeitet man a.M. Goedicke Programmierung WiSe 2019/2020 46 paluno Rekursion: Rekursive Datenstrukturenpublic static void main(String[] args) { BinaryTree tree; tree = new BinaryTree<>(4, vier); tree.insert(6, sechs); tree.insert(2, zwei); tree.insert(3, drei); tree.insert(7, sieben); tree.insert(5, funf); tree.insert(1, eins);
// Durchlauf mit Tiefensuche
}
Elemente des Binarbaums
key: 4
value: vier
key: 6
value: sechs
key: 2
value: zwei
key: 3
value: drei
key: 7 value: sieben
key: 5
value: funf
key: 1 value: eins
4
2
6
1
3
5
7
M. Goedicke Programmierung WiSe 2019/2020 47
paluno

Rekursion: Rekursive Datenstrukturen
public void dfsPreOrder() {
dfsPreOrder(0);
}
private void dfsPreOrder(int n) { System.out.println(Ebene + n + : + value);
if (leftTree != null) leftTree.dfsPreOrder(n + 1); if (rightTree != null) rightTree.dfsPreOrder(n + 1);
}
Ausgabe
4
2
6
1
3
5
7
M. Goedicke Programmierung WiSe 2019/2020 48
paluno

Rekursion: Rekursive Datenstrukturen
public void dfsPreOrder() {
dfsPreOrder(0);
}
private void dfsPreOrder(int n) { System.out.println(Ebene + n + : + value);
if (leftTree != null) leftTree.dfsPreOrder(n + 1); if (rightTree != null) rightTree.dfsPreOrder(n + 1);
}
Ausgabe
4
2
6
1
3
5
7
M. Goedicke Programmierung WiSe 2019/2020 49
paluno

Rekursion: Rekursive Datenstrukturen
public void dfsPreOrder() {
dfsPreOrder(0);
}
private void dfsPreOrder(int n) { System.out.println(Ebene + n + : + value);
if (leftTree != null) leftTree.dfsPreOrder(n + 1); if (rightTree != null) rightTree.dfsPreOrder(n + 1);
}
Ausgabe
Ebene 0: vier
4
2
6
1
3
5
7
M. Goedicke Programmierung WiSe 2019/2020 50
paluno

Rekursion: Rekursive Datenstrukturen
public void dfsPreOrder() {
dfsPreOrder(0);
}
private void dfsPreOrder(int n) { System.out.println(Ebene + n + : + value);
if (leftTree != null) leftTree.dfsPreOrder(n + 1); if (rightTree != null) rightTree.dfsPreOrder(n + 1);
}
Ausgabe
Ebene 0: vier
4
2
6
1
3
5
7
M. Goedicke Programmierung WiSe 2019/2020 51
paluno

Rekursion: Rekursive Datenstrukturen
public void dfsPreOrder() {
dfsPreOrder(0);
}
private void dfsPreOrder(int n) { System.out.println(Ebene + n + : + value);
if (leftTree != null) leftTree.dfsPreOrder(n + 1); if (rightTree != null) rightTree.dfsPreOrder(n + 1);
}
Ausgabe
Ebene 0: vier
Ebene 1: zwei
4
2
6
1
3
5
7
M. Goedicke Programmierung WiSe 2019/2020 52
paluno

Rekursion: Rekursive Datenstrukturen
public void dfsPreOrder() {
dfsPreOrder(0);
}
private void dfsPreOrder(int n) { System.out.println(Ebene + n + : + value);
if (leftTree != null) leftTree.dfsPreOrder(n + 1); if (rightTree != null) rightTree.dfsPreOrder(n + 1);
}
Ausgabe
Ebene 0: vier
Ebene 1: zwei
4 2
1
6
3
5
7
M. Goedicke Programmierung WiSe 2019/2020 53
paluno

Rekursion: Rekursive Datenstrukturen
public void dfsPreOrder() {
dfsPreOrder(0);
}
private void dfsPreOrder(int n) { System.out.println(Ebene + n + : + value);
if (leftTree != null) leftTree.dfsPreOrder(n + 1); if (rightTree != null) rightTree.dfsPreOrder(n + 1);
}
Ausgabe
Ebene 0: vier
Ebene 1: zwei
Ebene 2: eins
4 2
1
6
3
5
7
M. Goedicke Programmierung WiSe 2019/2020 54
paluno

Rekursion: Rekursive Datenstrukturen
public void dfsPreOrder() {
dfsPreOrder(0);
}
private void dfsPreOrder(int n) { System.out.println(Ebene + n + : + value);
if (leftTree != null) leftTree.dfsPreOrder(n + 1); if (rightTree != null) rightTree.dfsPreOrder(n + 1);
}
Ausgabe
Ebene 0: vier
Ebene 1: zwei
Ebene 2: eins
4
2
1
6
3
5
7
M. Goedicke Programmierung WiSe 2019/2020 55
paluno

Rekursion: Rekursive Datenstrukturen
public void dfsPreOrder() {
dfsPreOrder(0);
}
private void dfsPreOrder(int n) { System.out.println(Ebene + n + : + value);
if (leftTree != null) leftTree.dfsPreOrder(n + 1); if (rightTree != null) rightTree.dfsPreOrder(n + 1);
}
Ausgabe
Ebene 0: vier
Ebene 1: zwei
Ebene 2: eins
4 2
13
6
5
7
M. Goedicke Programmierung WiSe 2019/2020 56
paluno

Rekursion: Rekursive Datenstrukturen
public void dfsPreOrder() {
dfsPreOrder(0);
}
private void dfsPreOrder(int n) { System.out.println(Ebene + n + : + value);
if (leftTree != null) leftTree.dfsPreOrder(n + 1); if (rightTree != null) rightTree.dfsPreOrder(n + 1);
}
Ausgabe
Ebene 0: vier Ebene 1: zwei Ebene 2: eins Ebene 2: drei
4 2
13
6
5
7
M. Goedicke Programmierung WiSe 2019/2020 57
paluno

Rekursion: Rekursive Datenstrukturen
public void dfsPreOrder() {
dfsPreOrder(0);
}
private void dfsPreOrder(int n) { System.out.println(Ebene + n + : + value);
if (leftTree != null) leftTree.dfsPreOrder(n + 1); if (rightTree != null) rightTree.dfsPreOrder(n + 1);
}
Ausgabe
Ebene 0: vier Ebene 1: zwei Ebene 2: eins Ebene 2: drei
4
2
13
6
5
7
M. Goedicke Programmierung WiSe 2019/2020 58
paluno

Rekursion: Rekursive Datenstrukturen
public void dfsPreOrder() {
dfsPreOrder(0);
}
private void dfsPreOrder(int n) { System.out.println(Ebene + n + : + value);
if (leftTree != null) leftTree.dfsPreOrder(n + 1); if (rightTree != null) rightTree.dfsPreOrder(n + 1);
}
Ausgabe
Ebene 0: vier Ebene 1: zwei Ebene 2: eins Ebene 2: drei
4
2 13
6
5
7
M. Goedicke Programmierung WiSe 2019/2020 59
paluno

Rekursion: Rekursive Datenstrukturen
public void dfsPreOrder() {
dfsPreOrder(0);
}
private void dfsPreOrder(int n) { System.out.println(Ebene + n + : + value);
if (leftTree != null) leftTree.dfsPreOrder(n + 1); if (rightTree != null) rightTree.dfsPreOrder(n + 1);
}
Ausgabe
Ebene 0: vier Ebene 1: zwei Ebene 2: eins Ebene 2: drei
4 26
13
5
7
M. Goedicke Programmierung WiSe 2019/2020 60
paluno

Rekursion: Rekursive Datenstrukturen
public void dfsPreOrder() {
dfsPreOrder(0);
}
private void dfsPreOrder(int n) { System.out.println(Ebene + n + : + value);
if (leftTree != null) leftTree.dfsPreOrder(n + 1); if (rightTree != null) rightTree.dfsPreOrder(n + 1);
}
Ausgabe
Ebene 0: vier Ebene 1: zwei Ebene 2: eins Ebene 2: drei Ebene 1: sechs
4 26
13
5
7
M. Goedicke Programmierung WiSe 2019/2020 61
paluno

Rekursion: Rekursive Datenstrukturen
public void dfsPreOrder() {
dfsPreOrder(0);
}
private void dfsPreOrder(int n) { System.out.println(Ebene + n + : + value);
if (leftTree != null) leftTree.dfsPreOrder(n + 1); if (rightTree != null) rightTree.dfsPreOrder(n + 1);
}
Ausgabe
Ebene 0: vier Ebene 1: zwei Ebene 2: eins Ebene 2: drei Ebene 1: sechs
4 26
135
7
M. Goedicke Programmierung WiSe 2019/2020 62
paluno

Rekursion: Rekursive Datenstrukturen
public void dfsPreOrder() {
dfsPreOrder(0);
}
private void dfsPreOrder(int n) { System.out.println(Ebene + n + : + value);
if (leftTree != null) leftTree.dfsPreOrder(n + 1); if (rightTree != null) rightTree.dfsPreOrder(n + 1);
}
Ausgabe
Ebene 0: vier Ebene 1: zwei Ebene 2: eins Ebene 2: drei Ebene 1: sechs Ebene 2: funf
4 26
135
7
M. Goedicke Programmierung WiSe 2019/2020 63
paluno

Rekursion: Rekursive Datenstrukturen
public void dfsPreOrder() {
dfsPreOrder(0);
}
private void dfsPreOrder(int n) { System.out.println(Ebene + n + : + value);
if (leftTree != null) leftTree.dfsPreOrder(n + 1); if (rightTree != null) rightTree.dfsPreOrder(n + 1);
}
Ausgabe
Ebene 0: vier Ebene 1: zwei Ebene 2: eins Ebene 2: drei Ebene 1: sechs Ebene 2: funf
4 26
135
7
M. Goedicke Programmierung WiSe 2019/2020 64
paluno

Rekursion: Rekursive Datenstrukturen
public void dfsPreOrder() {
dfsPreOrder(0);
}
private void dfsPreOrder(int n) { System.out.println(Ebene + n + : + value);
if (leftTree != null) leftTree.dfsPreOrder(n + 1); if (rightTree != null) rightTree.dfsPreOrder(n + 1);
}
Ausgabe
Ebene 0: vier Ebene 1: zwei Ebene 2: eins Ebene 2: drei Ebene 1: sechs Ebene 2: funf
4 26 1357
M. Goedicke Programmierung WiSe 2019/2020 65
paluno

Rekursion: Rekursive Datenstrukturen
public void dfsPreOrder() {
dfsPreOrder(0);
}
private void dfsPreOrder(int n) { System.out.println(Ebene + n + : + value);
if (leftTree != null) leftTree.dfsPreOrder(n + 1); if (rightTree != null) rightTree.dfsPreOrder(n + 1);
}
Ausgabe
Ebene 0: vier Ebene 1: zwei Ebene 2: eins Ebene 2: drei Ebene 1: sechs Ebene 2: funf Ebene 2: sieben
4 26 1357
M. Goedicke Programmierung WiSe 2019/2020 66
paluno

Rekursion: Rekursive Datenstrukturen
public void dfsPreOrder() {
dfsPreOrder(0);
}
private void dfsPreOrder(int n) { System.out.println(Ebene + n + : + value);
if (leftTree != null) leftTree.dfsPreOrder(n + 1); if (rightTree != null) rightTree.dfsPreOrder(n + 1);
}
Ausgabe
Ebene 0: vier Ebene 1: zwei Ebene 2: eins Ebene 2: drei Ebene 1: sechs Ebene 2: funf Ebene 2: sieben
4 26 1357
M. Goedicke Programmierung WiSe 2019/2020 67
paluno

Rekursion: Rekursive Datenstrukturen
public void dfsPreOrder() {
dfsPreOrder(0);
}
private void dfsPreOrder(int n) { System.out.println(Ebene + n + : + value);
if (leftTree != null) leftTree.dfsPreOrder(n + 1); if (rightTree != null) rightTree.dfsPreOrder(n + 1);
}
Ausgabe
Ebene 0: vier Ebene 1: zwei Ebene 2: eins Ebene 2: drei Ebene 1: sechs Ebene 2: funf Ebene 2: sieben
4
26 1357
M. Goedicke Programmierung WiSe 2019/2020 68
paluno

Rekursion: Rekursive Datenstrukturen
public void dfsInOrder() {
dfsInOrder(0);
}
private void dfsInOrder(int n) {
if (leftTree != null) leftTree.dfsInOrder(n + 1); System.out.println(Ebene + n + : + value); if (rightTree != null) rightTree.dfsInOrder(n + 1);
}
Ausgabe
4
2
6
1
3
5
7
M. Goedicke Programmierung WiSe 2019/2020 69
paluno

Rekursion: Rekursive Datenstrukturen
public void dfsInOrder() {
dfsInOrder(0);
}
private void dfsInOrder(int n) {
if (leftTree != null) leftTree.dfsInOrder(n + 1); System.out.println(Ebene + n + : + value); if (rightTree != null) rightTree.dfsInOrder(n + 1);
}
Ausgabe
4
2
6
1
3
5
7
M. Goedicke Programmierung WiSe 2019/2020 70
paluno

Rekursion: Rekursive Datenstrukturen
public void dfsInOrder() {
dfsInOrder(0);
}
private void dfsInOrder(int n) {
if (leftTree != null) leftTree.dfsInOrder(n + 1); System.out.println(Ebene + n + : + value); if (rightTree != null) rightTree.dfsInOrder(n + 1);
}
Ausgabe
4
2
6
1
3
5
7
M. Goedicke Programmierung WiSe 2019/2020 71
paluno

Rekursion: Rekursive Datenstrukturen
public void dfsInOrder() {
dfsInOrder(0);
}
private void dfsInOrder(int n) {
if (leftTree != null) leftTree.dfsInOrder(n + 1); System.out.println(Ebene + n + : + value); if (rightTree != null) rightTree.dfsInOrder(n + 1);
}
Ausgabe
4 2
1
6
3
5
7
M. Goedicke Programmierung WiSe 2019/2020 72
paluno

Rekursion: Rekursive Datenstrukturen
public void dfsInOrder() {
dfsInOrder(0);
}
private void dfsInOrder(int n) {
if (leftTree != null) leftTree.dfsInOrder(n + 1); System.out.println(Ebene + n + : + value); if (rightTree != null) rightTree.dfsInOrder(n + 1);
}
Ausgabe
Ebene 2: eins
4 2
1
6
3
5
7
M. Goedicke Programmierung WiSe 2019/2020 73
paluno

Rekursion: Rekursive Datenstrukturen
public void dfsInOrder() {
dfsInOrder(0);
}
private void dfsInOrder(int n) {
if (leftTree != null) leftTree.dfsInOrder(n + 1); System.out.println(Ebene + n + : + value); if (rightTree != null) rightTree.dfsInOrder(n + 1);
}
Ausgabe
Ebene 2: eins
4
2
1
6
3
5
7
M. Goedicke Programmierung WiSe 2019/2020 74
paluno

Rekursion: Rekursive Datenstrukturen
public void dfsInOrder() {
dfsInOrder(0);
}
private void dfsInOrder(int n) {
if (leftTree != null) leftTree.dfsInOrder(n + 1); System.out.println(Ebene + n + : + value); if (rightTree != null) rightTree.dfsInOrder(n + 1);
}
Ausgabe
Ebene 2: eins
Ebene 1: zwei
4
2
1
6
3
5
7
M. Goedicke Programmierung WiSe 2019/2020 75
paluno

Rekursion: Rekursive Datenstrukturen
public void dfsInOrder() {
dfsInOrder(0);
}
private void dfsInOrder(int n) {
if (leftTree != null) leftTree.dfsInOrder(n + 1); System.out.println(Ebene + n + : + value); if (rightTree != null) rightTree.dfsInOrder(n + 1);
}
Ausgabe
Ebene 2: eins
Ebene 1: zwei
4 2
13
6
5
7
M. Goedicke Programmierung WiSe 2019/2020 76
paluno

Rekursion: Rekursive Datenstrukturen
public void dfsInOrder() {
dfsInOrder(0);
}
private void dfsInOrder(int n) {
if (leftTree != null) leftTree.dfsInOrder(n + 1); System.out.println(Ebene + n + : + value); if (rightTree != null) rightTree.dfsInOrder(n + 1);
}
Ausgabe
Ebene 2: eins
Ebene 1: zwei
Ebene 2: drei
4 2
13
6
5
7
M. Goedicke Programmierung WiSe 2019/2020 77
paluno

Rekursion: Rekursive Datenstrukturen
public void dfsInOrder() {
dfsInOrder(0);
}
private void dfsInOrder(int n) {
if (leftTree != null) leftTree.dfsInOrder(n + 1); System.out.println(Ebene + n + : + value); if (rightTree != null) rightTree.dfsInOrder(n + 1);
}
Ausgabe
Ebene 2: eins
Ebene 1: zwei
Ebene 2: drei
4
2
13
6
5
7
M. Goedicke Programmierung WiSe 2019/2020 78
paluno

Rekursion: Rekursive Datenstrukturen
public void dfsInOrder() {
dfsInOrder(0);
}
private void dfsInOrder(int n) {
if (leftTree != null) leftTree.dfsInOrder(n + 1); System.out.println(Ebene + n + : + value); if (rightTree != null) rightTree.dfsInOrder(n + 1);
}
Ausgabe
Ebene 2: eins
Ebene 1: zwei
Ebene 2: drei
4
2 13
6
5
7
M. Goedicke Programmierung WiSe 2019/2020 79
paluno

Rekursion: Rekursive Datenstrukturen
public void dfsInOrder() {
dfsInOrder(0);
}
private void dfsInOrder(int n) {
if (leftTree != null) leftTree.dfsInOrder(n + 1); System.out.println(Ebene + n + : + value); if (rightTree != null) rightTree.dfsInOrder(n + 1);
}
Ausgabe
Ebene 2: eins Ebene 1: zwei Ebene 2: drei Ebene 0: vier
4
2 13
6
5
7
M. Goedicke Programmierung WiSe 2019/2020 80
paluno

Rekursion: Rekursive Datenstrukturen
public void dfsInOrder() {
dfsInOrder(0);
}
private void dfsInOrder(int n) {
if (leftTree != null) leftTree.dfsInOrder(n + 1); System.out.println(Ebene + n + : + value); if (rightTree != null) rightTree.dfsInOrder(n + 1);
}
Ausgabe
Ebene 2: eins Ebene 1: zwei Ebene 2: drei Ebene 0: vier
4 26
13
5
7
M. Goedicke Programmierung WiSe 2019/2020 81
paluno

Rekursion: Rekursive Datenstrukturen
public void dfsInOrder() {
dfsInOrder(0);
}
private void dfsInOrder(int n) {
if (leftTree != null) leftTree.dfsInOrder(n + 1); System.out.println(Ebene + n + : + value); if (rightTree != null) rightTree.dfsInOrder(n + 1);
}
Ausgabe
Ebene 2: eins Ebene 1: zwei Ebene 2: drei Ebene 0: vier
4 26
135
7
M. Goedicke Programmierung WiSe 2019/2020 82
paluno

Rekursion: Rekursive Datenstrukturen
public void dfsInOrder() {
dfsInOrder(0);
}
private void dfsInOrder(int n) {
if (leftTree != null) leftTree.dfsInOrder(n + 1); System.out.println(Ebene + n + : + value); if (rightTree != null) rightTree.dfsInOrder(n + 1);
}
Ausgabe
Ebene 2: eins Ebene 1: zwei Ebene 2: drei Ebene 0: vier Ebene 2: funf
4 26
135
7
M. Goedicke Programmierung WiSe 2019/2020 83
paluno

Rekursion: Rekursive Datenstrukturen
public void dfsInOrder() {
dfsInOrder(0);
}
private void dfsInOrder(int n) {
if (leftTree != null) leftTree.dfsInOrder(n + 1); System.out.println(Ebene + n + : + value); if (rightTree != null) rightTree.dfsInOrder(n + 1);
}
Ausgabe
Ebene 2: eins Ebene 1: zwei Ebene 2: drei Ebene 0: vier Ebene 2: funf
4 26
135
7
M. Goedicke Programmierung WiSe 2019/2020 84
paluno

Rekursion: Rekursive Datenstrukturen
public void dfsInOrder() {
dfsInOrder(0);
}
private void dfsInOrder(int n) {
if (leftTree != null) leftTree.dfsInOrder(n + 1); System.out.println(Ebene + n + : + value); if (rightTree != null) rightTree.dfsInOrder(n + 1);
}
Ausgabe
Ebene 2: eins Ebene 1: zwei Ebene 2: drei Ebene 0: vier Ebene 2: funf Ebene 1: sechs
4 26
135
7
M. Goedicke Programmierung WiSe 2019/2020 85
paluno

Rekursion: Rekursive Datenstrukturen
public void dfsInOrder() {
dfsInOrder(0);
}
private void dfsInOrder(int n) {
if (leftTree != null) leftTree.dfsInOrder(n + 1); System.out.println(Ebene + n + : + value); if (rightTree != null) rightTree.dfsInOrder(n + 1);
}
Ausgabe
Ebene 2: eins Ebene 1: zwei Ebene 2: drei Ebene 0: vier Ebene 2: funf Ebene 1: sechs
4 26 1357
M. Goedicke Programmierung WiSe 2019/2020 86
paluno

Rekursion: Rekursive Datenstrukturen
public void dfsInOrder() {
dfsInOrder(0);
}
private void dfsInOrder(int n) {
if (leftTree != null) leftTree.dfsInOrder(n + 1); System.out.println(Ebene + n + : + value); if (rightTree != null) rightTree.dfsInOrder(n + 1);
}
Ausgabe
Ebene 2: eins Ebene 1: zwei Ebene 2: drei Ebene 0: vier Ebene 2: funf Ebene 1: sechs Ebene 2: sieben
4 26 1357
M. Goedicke Programmierung WiSe 2019/2020 87
paluno

Rekursion: Rekursive Datenstrukturen
public void dfsInOrder() {
dfsInOrder(0);
}
private void dfsInOrder(int n) {
if (leftTree != null) leftTree.dfsInOrder(n + 1); System.out.println(Ebene + n + : + value); if (rightTree != null) rightTree.dfsInOrder(n + 1);
}
Ausgabe
Ebene 2: eins Ebene 1: zwei Ebene 2: drei Ebene 0: vier Ebene 2: funf Ebene 1: sechs Ebene 2: sieben
4 26 1357
M. Goedicke Programmierung WiSe 2019/2020 88
paluno

Rekursion: Rekursive Datenstrukturen
public void dfsInOrder() {
dfsInOrder(0);
}
private void dfsInOrder(int n) {
if (leftTree != null) leftTree.dfsInOrder(n + 1); System.out.println(Ebene + n + : + value); if (rightTree != null) rightTree.dfsInOrder(n + 1);
}
Ausgabe
Ebene 2: eins Ebene 1: zwei Ebene 2: drei Ebene 0: vier Ebene 2: funf Ebene 1: sechs Ebene 2: sieben
4
26 1357
M. Goedicke Programmierung WiSe 2019/2020 89
paluno

Rekursion: Rekursive Datenstrukturen
public void dfsPostOrder() {
dfsPostOrder(0);
}
private void dfsPostOrder(int n) {
if (leftTree != null) leftTree.dfsPostOrder(n + 1); if (rightTree != null) rightTree.dfsPostOrder(n + 1); System.out.println(Ebene + n + : + value);
}
Ausgabe
4
2
6
1
3
5
7
M. Goedicke Programmierung WiSe 2019/2020 90
paluno

Rekursion: Rekursive Datenstrukturen
public void dfsPostOrder() {
dfsPostOrder(0);
}
private void dfsPostOrder(int n) {
if (leftTree != null) leftTree.dfsPostOrder(n + 1); if (rightTree != null) rightTree.dfsPostOrder(n + 1); System.out.println(Ebene + n + : + value);
}
Ausgabe
4
2
6
1
3
5
7
M. Goedicke Programmierung WiSe 2019/2020 91
paluno

Rekursion: Rekursive Datenstrukturen
public void dfsPostOrder() {
dfsPostOrder(0);
}
private void dfsPostOrder(int n) {
if (leftTree != null) leftTree.dfsPostOrder(n + 1); if (rightTree != null) rightTree.dfsPostOrder(n + 1); System.out.println(Ebene + n + : + value);
}
Ausgabe
4
2
6
1
3
5
7
M. Goedicke Programmierung WiSe 2019/2020 92
paluno

Rekursion: Rekursive Datenstrukturen
public void dfsPostOrder() {
dfsPostOrder(0);
}
private void dfsPostOrder(int n) {
if (leftTree != null) leftTree.dfsPostOrder(n + 1); if (rightTree != null) rightTree.dfsPostOrder(n + 1); System.out.println(Ebene + n + : + value);
}
Ausgabe
4 2
1
6
3
5
7
M. Goedicke Programmierung WiSe 2019/2020 93
paluno

Rekursion: Rekursive Datenstrukturen
public void dfsPostOrder() {
dfsPostOrder(0);
}
private void dfsPostOrder(int n) {
if (leftTree != null) leftTree.dfsPostOrder(n + 1); if (rightTree != null) rightTree.dfsPostOrder(n + 1); System.out.println(Ebene + n + : + value);
}
Ausgabe
Ebene 2: eins
4 2
1
6
3
5
7
M. Goedicke Programmierung WiSe 2019/2020 94
paluno

Rekursion: Rekursive Datenstrukturen
public void dfsPostOrder() {
dfsPostOrder(0);
}
private void dfsPostOrder(int n) {
if (leftTree != null) leftTree.dfsPostOrder(n + 1); if (rightTree != null) rightTree.dfsPostOrder(n + 1); System.out.println(Ebene + n + : + value);
}
Ausgabe
Ebene 2: eins
4
2
1
6
3
5
7
M. Goedicke Programmierung WiSe 2019/2020 95
paluno

Rekursion: Rekursive Datenstrukturen
public void dfsPostOrder() {
dfsPostOrder(0);
}
private void dfsPostOrder(int n) {
if (leftTree != null) leftTree.dfsPostOrder(n + 1); if (rightTree != null) rightTree.dfsPostOrder(n + 1); System.out.println(Ebene + n + : + value);
}
Ausgabe
Ebene 2: eins
4 2
13
6
5
7
M. Goedicke Programmierung WiSe 2019/2020 96
paluno

Rekursion: Rekursive Datenstrukturen
public void dfsPostOrder() {
dfsPostOrder(0);
}
private void dfsPostOrder(int n) {
if (leftTree != null) leftTree.dfsPostOrder(n + 1); if (rightTree != null) rightTree.dfsPostOrder(n + 1); System.out.println(Ebene + n + : + value);
}
Ausgabe
Ebene 2: eins
Ebene 2: drei
4 2
13
6
5
7
M. Goedicke Programmierung WiSe 2019/2020 97
paluno

Rekursion: Rekursive Datenstrukturen
public void dfsPostOrder() {
dfsPostOrder(0);
}
private void dfsPostOrder(int n) {
if (leftTree != null) leftTree.dfsPostOrder(n + 1); if (rightTree != null) rightTree.dfsPostOrder(n + 1); System.out.println(Ebene + n + : + value);
}
Ausgabe
Ebene 2: eins
Ebene 2: drei
4
2
13
6
5
7
M. Goedicke Programmierung WiSe 2019/2020 98
paluno

Rekursion: Rekursive Datenstrukturen
public void dfsPostOrder() {
dfsPostOrder(0);
}
private void dfsPostOrder(int n) {
if (leftTree != null) leftTree.dfsPostOrder(n + 1); if (rightTree != null) rightTree.dfsPostOrder(n + 1); System.out.println(Ebene + n + : + value);
}
Ausgabe
Ebene 2: eins
Ebene 2: drei
Ebene 1: zwei
4
2
13
6
5
7
M. Goedicke Programmierung WiSe 2019/2020 99
paluno

Rekursion: Rekursive Datenstrukturen
public void dfsPostOrder() {
dfsPostOrder(0);
}
private void dfsPostOrder(int n) {
if (leftTree != null) leftTree.dfsPostOrder(n + 1); if (rightTree != null) rightTree.dfsPostOrder(n + 1); System.out.println(Ebene + n + : + value);
}
Ausgabe
Ebene 2: eins
Ebene 2: drei
Ebene 1: zwei
4
2 13
6
5
7
M. Goedicke Programmierung WiSe 2019/2020 100
paluno

Rekursion: Rekursive Datenstrukturen
public void dfsPostOrder() {
dfsPostOrder(0);
}
private void dfsPostOrder(int n) {
if (leftTree != null) leftTree.dfsPostOrder(n + 1); if (rightTree != null) rightTree.dfsPostOrder(n + 1); System.out.println(Ebene + n + : + value);
}
Ausgabe
Ebene 2: eins
Ebene 2: drei
Ebene 1: zwei
4 26
13
5
7
M. Goedicke Programmierung WiSe 2019/2020 101
paluno

Rekursion: Rekursive Datenstrukturen
public void dfsPostOrder() {
dfsPostOrder(0);
}
private void dfsPostOrder(int n) {
if (leftTree != null) leftTree.dfsPostOrder(n + 1); if (rightTree != null) rightTree.dfsPostOrder(n + 1); System.out.println(Ebene + n + : + value);
}
Ausgabe
Ebene 2: eins
Ebene 2: drei
Ebene 1: zwei
4 26
135
7
M. Goedicke Programmierung WiSe 2019/2020 102
paluno

Rekursion: Rekursive Datenstrukturen
public void dfsPostOrder() {
dfsPostOrder(0);
}
private void dfsPostOrder(int n) {
if (leftTree != null) leftTree.dfsPostOrder(n + 1); if (rightTree != null) rightTree.dfsPostOrder(n + 1); System.out.println(Ebene + n + : + value);
}
Ausgabe
Ebene 2: eins Ebene 2: drei Ebene 1: zwei Ebene 2: funf
4 26
135
7
M. Goedicke Programmierung WiSe 2019/2020 103
paluno

Rekursion: Rekursive Datenstrukturen
public void dfsPostOrder() {
dfsPostOrder(0);
}
private void dfsPostOrder(int n) {
if (leftTree != null) leftTree.dfsPostOrder(n + 1); if (rightTree != null) rightTree.dfsPostOrder(n + 1); System.out.println(Ebene + n + : + value);
}
Ausgabe
Ebene 2: eins Ebene 2: drei Ebene 1: zwei Ebene 2: funf
4 26
135
7
M. Goedicke Programmierung WiSe 2019/2020 104
paluno

Rekursion: Rekursive Datenstrukturen
public void dfsPostOrder() {
dfsPostOrder(0);
}
private void dfsPostOrder(int n) {
if (leftTree != null) leftTree.dfsPostOrder(n + 1); if (rightTree != null) rightTree.dfsPostOrder(n + 1); System.out.println(Ebene + n + : + value);
}
Ausgabe
Ebene 2: eins Ebene 2: drei Ebene 1: zwei Ebene 2: funf
4 26 1357
M. Goedicke Programmierung WiSe 2019/2020 105
paluno

Rekursion: Rekursive Datenstrukturen
public void dfsPostOrder() {
dfsPostOrder(0);
}
private void dfsPostOrder(int n) {
if (leftTree != null) leftTree.dfsPostOrder(n + 1); if (rightTree != null) rightTree.dfsPostOrder(n + 1); System.out.println(Ebene + n + : + value);
}
Ausgabe
Ebene 2: eins Ebene 2: drei Ebene 1: zwei Ebene 2: funf Ebene 2: sieben
4 26 1357
M. Goedicke Programmierung WiSe 2019/2020 106
paluno

Rekursion: Rekursive Datenstrukturen
public void dfsPostOrder() {
dfsPostOrder(0);
}
private void dfsPostOrder(int n) {
if (leftTree != null) leftTree.dfsPostOrder(n + 1); if (rightTree != null) rightTree.dfsPostOrder(n + 1); System.out.println(Ebene + n + : + value);
}
Ausgabe
Ebene 2: eins Ebene 2: drei Ebene 1: zwei Ebene 2: funf Ebene 2: sieben
4 26 1357
M. Goedicke Programmierung WiSe 2019/2020 107
paluno

Rekursion: Rekursive Datenstrukturen
public void dfsPostOrder() {
dfsPostOrder(0);
}
private void dfsPostOrder(int n) {
if (leftTree != null) leftTree.dfsPostOrder(n + 1); if (rightTree != null) rightTree.dfsPostOrder(n + 1); System.out.println(Ebene + n + : + value);
}
Ausgabe
Ebene 2: eins Ebene 2: drei Ebene 1: zwei Ebene 2: funf Ebene 2: sieben Ebene 1: sechs
4 26 1357
M. Goedicke Programmierung WiSe 2019/2020 108
paluno

Rekursion: Rekursive Datenstrukturen
public void dfsPostOrder() {
dfsPostOrder(0);
}
private void dfsPostOrder(int n) {
if (leftTree != null) leftTree.dfsPostOrder(n + 1); if (rightTree != null) rightTree.dfsPostOrder(n + 1); System.out.println(Ebene + n + : + value);
}
Ausgabe
Ebene 2: eins Ebene 2: drei Ebene 1: zwei Ebene 2: funf Ebene 2: sieben Ebene 1: sechs
4
26 1357
M. Goedicke Programmierung WiSe 2019/2020 109
paluno

Rekursion: Rekursive Datenstrukturen
public void dfsPostOrder() {
dfsPostOrder(0);
}
private void dfsPostOrder(int n) {
if (leftTree != null) leftTree.dfsPostOrder(n + 1); if (rightTree != null) rightTree.dfsPostOrder(n + 1); System.out.println(Ebene + n + : + value);
}
Ausgabe
Ebene 2: eins Ebene 2: drei Ebene 1: zwei Ebene 2: funf Ebene 2: sieben Ebene 1: sechs Ebene 0: vier
4
26 1357
M. Goedicke Programmierung WiSe 2019/2020 110
paluno

Rekursion: Rekursive Datenstrukturen
Wenn man einen Binarbaum mit einer Breitensuche durchlauft, dann muss man die Nachfolger der bereits besuchten Elemente in einer Liste speichern.
Die Liste wird dabei mit folgendem Prinzip bearbeitet: man entfernt immer dasjenige Element, das sich aktuell am langsten in der Liste befindet.
Dieses Prinzip nennt man FIFO (First In First Out) und eine Datenstruktur, die nach diesem Prinzip arbeitet, nennt man Warteschlange.
public class Warteschlange { private List liste;
// Konstruktoren und Methoden
}
T
Warteschlange
-liste:List
+Warteschlange() +add(value:T):void +remove():T +isEmpty():boolean
M. Goedicke Programmierung WiSe 2019/2020 111
paluno

Rekursion: Rekursive Datenstrukturen
Quelle: http://www.asklubo.com
public Warteschlange() {
liste = new LinkedList ();
}
public void add(T value) { liste.add(value);
}
public T remove() {
return liste.remove(0);
}
public boolean isEmpty() { return liste.isEmpty();
}
T
Warteschlange
-liste:List
+Warteschlange() +add(value:T):void +remove():T +isEmpty():boolean
M. Goedicke Programmierung WiSe 2019/2020 112
paluno

Rekursion: Rekursive Datenstrukturen
Quelle: http://www.asklubo.com
public Warteschlange() {
liste = new LinkedList ();
}
public void add(T value) { liste.add(value);
}
public T remove() {
return liste.remove(0);
}
public boolean isEmpty() { return liste.isEmpty();
}
T
Warteschlange
-liste:List
+Warteschlange() +add(value:T):void +remove():T +isEmpty():boolean
M. Goedicke Programmierung WiSe 2019/2020 113
paluno

Rekursion: Rekursive Datenstrukturen
Quelle: http://www.asklubo.com
public Warteschlange() {
liste = new LinkedList ();
}
public void add(T value) { liste.add(value);
}
public T remove() {
return liste.remove(0);
}
public boolean isEmpty() { return liste.isEmpty();
}
T
Warteschlange
-liste:List
+Warteschlange() +add(value:T):void +remove():T +isEmpty():boolean
M. Goedicke Programmierung WiSe 2019/2020 114
paluno

Rekursion: Rekursive Datenstrukturen
Quelle: http://www.asklubo.com
public Warteschlange() {
liste = new LinkedList ();
}
public void add(T value) { liste.add(value);
}
public T remove() {
return liste.remove(0);
}
public boolean isEmpty() { return liste.isEmpty();
}
T
Warteschlange
-liste:List
+Warteschlange() +add(value:T):void +remove():T +isEmpty():boolean
M. Goedicke Programmierung WiSe 2019/2020 115
paluno

Rekursion: Rekursive Datenstrukturen
Quelle: http://www.asklubo.com
public Warteschlange() {
liste = new LinkedList ();
}
public void add(T value) { liste.add(value);
}
public T remove() {
return liste.remove(0);
}
public boolean isEmpty() { return liste.isEmpty();
}
T
Warteschlange
-liste:List
+Warteschlange() +add(value:T):void +remove():T +isEmpty():boolean
M. Goedicke Programmierung WiSe 2019/2020 116
paluno

Rekursion: Rekursive Datenstrukturen
public void breadthFirstSearch() {
Warteschlange > warteschlange = new Warteschlange<>(); warteschlange.add(this);
while (!warteschlange.isEmpty()) {
BinaryTree tree = warteschlange.remove(); if (tree != null) {
} }
}
System.out.print(tree.value + ); warteschlange.add(tree.leftTree); warteschlange.add(tree.rightTree);
4
Warteschlange: Ausgabe:
2
6
1
3
5
7
M. Goedicke Programmierung WiSe 2019/2020 117
paluno

Rekursion: Rekursive Datenstrukturen
public void breadthFirstSearch() {
Warteschlange > warteschlange = new Warteschlange<>(); warteschlange.add(this);
while (!warteschlange.isEmpty()) {
BinaryTree tree = warteschlange.remove(); if (tree != null) {
} }
}
System.out.print(tree.value + ); warteschlange.add(tree.leftTree); warteschlange.add(tree.rightTree);
Warteschlange: Ausgabe:
4
4
2
6
1
3
5
7
M. Goedicke Programmierung WiSe 2019/2020 118
paluno

Rekursion: Rekursive Datenstrukturen
public void breadthFirstSearch() {
Warteschlange > warteschlange = new Warteschlange<>(); warteschlange.add(this);
while (!warteschlange.isEmpty()) {
BinaryTree tree = warteschlange.remove(); if (tree != null) {
} }
}
System.out.print(tree.value + ); warteschlange.add(tree.leftTree); warteschlange.add(tree.rightTree);
4
Warteschlange: Ausgabe:
2
6
1
3
5
7
M. Goedicke Programmierung WiSe 2019/2020 119
paluno

Rekursion: Rekursive Datenstrukturen
public void breadthFirstSearch() {
Warteschlange > warteschlange = new Warteschlange<>(); warteschlange.add(this);
while (!warteschlange.isEmpty()) {
BinaryTree tree = warteschlange.remove(); if (tree != null) {
} }
}
System.out.print(tree.value + ); warteschlange.add(tree.leftTree); warteschlange.add(tree.rightTree);
4
Warteschlange: Ausgabe: vier
2
6
1
3
5
7
M. Goedicke Programmierung WiSe 2019/2020 120
paluno

Rekursion: Rekursive Datenstrukturen
public void breadthFirstSearch() {
Warteschlange > warteschlange = new Warteschlange<>(); warteschlange.add(this);
while (!warteschlange.isEmpty()) {
BinaryTree tree = warteschlange.remove(); if (tree != null) {
} }
}
System.out.print(tree.value + ); warteschlange.add(tree.leftTree); warteschlange.add(tree.rightTree);
2
6
4
Warteschlange: Ausgabe: vier
2
6
1
3
5
7
M. Goedicke Programmierung WiSe 2019/2020 121
paluno

Rekursion: Rekursive Datenstrukturen
public void breadthFirstSearch() {
Warteschlange > warteschlange = new Warteschlange<>(); warteschlange.add(this);
while (!warteschlange.isEmpty()) {
BinaryTree tree = warteschlange.remove(); if (tree != null) {
} }
}
System.out.print(tree.value + ); warteschlange.add(tree.leftTree); warteschlange.add(tree.rightTree);
2
6
4
Warteschlange: Ausgabe: vier
2
6
1
3
5
7
M. Goedicke Programmierung WiSe 2019/2020 122
paluno

Rekursion: Rekursive Datenstrukturen
public void breadthFirstSearch() {
Warteschlange > warteschlange = new Warteschlange<>(); warteschlange.add(this);
while (!warteschlange.isEmpty()) {
BinaryTree tree = warteschlange.remove(); if (tree != null) {
} }
}
System.out.print(tree.value + ); warteschlange.add(tree.leftTree); warteschlange.add(tree.rightTree);
6
4
Warteschlange: Ausgabe: vier
2
6
1
3
5
7
M. Goedicke Programmierung WiSe 2019/2020 123
paluno

Rekursion: Rekursive Datenstrukturen
public void breadthFirstSearch() {
Warteschlange > warteschlange = new Warteschlange<>(); warteschlange.add(this);
while (!warteschlange.isEmpty()) {
BinaryTree tree = warteschlange.remove(); if (tree != null) {
} }
}
System.out.print(tree.value + ); warteschlange.add(tree.leftTree); warteschlange.add(tree.rightTree);
6
4
Warteschlange: Ausgabe: vier zwei
2
6
1
3
5
7
M. Goedicke Programmierung WiSe 2019/2020 124
paluno

Rekursion: Rekursive Datenstrukturen
public void breadthFirstSearch() {
Warteschlange > warteschlange = new Warteschlange<>(); warteschlange.add(this);
while (!warteschlange.isEmpty()) {
BinaryTree tree = warteschlange.remove(); if (tree != null) {
} }
}
System.out.print(tree.value + ); warteschlange.add(tree.leftTree); warteschlange.add(tree.rightTree);
6
1
3
4
Warteschlange: Ausgabe: vier zwei
2
6
1
3
5
7
M. Goedicke Programmierung WiSe 2019/2020 125
paluno

Rekursion: Rekursive Datenstrukturen
public void breadthFirstSearch() {
Warteschlange > warteschlange = new Warteschlange<>(); warteschlange.add(this);
while (!warteschlange.isEmpty()) {
BinaryTree tree = warteschlange.remove(); if (tree != null) {
} }
}
System.out.print(tree.value + ); warteschlange.add(tree.leftTree); warteschlange.add(tree.rightTree);
6
1
3
4 2
Warteschlange: Ausgabe: vier zwei
6
1
3
5
7
M. Goedicke Programmierung WiSe 2019/2020 126
paluno

Rekursion: Rekursive Datenstrukturen
public void breadthFirstSearch() {
Warteschlange > warteschlange = new Warteschlange<>(); warteschlange.add(this);
while (!warteschlange.isEmpty()) {
BinaryTree tree = warteschlange.remove(); if (tree != null) {
} }
}
System.out.print(tree.value + ); warteschlange.add(tree.leftTree); warteschlange.add(tree.rightTree);
1
3
4 26
Warteschlange: Ausgabe: vier zwei
1
3
5
7
M. Goedicke Programmierung WiSe 2019/2020 127
paluno

Rekursion: Rekursive Datenstrukturen
public void breadthFirstSearch() {
Warteschlange > warteschlange = new Warteschlange<>(); warteschlange.add(this);
while (!warteschlange.isEmpty()) {
BinaryTree tree = warteschlange.remove(); if (tree != null) {
} }
}
System.out.print(tree.value + ); warteschlange.add(tree.leftTree); warteschlange.add(tree.rightTree);
1
3
4 26
Warteschlange: Ausgabe: vier zwei sechs
1
3
5
7
M. Goedicke Programmierung WiSe 2019/2020 128
paluno

Rekursion: Rekursive Datenstrukturen
public void breadthFirstSearch() {
Warteschlange > warteschlange = new Warteschlange<>(); warteschlange.add(this);
while (!warteschlange.isEmpty()) {
BinaryTree tree = warteschlange.remove(); if (tree != null) {
} }
}
System.out.print(tree.value + ); warteschlange.add(tree.leftTree); warteschlange.add(tree.rightTree);
1
3
5
7
4 26
Warteschlange: Ausgabe: vier zwei sechs
1
3
5
7
M. Goedicke Programmierung WiSe 2019/2020 129
paluno

Rekursion: Rekursive Datenstrukturen
public void breadthFirstSearch() {
Warteschlange > warteschlange = new Warteschlange<>(); warteschlange.add(this);
while (!warteschlange.isEmpty()) {
BinaryTree tree = warteschlange.remove(); if (tree != null) {
} }
}
System.out.print(tree.value + ); warteschlange.add(tree.leftTree); warteschlange.add(tree.rightTree);
1
3
5
7
4 26
Warteschlange: Ausgabe: vier zwei sechs
1
3
5
7
M. Goedicke Programmierung WiSe 2019/2020 130
paluno

Rekursion: Rekursive Datenstrukturen
public void breadthFirstSearch() {
Warteschlange > warteschlange = new Warteschlange<>(); warteschlange.add(this);
while (!warteschlange.isEmpty()) {
BinaryTree tree = warteschlange.remove(); if (tree != null) {
} }
}
System.out.print(tree.value + ); warteschlange.add(tree.leftTree); warteschlange.add(tree.rightTree);
3
5
7
4 26
Warteschlange: Ausgabe: vier zwei sechs
1
3
5
7
M. Goedicke Programmierung WiSe 2019/2020 131
paluno

Rekursion: Rekursive Datenstrukturen
public void breadthFirstSearch() {
Warteschlange > warteschlange = new Warteschlange<>(); warteschlange.add(this);
while (!warteschlange.isEmpty()) {
BinaryTree tree = warteschlange.remove(); if (tree != null) {
} }
}
System.out.print(tree.value + ); warteschlange.add(tree.leftTree); warteschlange.add(tree.rightTree);
3
5
7
4 26
Warteschlange:
Ausgabe: vier zwei sechs eins
1
3
5
7
M. Goedicke Programmierung WiSe 2019/2020 132
paluno

Rekursion: Rekursive Datenstrukturen
public void breadthFirstSearch() {
Warteschlange > warteschlange = new Warteschlange<>(); warteschlange.add(this);
while (!warteschlange.isEmpty()) {
BinaryTree tree = warteschlange.remove(); if (tree != null) {
} }
}
System.out.print(tree.value + ); warteschlange.add(tree.leftTree); warteschlange.add(tree.rightTree);
3
5
7
4 26
Warteschlange:
Ausgabe: vier zwei sechs eins
1
3
5
7
M. Goedicke Programmierung WiSe 2019/2020 133
paluno

Rekursion: Rekursive Datenstrukturen
public void breadthFirstSearch() {
Warteschlange > warteschlange = new Warteschlange<>(); warteschlange.add(this);
while (!warteschlange.isEmpty()) {
BinaryTree tree = warteschlange.remove(); if (tree != null) {
} }
}
System.out.print(tree.value + ); warteschlange.add(tree.leftTree); warteschlange.add(tree.rightTree);
5
7
4 26
Warteschlange:
Ausgabe: vier zwei sechs eins
13
5
7
M. Goedicke Programmierung WiSe 2019/2020 134
paluno

Rekursion: Rekursive Datenstrukturen
public void breadthFirstSearch() {
Warteschlange > warteschlange = new Warteschlange<>(); warteschlange.add(this);
while (!warteschlange.isEmpty()) {
BinaryTree tree = warteschlange.remove(); if (tree != null) {
} }
}
System.out.print(tree.value + ); warteschlange.add(tree.leftTree); warteschlange.add(tree.rightTree);
5
7
4 26
Warteschlange:
Ausgabe: vier zwei sechs eins drei
13
5
7
M. Goedicke Programmierung WiSe 2019/2020 135
paluno

Rekursion: Rekursive Datenstrukturen
public void breadthFirstSearch() {
Warteschlange > warteschlange = new Warteschlange<>(); warteschlange.add(this);
while (!warteschlange.isEmpty()) {
BinaryTree tree = warteschlange.remove(); if (tree != null) {
} }
}
System.out.print(tree.value + ); warteschlange.add(tree.leftTree); warteschlange.add(tree.rightTree);
5
7
4 26
Warteschlange:
Ausgabe: vier zwei sechs eins drei
13
5
7
M. Goedicke Programmierung WiSe 2019/2020 136
paluno

Rekursion: Rekursive Datenstrukturen
public void breadthFirstSearch() {
Warteschlange > warteschlange = new Warteschlange<>(); warteschlange.add(this);
while (!warteschlange.isEmpty()) {
BinaryTree tree = warteschlange.remove(); if (tree != null) {
} }
}
System.out.print(tree.value + ); warteschlange.add(tree.leftTree); warteschlange.add(tree.rightTree);
7
4 26
135
Warteschlange:
Ausgabe: vier zwei sechs eins drei
7
M. Goedicke Programmierung WiSe 2019/2020 137
paluno

Rekursion: Rekursive Datenstrukturen
public void breadthFirstSearch() {
Warteschlange > warteschlange = new Warteschlange<>(); warteschlange.add(this);
while (!warteschlange.isEmpty()) {
BinaryTree tree = warteschlange.remove(); if (tree != null) {
} }
}
System.out.print(tree.value + ); warteschlange.add(tree.leftTree); warteschlange.add(tree.rightTree);
7
4 26
135
Warteschlange:
Ausgabe: vier zwei sechs eins drei funf
7
M. Goedicke Programmierung WiSe 2019/2020 138
paluno

Rekursion: Rekursive Datenstrukturen
public void breadthFirstSearch() {
Warteschlange > warteschlange = new Warteschlange<>(); warteschlange.add(this);
while (!warteschlange.isEmpty()) {
BinaryTree tree = warteschlange.remove(); if (tree != null) {
} }
}
System.out.print(tree.value + ); warteschlange.add(tree.leftTree); warteschlange.add(tree.rightTree);
7
4 26
135
Warteschlange:
Ausgabe: vier zwei sechs eins drei funf
7
M. Goedicke Programmierung WiSe 2019/2020 139
paluno

Rekursion: Rekursive Datenstrukturen
public void breadthFirstSearch() {
Warteschlange > warteschlange = new Warteschlange<>(); warteschlange.add(this);
while (!warteschlange.isEmpty()) {
BinaryTree tree = warteschlange.remove(); if (tree != null) {
} }
}
System.out.print(tree.value + ); warteschlange.add(tree.leftTree); warteschlange.add(tree.rightTree);
4 26 1357
Warteschlange:
Ausgabe: vier zwei sechs eins drei funf
M. Goedicke Programmierung WiSe 2019/2020 140
paluno

Rekursion: Rekursive Datenstrukturen
public void breadthFirstSearch() {
Warteschlange > warteschlange = new Warteschlange<>(); warteschlange.add(this);
while (!warteschlange.isEmpty()) {
BinaryTree tree = warteschlange.remove(); if (tree != null) {
} }
}
System.out.print(tree.value + ); warteschlange.add(tree.leftTree); warteschlange.add(tree.rightTree);
4 26 1357
Warteschlange:
Ausgabe: vier zwei sechs eins drei funf sieben
M. Goedicke Programmierung WiSe 2019/2020 141
paluno

Rekursion: Rekursive Datenstrukturen
public void breadthFirstSearch() {
Warteschlange > warteschlange = new Warteschlange<>(); warteschlange.add(this);
while (!warteschlange.isEmpty()) {
BinaryTree tree = warteschlange.remove(); if (tree != null) {
} }
}
System.out.print(tree.value + ); warteschlange.add(tree.leftTree); warteschlange.add(tree.rightTree);
4 26 1357
Warteschlange:
Ausgabe: vier zwei sechs eins drei funf sieben
M. Goedicke Programmierung WiSe 2019/2020 142
paluno

Rekursion: Zusammenfassung
Jedes Programm besitzt zur Laufzeit einen Aufrufstack. Wenn die Terminierungsbedingung einer rekursiven Methode nicht erreicht wird, dann wird ein StackOverflowError ausgelost.
Neben rekursiven Methoden gibt es auch rekursive Datenstrukturen.
Einen Binarbaum kann man mit Tiefensuche oder mit Breitensuche durchlaufen.
M. Goedicke Programmierung WiSe 2019/2020 143
paluno