CS计算机代考程序代写 Java Programmierung … Rekursion

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<4 4 2 6 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 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.
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<6 4 2 6 5 7 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 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.
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 36 4 2 6 1 3 5 7 © 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 41 2 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 Datenstrukturen Höhe des Baums: 0 Höhe des Baums: 1 Höhe des Baums: 1 4 4 4 2 Höhe des Baums: 2 Höhe des Baums: 2 Höhe des Baums: 2 2 6 4 4 6 2 6 2 6 4 1 1 3 ▪ 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 Datenstrukturen public 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