[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 Bücher ähnelt: 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 Rücksprungadresse.
▪ Die Rücksprungadresse gibt an, an welcher Stelle das Programm nach Abarbeitung der Methode fortgesetzt wird.
▪ Jede Methodeninstanz definiert einen eigenen Namensraum für die Parameter und lokalen Variablen der zugrunde liegenden Methode.
▪ Während der Ausführung 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: Fakultät
▪ Für eine natürliche Zahl n > 1 sei f(n) = n ∙ f(n-1). Zudem sei f(1) = 1. Dann heißt f Fakultätsfunktion und man schreibt f(n) = n!.
▪ Diese Definition lässt sich leicht in eine JAVA-Methode umsetzen:
public int fakultaet(int n) { if (n == 1) {
return 1;
} else {
return n * fakultaet(n – 1); }
}
▪ Wir überlegen uns nun, wie sich der Aufrufstack beim Aufruf von fakultaet(4) verhält, wobei wir auf die Widergabe der main()-
Methode verzichten.
M. Goedicke – Programmierung WiSe 2019/2020 4
© paluno

Rekursion: Fakultät
▪ Zuerst wird der Namensraum für 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: Fakultät
▪ Anschließend wird der Namensraum für 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: Fakultät
▪ Anschließend wird der Namensraum für 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: Fakultät
▪ Anschließend wird der Namensraum für den Methodenaufruf mit dem Parameter n = 1 aufgebaut. Da an dieser Stelle n = 1 gilt, wird 1
zurückgegeben.
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: Fakultät
▪ Anschließend springt das Programm zu der Auswertung des Ausdruck 2 * fakultaet(1) zurück, wobei fakultaet(1) durch den Wert 1 ersetzt und daher 2 zurückgegeben 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: Fakultät
▪ Anschließend springt das Programm zu der Auswertung des Ausdruck 3 * fakultaet(2) zurück, wobei fakultaet(2) durch den Wert 2 ersetzt und daher 6 zurückgegeben 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: Fakultät
▪ Abschließend springt das Programm zu der Auswertung des Ausdruck 4 * fakultaet(3) zurück, wobei fakultaet(3) durch den Wert 6 ersetzt und daher 24 zurückgegeben 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 Fakultätsbeispiel zeigt, dass der Aufrufstack bei der Abarbeitung rekursiver Methoden stark anwachsen kann.
▪ Daher sind rekursive Lösungen eines Problems in der Regel weniger performant als iterative Lösungen; rekursive Lösungen sind aber oft einfacher zu verstehen.
▪ Da die Größe des Aufrufstacks durch den zur Verfügung stehenden Speicherplatz beschränkt 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() führt zu einem StackOverflowError, da keine Terminierungsbedingung angegeben wurde.
▪ Wenn die Terminierungsbedingung einer rekursiven Methode erfüllt ist, dann muss der Rückgabewert 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 für ein Typ das Element (hier element) hat,
Dokument, Person, Buch, Auto …
▪ Wie das im Detail funktioniert, wird später beschrieben. ▪ Java (ab Version 5) unterstützt 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.
▪ Für 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)=truefürL=[a]oderL=[a|L′],
• mem(a,L)=mem(a,L′)fürL=[x|L′]unda≠xsowie • mem(a,[x])=falsefüra≠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 Binärbaum besteht aus einem Element und kann einen linken oder einen rechten Teilbaum besitzen. Wenn also leftTree und rightTree Binärbäume sind, dann gilt:
• (a,null,null) ist ein Binärbaum ohne Teilbäume.
• (a,leftTree,null) ist ein Binärbaum mit einem linken Teilbaum.
• (a,null,rightTree) ist ein Binärbaum mit einem rechten Teilbaum.
• (a,leftTree,rightTree) ist ein Binärbaum mit einem linken und einem rechten Teilbaum.
▪ Beispiel: (a,(b,(c,null,null),(d,null,null)),(e,null,(f,null,
null))) ist ein Binärbaum mit sechs Elementen.
a
b
e
c
d
f
M. Goedicke – Programmierung WiSe 2019/2020 17
© paluno

Rekursion: Rekursive Datenstrukturen
▪ Die rekursive Definition eines Binärbaums kann man unmittelbar in ein Klasse umsetzen:
Wir nehmen an, dass jedes Element des Binärbaums aus einem Schlüssel 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 Schlüssels 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 Schlüssels 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 Schlüssels 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 Schlüssels 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 Schlüssels 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 Schlüssels 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 Schlüssels 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 Schlüssels 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 Schlüssels 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 Binärbaum eingefügt werden soll, dann muss entschieden werden, ob man das Element in den linken oder in den rechten Teilbaum einfügt.
▪ Im folgenden nehmen wir daher an, dass eine Ordnung auf der Menge der Schlüssel 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 erfüllt.
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 Binärbaum Tree = (a,…,…) einzufügen:
▪ 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 fügen wir b in den
Binärbaum 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 fügen wir b in den Binärbaum 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 Binärbaum Tree = (a,…,…) einzufügen:
▪ 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 fügen wir b in den
Binärbaum 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 fügen wir b in den Binärbaum 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 Binärbaum Tree = (a,…,…) einzufügen:
▪ 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 fügen wir b in den Binärbaum
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 fügen wir b in den Binärbaum 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 Binärbaum Tree = (a,…,…) einzufügen:▪ 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 fügen wir b in denBinärbaum 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 fügen wir b in den Binärbaum rightTree ein.
7
5
3
1
7>4∧7>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 Binärbaum Tree = (a,…,…) einzufügen:
▪ 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 fügen wir b in den
Binärbaum 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 fügen wir b in den Binärbaum rightTree ein.
5
3
1
5>4∧5<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 Binärbaum Tree = (a,…,…) einzufügen:▪ 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 fügen wir b in denBinärbaum 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 fügen wir b in den Binärbaum rightTree ein.
3
1
3<4∧3>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 Binärbaum Tree = (a,…,…) einzufügen:
▪ 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 fügen wir b in den Binärbaum
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 fügen wir b in den Binärbaum rightTree ein.
1
1<4∧1<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 Binärbaums hängt von der Reihenfolge ab, in der die Elemente eingefügt 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 Binärbaums hängt von der Reihenfolge ab, in der die Elemente eingefügt 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 Binärbaums hängt von der Reihenfolge ab, in der die Elemente eingefügt wurden:
3
3>1∧3>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 Binärbaums hängt von der Reihenfolge ab, in der die Elemente eingefügt 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 Binärbaums hängt von der Reihenfolge ab, in der die Elemente eingefügt 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 Binärbaums hängt von der Reihenfolge ab, in der die Elemente eingefügt wurden:
3
3>2
M. Goedicke – Programmierung WiSe 2019/2020 42
2
1
3
© paluno

Rekursion: Rekursive Datenstrukturen
▪ Wenn man einen Binärbaum mit Hilfe der insert(S,T)-Methode aufbaut, dann erhält man einen Suchbaum:
• (a,null,null) ist ein Suchbaum.
• (a,leftTree,null) ist ein Suchbaum, wenn für alle Elemente b von
leftTree stets b.key ≤ a.key gilt.
• (a,null,rightTree) ist ein Suchbaum, wenn für alle Elemente c von
rightTree stets a.key < c.key gilt.• (a,leftTree,rightTree) ist ein Binärbaum, wenn für alle Elemente b von leftTree stets b.key ≤ a.key gilt und wenn für 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 durchgeführten Schlüsselvergleiche hängt von der Höhe 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 lässt 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 DatenstrukturenHöhe des Baums: 0 Höhe des Baums: 1 Höhe des Baums: 1444 2Höhe des Baums: 2 Höhe des Baums: 2 Höhe des Baums: 22644626264 113▪ Ein Binärbaum mit der Höhe 2 enthält mindestens 3 = 2 + 1 und höchstens 7 = 23 – 1 Elemente.▪ Ein Binärbaum mit der Höhe h enthält mindestens h + 1 und höchstens 2h+1 – 1 Elemente.▪ Für die Höhe h eines Binärbaums 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 Schlüsseln sortieren.▪ Um die Elemente sortiert auszugeben, muss man den Suchbaum in der richtigen Reihenfolge durchlaufen.▪ Einen Binärbaum 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. Anschließend bearbeitet man leftTree rekursiv. Danach bearbeitet man rightTree rekursiv.InOrder: Bei der Bearbeitung von (a,leftTree,rightTree) bearbeitet man zuerst leftTree rekursiv. Anschließend bearbeitet man a. Danach bearbeitet man rightTree rekursiv.PostOrder: Bei der Bearbeitung von (a,leftTree,rightTree) bearbeitet man zuerst leftTree rekursiv. Anschließend 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, “fünf”); tree.insert(1, “eins”);
// Durchlauf mit Tiefensuche
}
Elemente des Binärbaums
key: 4
value: vier
key: 6
value: sechs
key: 2
value: zwei
key: 3
value: drei
key: 7 value: sieben
key: 5
value: fünf
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: fünf
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: fünf
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: fünf
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: fünf 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: fünf 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: fünf 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: fünf
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: fünf
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: fünf 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: fünf 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: fünf 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: fünf 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: fünf 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: fünf
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: fünf
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: fünf
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: fünf 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: fünf 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: fünf 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: fünf 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: fünf 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 Binärbaum mit einer Breitensuche durchläuft, 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 längsten 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 fünf
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 fünf
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 fünf
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 fünf 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 fünf 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 ausgelöst.
▪ Neben rekursiven Methoden gibt es auch rekursive Datenstrukturen.
▪ Einen Binärbaum kann man mit Tiefensuche oder mit Breitensuche durchlaufen.
M. Goedicke – Programmierung WiSe 2019/2020 143
© paluno