Objektorientierte Programmierung OOP
KE6 Algorithmus und Datenstrukturen
KE6 Algorithmus und Datenstrukturen
Bestimmen Sie den Pfad mit der minimalen Entfernung zwischen Dresden und Karlsruhe an Hand der Abbildung.
Der kürzeste Weg von Dresden nach Karlsruhe geht über Erfurt, Würzburg und Stuttgart und hat eine Länge von 580 Kilometern.
Nennen Sie einige Besonderheiten von Graphen.
Ein Pfad, dessen Start- und Zielknoten identisch ist, wird als Zyklus bezeichnet.
Gerichtete Graphen ohne Zyklen werden als gerichtete, azyklische Graphen, (engl. directed acyclic graph, kurz: DAG) bezeichnet.
Wichtige Algorithmen auf Graphen sind zum Beispiel die Suche von Elementen und Pfaden, insbesondere von kürzesten Wegen.
Ein ungerichteter Graph wird als zusammenhängend bezeichnet, wenn es von jedem Knoten einen Pfad zu jedem anderen Knoten gibt. Ein gerichteter Graph wird als stark zusammenhängend bezeichnet, wenn es zwischen allen Knoten einen gerichteten Pfad gibt. Ein gerichteter Graph wird als schwach zusammenhängend
bezeichnet, wenn es zwischen allen Knoten einen ungerichteten Pfad gibt.
Was ist eine Baumdarstellung und wo wird sie höffig eingesetzt?
Im täglichen Leben benutzen wir Baumdarstellungen, um z. B. die Personal- oder Abteilungshierarchie einer Organisation zu beschreiben oder einen Familienstammbaum übersichtlich zu präsentieren. Auch das Dateisystem Ihres Computers ist als Baumstruktur organisiert.
Baum
Ein Baum (engl. tree) ist ein gerichteter, schwach zusammenhängender, azyklischer Graph. Jeder Knoten besitzt einen maximalen Eingangsgrad von 1.
Was sind Bestandteile einer Datenstruktur vom Typ Baum?
Jeder nicht leere Baum hat einen speziellen Knoten, die Wurzel (engl. root). Die Wurzel hat als einziger Knoten einen Eingangsgrad von 0.
Der Startknoten der eingehenden Kante wird als direkter Vorgänger- oder Elternknoten bezeichnet. Alle Knoten, außer der Wurzel, haben genau einen direkten Vorgängerknoten.
Jeder Knoten kann eine endliche Anzahl von direkten Nachfolger- oder Kindknoten besitzen.
Knoten, die keine Nachfolger, also einen Ausgangsgrad von 0, besitzen, werden Blätter (engl. leaf) genannt.
Die Höhe eines Baums ist das Maximum der Knoten, die auf dem Weg von einem Blatt zur Wurzel liegen.
Häufig werden bei der Programmierung Baumdatenstrukturen mit bestimmten Eigenschaften benutzt:
· Ein Binärer Baum ist ein Baum, bei dem jeder Knoten höchstens zwei Nachfolgerknoten besitzt. Binäre Bäume werden bevorzugt als effiziente Suchstrukturen verwendet.
· Bei einem balancierten Baum (engl. balanced tree) B haben alle Unterbäume von B möglichst die gleiche Tiefe, d. h. zwischen der Wurzel und jedem Blatt von B bis auf eine vorgegebene Differenz (meist 1) gleich viele innere Knoten.
· Ein AVL-Baum ist ein binärer Baum, bei dem sich die Höhen der Unterbäume jedes Knotens höchstens um 1 unterscheiden und jeder Unterbaum ein AVL-Baum ist.
Die Abbildung veranschaulicht die Begriffe Wurzel, Knoten und Blatt. In der Informatik wächst ein Baum üblicherweise von oben nach unten, so dass sich seine Wurzel oben und seine Blätter unten befinden. Die Höhe des Baum in der Abbildung ist 4.
Aus dem bisher Gesagten können wir die folgenden Konzepte ableiten:
Die Vorgänger eines Knotens U sind alle Knoten bis zur Wurzel, die direkt oder indirekt Vorgänger von U sind.
Die Nachfolger von U sind seine direkten Nachfolger, die Nachfolger ihrer Nachfolger usw. bis hin zu den Blättern.
Der durch einen Knoten und alle seine Nachfolgerknoten aufgespannte Baum wird als Unterbaum bezeichnet.
Knoten, die den gleichen Vorgängerknoten haben, werden Geschwisterknoten (engl. sibling) genannt.
Angenommen, wir haben ein Buch mit 4 Kapiteln 1, ..., 4, wobei
-
Kapitel 1 aus drei Unterkapiteln 1.1, ..., 1.3 besteht,
-
Kapitel 2 zwei Unterkapitel 2.1 und 2.2 aufweist,
-
Kapitel 3 vier Unterkapitel besitzt und
-
Kapitel 4 drei Unterkapitel hat.
-
Unterkapitel 3.2 bestehe aus zwei Unterkapiteln 3.2.1 und 3.2.2.
Zeichnen Sie einen Baum, der die Struktur des Buches repräsentiert. Die Knoten des Baumes sollen die Nummern der Kapitel und Unterkapitel tragen, und die Geschwisterknoten sollen in aufsteigender Reihenfolge von links nach rechts angeordnet sein.
Kapitelstruktur
Welche vier Durchlaufstrategien gibt es bei Bäumen?
Es wird zwischen vier möglichen Strategien, den Baum systematisch zu durchlaufen, unterschieden:
-
pre-order: wir untersuchen zuerst den betrachteten Knoten, dann den linken und dann den rechten Nachfolger;
-
post-order: wir besuchen zuerst den linken Nachfolger, dann den rechten Nachfolger und schließlich den betrachteten Knoten;
-
in-order: hierbei besuchen wir zuerst den linken Nachfolger, dann den betrachteten Knoten und schließlich den rechten Nachfolger;
-
level-order: zuerst werden alle Knoten auf einer Ebene untersucht, dann alle Nachfolgerknoten jedes Knotens der betrachteten Ebene von links nach rechts.
Die in-order-Strategie kann lediglich bei binären Bäumen verwendet werden. Alle anderen Strategien können auch bei anderen Bäumen angewendet werden.
Die von uns gezeigten Durchlaufstrategien bevorzugen ein links-nach-rechts-Verfahren. Wir hätten ebenso ein rechts-nach-links-Verfahren vorschlagen können, doch der Durchlauf von links nach rechts ist der Standard.
Durchlaufen Sie die beiden in der Abbildung dargestellten Bäume mit der pre-order-, post-order- und level-order-Strategie und geben Sie jeweils an, in welcher Reihenfolge die Knoten besucht werden. Durchlaufen Sie den binären Baum außerdem auch mit Hilfe der in-order-Strategie.
linker Baum:
pre-order: 5, 2, 9, 0, 1, 4, 7, 3, 6, 8
post-order: 9, 0, 4, 1, 2, 7, 6, 8, 3, 5
level-order: 5, 2, 7, 3, 9, 0, 1, 6, 8, 4
rechter Baum:
pre-order: 6, 2, 1, 3, 5, 8, 7, 4, 9
post-order: 3, 5, 1, 2, 7, 9, 4, 8, 6
level-order: 6, 2, 8, 1, 7, 4, 3, 5, 9
in-order: 2, 3, 1, 5, 6, 7, 8, 9, 4
Was sind in Java Binärbäume?
Binäre Bäume sind Datenstrukturen, die in jedem Knoten einen Eintrag speichern und deren Knoten einen maximalen Ausgangsgraf von 2 aufweisen. Ein binärer Baum kann in Java ähnlich wie eine Liste implementiert werden. Bei einem binären Baum muss jeder Knoten jedoch nicht nur einen, sondern zwei Verweise auf seine Nachfolger speichern können.
Definieren Sie die Klasse BinaryTreeNode für unsere Baumknote.
public class BinaryTreeNode { private int entry; private BinaryTreeNode leftChild; private BinaryTreeNode rightChild; public BinaryTreeNode(int e) { this.entry = e; } public BinaryTreeNode(int e, BinaryTreeNode left, BinaryTreeNode right) { this(e); this.leftChild = left; this.rightChild = right; } // Getter und Setter // ...}
Entwerfen Sie die BinaryTree Klasse.
public class BinaryTree { private BinaryTreeNode root; public BinaryTree() { } public BinaryTree(BinaryTreeNode root) { this.root = root; } // Getter und Setter // ...}
Entwickeln Sie die Anweisungen, um den Baum aus der Abbildung darzustellen.
BinaryTreeNode a = new BinaryTreeNode(6, null, new BinaryTreeNode(5)); BinaryTreeNode b = new BinaryTreeNode(2, new BinaryTreeNode(9), a); BinaryTreeNode c = new BinaryTreeNode(1, new BinaryTreeNode(4), new BinaryTreeNode(8)); BinaryTreeNode root = new BinaryTreeNode(7, b, c); BinaryTree bt = new BinaryTree(root);
Welche Suchmethoden sind bei Binärbäumen anwendbar.
Rekursive Methoden sind gut geeignet, einen Baum zu durchsuchen und zu verändern, wenn man eine der ersten drei Durchquerungsstrategien pre-, post-, oder in-order benutzt. Diese Verfahren spiegeln die rekursive Struktur eines Baumes, der aus linken und rechten Unterbäumen besteht, wider.
Im Gegensatz dazu ist die level-order-Durchquerung für ein rekursives Verarbeitungsschema weniger gut geeignet, da sie den Verknüpfungen eines Baums nicht folgt, sondern sie quer durchschneidet.
Wir wollen nun eine Methode printPreorder() in der Klasse BinaryTree implementieren, die die Knoten in der Reihenfolge ausgibt, in der sie mit Hilfe der pre-order-Strategie besucht werden. Auch hier benutzen wir wieder eine private Hilfsmethode.
public class BinaryTree { private BinaryTreeNode root; // ... public void printPreorder() { // start with root printPreorder(root); } private void printPreorder(BinaryTreeNode tn) { // base case: empty subtree if (tn == null) { return; } // visit current node System.out.print(tn.getEntry() + " "); // visit left child printPreorder(tn.getLeftChild()); // visit right child printPreorder(tn.getRightChild()); }}
Entwickeln Sie analog zur Methode printPreorder() die Methoden printInorder() und printPostorder() für die KlasseBinaryTree.
public class BinaryTree { Private BinaryTreeNode root; / / ... public void printInorder () { / / Mit Root starten printInorder (root); } private void printInorder (BinaryTreeNode tn) { / / Base case: empty Teilbaum if (tn == null) { zurück; } / / Besuch linke Kind printInorder (tn.getLeftChild ()); / / Besuch aktuellen Knoten System.out.print (tn.getEntry () + ""); / / Besuch rechte Kind printInorder (tn.getRightChild ()); } public void printPostorder () { / / Mit Root starten printPostorder (root); } private void printPostorder (BinaryTreeNode tn) { / / Base case: empty Teilbaum if (tn == null) { zurück; } / / Besuch linke Kind printPostorder (tn.getLeftChild ()); / / Besuch rechte Kind printPostorder (tn.getRightChild ()); / / Besuch aktuellen Knoten System.out.print (tn.getEntry () + ""); } }
Entwickeln Sie eine Methode public contains(int x), die überprüft, ob der Baum den Wert x enthält. Geben Sie an, welche Suchstrategie Ihre Methode verwendet.
public class BinaryTree { Private BinaryTreeNode root; / / ... public boolean contains (int x) { Rückkehr enthält (Wurzel, x); } private boolean contains (BinaryTreeNode tn, int x) { / / Base case 1: leere Teilbaum if (tn == null) { return false; } / / Search in preorder / / Vergleichen x mit aktuellen Knoten if (tn.getEntry () == x) { / / Base case 2: x gefunden return true; } / / Search in der linken und in der rechten Teilbaum Rückkehr enthält (tn.getLeftChild (), x) | | Enthält (tn.getRightChild (), x); }}
Entwickeln Sie eine Methode public contains(int x), die überprüft, ob der Baum den Wert x enthält. Geben Sie an, welche Suchstrategie Ihre Methode verwendet.
public class BinaryTree { Private BinaryTreeNode root; / / ... public boolean contains (int x) { Rückkehr enthält (Wurzel, x); } private boolean contains (BinaryTreeNode tn, int x) { / / Base case 1: leere Teilbaum if (tn == null) { return false; } / / Search in preorder / / Vergleichen x mit aktuellen Knoten if (tn.getEntry () == x) { / / Base case 2: x gefunden return true; } / / Search in der linken und in der rechten Teilbaum Rückkehr enthält (tn.getLeftChild (), x) | | Enthält (tn.getRightChild (), x); }}
Nach welchem Schema ist ein Suchbaum aufgebaut?
Der Wert, der im linken Kind gespeichert ist, ist immer kleiner als der Wert des Elternknotens, und der Wert des rechten Kindes ist immer größer als der Wert des Elternknotens. Ein Baum, dessen Elemente diese Eigenschaft aufweisen, wird auch Suchbaum genannt. In einem solchen Suchbaum kann jedes Element maximal einmal vorkommen.
Zeichnen Sie den Suchbaum, der entsteht, wenn Sie der Reihe nach die Werte 7, 12, 20, 3, 5, 1, 6, 9 einfügen.
Suchbaum
Beschreiben Sie das Verfahren der Tiefensuche.
Bei der Tiefensuche hingegen wird erst ein Nachbar gewählt und anschließend von diesem Nachbarn wieder ein Nachbar ausgewählt. Es wird solange diese Strategie angewendet, bis ein Knoten keine Nachbarn hat oder all seine Nachbarn schon besucht wurden. Ist dies der Fall, geht man einen Schritt zurück und schaut, ob dieser Knoten noch andere unbesuchte Knoten aufweist. Diese Strategie des Zurückgehens wird auch als Backtracking bezeichnet. Bei der Tiefensuche geht man ähnlich wie in einem Labyrinth so lange weiter, bis man in eine Sackgasse gelangt, arbeitet sich dann wieder ein Stück zurück und versucht eine andere Abzweigung. Man sucht also zunächst in der Tiefe des Graphen. Die Abbildung veranschaulicht dieses Vorgehen. Die Nummern zeigen an, in welcher Reihenfolge die Knoten besucht werden.
Um eine Breitensuche systematisch durchführen zu können, benötigen wir eine Warteschlange.
1.
Füge den Startknoten in die Warteschlange ein.
2.
Entnehme solange den ersten, also ältesten Knoten aus der Warteschlange, bis du einen unbesuchten erhältst.
3.
Vergleiche den Wert des Knotens mit dem gesuchten Knoten.
4.
Sind sie identisch, so ist der gesuchte Knoten gefunden und die Suche kann beendet werden.
5.
Sind sie nicht identisch, so wird der Knoten als besucht gekennzeichnet.
6.
Füge alle noch nicht besuchten Nachbarn des Knotens in die Warteschlange ein.
7.
Ist die Warteschlange leer, so konnte der Knoten nicht gefunden werden und die Suche kann beendet werden.
8.
Fahre mit Schritt 2 fort.
Erläutern Sie der Verfahren der Breitensuche.
Die beiden Verfahren unterscheiden sich darin, in welcher Reihenfolge sie die Knoten durchsuchen. Beide Verfahren müssen speichern, welche Knoten schon besucht wurden, um nicht im Kreis zu laufen. Die BreitensucheBreitensucheBreitensuche betrachtet zunächst alle direkten Nachbarn des aktuellen Knotens. Wenn das gesuchte Element nicht dabei ist, so werden als nächstes die Nachbarn der Nachbarn betrachtet und so weiter. In welcher Reihenfolge die direkten Nachbarn untersucht werden, spielt keine Rolle. Man tastet sich bei der Suche also in der vollen Breite immer weiter vor. Abb. 36.5-1 veranschaulicht dieses Vorgehen. Die Nummern zeigen an, in welcher Reihenfolge die Knoten besucht werden.
Für die Tiefensuche können wir das folgende systematische Verfahren verwenden:
1.
Überprüfe ob der aktuelle Knoten der gesuchte Knoten ist.
2.
Sind die Knoten identisch, so ist der gesuchte Knoten gefunden und die Suche kann beendet werden.
3.
Sind sie nicht identisch, so wird der Knoten als besucht gekennzeichnet.
4.
Hat der Knoten keine unbesuchten Nachbarn, so muss die Suche hier erfolgreich abgebrochen werden und zum Vorgänger zurückgekehrt werden.
5.
Wähle einen unbesuchten Nachbarn des aktuellen Knotens aus und suche von dort rekursiv mit diesem Verfahren weiter.
6.
Wird ohne Erfolg vom besuchten Nachbarn hierher zurückgekehrt, so fahre mit Schritt 4 fort.
Implementieren Sie eine Methode boolean istEnthalten(String wert, String[] feld), die überprüft, ob die übergebene Zeichenkette im Feld enthalten ist. Was müssen Sie hierbei im Gegensatz zur Implementierung für Felder primitiver Typen beachten?
Die Elemente sollten nicht mit ==, sonder mit Hilfe der Methode equals() verglichen werden.
boolean istEnthalten(String wert, String[] feld) { if (feld == null) { return false; } for (String s : feld) { // Wert gefunden? if (s.equals(wert)) { return true; } } return false; }
Implementieren Sie eine Methode int bestimmeAnzahl(int wert, int[] feld), die zählt,
wie oft der übergebene Wert in dem Feld enthalten ist.
int bestimmeAnzahl(int wert, int[] feld) { if (feld == null) { return 0; } int anzahl = 0; for (int i : feld) { // Wert gefunden? if (i == wert) { anzahl++; } } return anzahl; }
Gegeben seien die folgenden Klassen
public class Kunde { // ... }
public class Rechnung {
private Kunde rechnungsempfaenger; // ...
public Kunde liefereRechnungsempfaenger() {
return this.rechnungsempfaenger;
}
public int bestimmeBetragInCent() {
// ...
}
// ...
}
public class Rechnungssammlung {
private Rechnung[] rechnungen;
// ...
}
Implementieren Sie eine Methode
int bestimmeGesamtbetragAllerRechnungenVon(Kunde k)
in der Klasse Rechnungssammlung, die die Summe aller Rechnungsbeträge dieses Kunden in Cent bestimmt.
int bestimmeGesamtbetragAllerRechnungenVon(Kunde k) { // wenn kein Kunde oder keine Rechnungen vorhanden if (k == null || rechnungen == null) { return 0; } int betrag = 0; // alle Rechnungen betrachten for (Rechnung r : rechnungen) { // wenn gesuchter Kunde if (r.liefereRechnungsempfaenger() == k) { // Betrag dazuaddieren betrag += r.bestimmeBetragInCent(); } } return betrag; }
Implementieren Sie eine Methode Rechnung findeTeuersteRechnung() in der Klasse Rechnungssammlung, die die Rechnung mit dem größten Betrag bestimmt.
Rechnung findeTeuersteRechnung() { // wenn keine Rechnungen vorhanden if (rechnungen == null) { return null; } Rechnung max = null; // alle Rechnungen betrachten for (Rechnung r : rechnungen) { // wenn noch kein Maximum gefunden // oder aktuelle Rechnung teurer if (max == null || max.bestimmeBetragInCent() < r.bestimmeBetragInCent()) { // Maximum anpassen max = r; } } return max;}
Wie können in einem Feld Teilfolgen ermittelt werden?
Man beginnt damit, den ersten Wert des Feldes mit dem ersten Wert der Zahlenfolge zu vergleichen. Stimmen die Werte überein, vergleicht man anschließend die zweiten Werte und so weiter. Stimmen die Werte nicht überein, so weiß man lediglich, dass die Zahlenfolge nicht beim ersten Element des Feldes beginnend gefunden werden kann. Man beginnt dann mit dem zweiten Element des Feldes und vergleicht es mit dem ersten der gesuchten Folge. Stimmen diese überein, so vergleicht man anschließend das dritte mit dem zweiten und so weiter. Wurde die gesamte Teilfolge gefunden, so kann die Methode beendet werden. Bei der Implementierung müssen wir aufpassen, dass wir nicht auf ungültige Feldelemente zugreifen.
Wie können in einem Feld Teilfolgen ermittelt werden?
boolean istTeilfolge(int[] feld, int[] gesuchteFolge) { // es muss nicht bis zum letzten Element gesucht werden, // da dort die Folge nicht mehr vollständig vorkommen kann for (int i = 0; i < feld.length - gesuchteFolge.length + 1; i++) { for (int j = 0; j < gesuchteFolge.length; j++) { // Vergleiche entsprechende Einträge if (feld[i + j] != gesuchteFolge[j]) { // Zahl an Position j stimmt nicht überein // suche bei i+1 weiter break; } else if (j == gesuchteFolge.length - 1) { // gesamte Folge wurde gefunden return true; } } } // Teilfolge konnte nicht vollständig gefunden werden return false; }
Implementieren Sie eine Methode int bestimmeAnfangdesWorts(char[] feld, String wort), die die Position zurückliefert, ab der das Wort vollständig im Feld gefunden wurde. Wird das Wort nicht vollständig gefunden, so soll -1 zurückgeliefert werden.
int bestimmeAnfangdesWorts(char[] feld, String wort) { for (int i = 0; i < feld.length - wort.length() + 1; i++) { for (int j = 0; j < wort.length(); j++) { // Vergleiche entsprechende Buchstaben if (feld[i + j] != wort.charAt(j)) { // Buchstabe an Position j stimmt nicht überein // suche bei i+1 weiter break; } else if (j == wort.length() - 1) { // gesamtes Wort wurde gefunden return i; } } } // Wort konnte nicht vollständig gefunden werden return -1; }
Wie kann das suchen in großen Datenbeständen beschleunigt werden?
Wenn die Datenelemente gemäß einer Ordnungsrelation sortiert werden. Der Suchalgorithmus kann diese Eigenschaft nutzen, um ein bestimmtes Element in der sortierten Menge zu finden.
Schreiben eine Methode, die Aufsteigend ein einfaches Feld sortiert.
void sortiereAufsteigend(int[] feld) { // beginne beim zweiten Element und betrachte // die Liste bis zum Index i - 1 als sortiert for (int i = 1; i < feld.length; i++) { // gehe solange von i nach links // bis das Element an die richtige // Stelle gerutscht ist for (int j = i; j > 0; j--) { if (feld[j - 1] > feld[j]) { // wenn linkes groesser, // vertausche die Elemente int temp = feld[j]; feld[j] = feld[j - 1]; feld[j - 1] = temp; } else { // das Element ist // an der richtigen Stelle break; } } }}
Wie viele Vergleichs- und Vertauschungsoperationen benötigt der Algorithmus „Sortieren beim Einfügen“, um das folgende Feld zu sortieren?
int[] beispiel = {4, 35, 23, 5, 2, 67, 45, 21}; Als Vergleich zählt die Auswertung der if-Bedingung.
Wir betrachten die drei Anweisungen im if-Block als eine Vertauschungsoperation.
Es werden 18 Vergleiche und 12 Vertauschungen benötigt.
Entwerfen Sie eine Methode void sortiereAbsteigend(String[] feld), die absteigend ein Feld von Zeichenketten sortiert.
void sortiereAbsteigend(String[] feld) { // beginne beim zweiten Element und betrachte // die Liste bis zum Index i - 1 als sortiert for (int i = 1; i < feld.length; i++) { // gehe solange von i nach links // bis das Element an die richtige // Stelle gerutscht ist for (int j = i; j > 0; j--) { if (feld[j - 1].compareTo(feld[j]) < 0) { // wenn linkes kleiner, // vertausche die Elemente String temp = feld[j]; feld[j] = feld[j - 1]; feld[j - 1] = temp; } else { // sonst, ist das Element // an der richtigen Stelle break; } } } }
Schreiben Sie eine Methode, die ein Feld nach dem klassischer Sortierungsalgorithmus Bubblesort bearbeitet.
void bubblesort(int[] feld) { // es werden maximal feld.length - 1 Durchläufe benötigt for (int i = 0; i < feld.length - 1; i++) { // solange keine Vertauschungen vorgenommen werden // ist das Feld sortiert boolean sorted = true; // Durchlaufe das Feld, in jedem Durchlauf muss // ein Element weniger berücksichtigt werden for (int j = 0; j < feld.length - 1 - i; j++) { if (feld[j] > feld[j + 1]) { // wenn linkes größer // dann vertausche int temp = feld[j]; feld[j] = feld[j + 1]; feld[j + 1] = temp; // Feld ist nicht sortiert sorted = false; } } if (sorted) { // keine Vertauschungen, Feld ist // folglich vollständig sortiert break; } } }
Entwerfen Sie mit Hilfe des Bubblesort-Algorithmus eine Methode void sortiereAufsteigend(Rechnung[] rechnungen), die die Rechnungen aufsteigend nach ihren Beträgen sortiert.
void sortiereAufsteigend(Rechnung[] rechnungen) { // es werden maximal length - 1 Durchläufe benötigt for (int i = 0; i < rechnungen.length - 1; i++) { // solange keine Vertauschungen vorgenommen werden // ist das Feld sortiert boolean sorted = true; // Durchlaufe das Feld, in jedem Durchlauf muss // ein Element weniger berücksichtigt werden for (int j = 0; j < rechnungen.length - 1 - i; j++) { if (rechnungen[j].bestimmeBetragInCent() > rechnungen[j + 1].bestimmeBetragInCent()) { // wenn linkes größer dann vertausche Rechnung temp = rechnungen[j]; rechnungen[j] = rechnungen[j + 1]; rechnungen[j + 1] = temp; // Feld ist nicht sortiert sorted = false; } } if (sorted) { // keine Vertauschungen, Feld ist // folglich vollständig sortiert break; } } }
Der Algorithmus „Sortieren durch Auswählen“ (engl. selection sortselection sortselection sort) nimmt am Anfang das komplette Feld als unsortiert an, sucht sich das größte Element unter den unsortierten Elementen und vertauscht es, wenn nötig, anschließend mit dem letzten Element des unsortierten Bereichs.
Im nächsten Schritt gehört das letzte Element nun zum sortierten Bereich. Es wird wiederum das größte Element des unsortierten Bereichs mit dem letzten Element vertauscht, so dass es anschließend zum sortierten Bereich gehört. Der Algorithmus terminiert, wenn der unsortierte Bereich aus einem Element besteht.
Wenden Sie den Algorithmus auf das folgende Feld an und zählen Sie die dabei nötigen Vergleichs- und Vertauschungsoperationen .
int[] beispiel = {4, 35, 23, 5, 2, 67, 45, 21};
Es werden 28 Vergleiche und 6 Vertauschungen benötigt.
Implementieren Sie die Methode void sortiere(double[] feld) so, dass sie das übergebene Feld mit Hilfe des Algorithmus „Sortieren durch Auswählen“ sortiert.
void sortiere(double[] feld) { // suche length-1 mal das Maximum for (int i = 0; i < feld.length - 1; i++) { // Position des Maximums int max = 0; // Suche das Maximum for (int j = 1; j < feld.length - i; j++) { // wenn aktueller Wert größer als Maximum if (feld[j] > feld[max]) { // speichere aktuelle Position max = j; } } // setzte das Maximum an die letzte der unsortierten // Positionen, wenn es dort nicht schon ist if (max != feld.length - 1 - i) { double temp = feld[max]; feld[max] = feld[feld.length - 1 - i]; feld[feld.length - 1 - i] = temp; } } }
Wann ist eine Methode oder Funktion Rekursiv?
Ein Algorithmus ist rekursiv, wenn er Methoden (oder Funktionen) enthält, die sich selbst aufrufen.
Jede rekursive Lösung umfasst zwei grundlegende Teile:
· den Basisfall, für den das Problem auf einfache Weise gelöst werden kann, und
· die rekursive Definition.
Die rekursive Definition besteht aus drei Facetten:
1.die Aufteilung des Problems in einfachere Teilprobleme,
2.die rekursive Anwendung auf alle Teilprobleme und
3.die Kombination der Teillösungen in eine Lösung für das Gesamtproblem.
Bei der rekursiven Anwendung ist darauf zu achten, dass wir uns mit zunehmender Rekursionstiefe an den Basisfall annähern. Wir bezeichnen diese Eigenschaft als Konvergenz der Rekursion.
Was passiert, wenn die Methode summeRekursiv() mit negativen Werten aufgerufen wird? Wie kann dieses Problem gelöst werden?
Es tritt ein StackOverflowError auf. Um dies zu verhindern, kann bei negativen Werten entweder eineIllegalArgumentException geworfen oder die Abfrage n == 0 durch n <= 0 ersetzt werden.
Implementieren Sie eine Methode fakultaetIterativ (int n), die iterativ die Fakultät berechnet und eine MethodefakultaetRekursiv(int n), die die Fakultät rekursiv berechnet. Die Methoden sollen dabei nur Werte akzeptieren.
int fakultaetIterativ(int n) { // ungültige Werte abfangen if (n < 0) { throw new IllegalArgumentException(); } // Ergebnis initialisieren int erg = 1; for (int i = 2; i <= n; i++) { erg *= i; } return erg; } int fakultaetRekursiv(int n) { // ungültige Werte abfangen if (n < 0) { throw new IllegalArgumentException(); } // Basisfall if (n == 0) { return 1; } // rekursiver Aufruf return n * fakultaetRekursiv(n - 1); }
Begründen Sie, warum die Lösung für fakultaetRekursiv() konvergiert.
In jedem Schritt wird n um eins verringert. Somit nähert sich n immer weiter an den Basisfall 0 an.
Schreiben Sie die Methode double power(int p, int n), die für zwei ganze Zahlen und rekursiv den Wert berechnet. Testen Sie Ihr Programm und vergleichen Sie es mit der Lösung von Selbsttestaufgabe 14.1-2, die eine iterative Variante aufzeigt.
public double power(int p, int n) { if (n < 0) { return 1.0 / power(p, -n); } if (n == 0) { return 1; } return p * power(p, n - 1); }
-
- 1 / 106
-
Cartes-fiches
Schreiben Sie eine rekursive Methode, die alle Einträge auf dem Bildschirm ausgibt.
public void printList() { printList(this.head); } private void printList(ListNode node) { if (node == null) { return; } node.print(); System.out.print(" "); printList(node.getNext()); }
Schreiben Sie ein Methodenpaar printReverseList(), das die Einträge der Listenknoten in umgekehrter Reihenfolge druckt.
public void printReverseList() { printReverseList(this.head); } private void printReverseList(ListNode node) { if (node == null) { return; } printReverseList(node.getNext()); node.print(); System.out.print(" "); }
Eine Liste ist ein dynamisches Objekt, das es uns auch erlaubt, Knoten zu löschen oder neue Knoten an einer bestimmten Position einzufügen. Wenn wir einen bestimmten Knoten entfernen wollen, müssen wir zwei Aufgaben lösen:
1. Wir müssen den Knoten, der entfernt werden soll, in der verketteten Liste finden, und
2. Wir müssen dafür sorgen, dass die dem gesuchten Knoten benachbarten Knoten wieder so miteinander verkettet sind, dass ihre ursprüngliche Reihenfolge erhalten bleibt.
Wir definieren eine rekursive Methode remove(), die einen Knoten node und einen ganzzahligen Wert value als Argumente akzeptiert. Die prinzipielle Idee ist die, dass die Methode rekursiv durch die Liste läuft, um den Knoten mit dem Eintrag valuezu finden. Wenn solch ein Knoten gefunden werden kann, wird er entfernt und sein Nachfolger wird zurückgegeben. Falls der Wert in keinem Knoten vorkommt, bleibt die Liste unverändert.
Erneut haben wir eine öffentliche Methode und einen nicht-öffentlichen rekursiven Algorithmus definiert. Beachten Sie, dass hier zwei Basisfälle vorliegen:
1.Ein Basisfall tritt auf, wenn kein passender Knoten in der Liste gefunden wurde oder wenn die Liste leer ist (Zeile 2 ).
2. Der zweite Basisfall liegt vor, wenn der Eintrag eines Knotens in der Liste mit dem gesuchten Wert, der als zweiter Parameter (value) beim Aufruf der Methode übergeben wurde, übereinstimmt (Zeile 5).
Falls keiner dieser Basisfälle auftritt, wird die Methode remove() rekursiv auf den Rest der Liste angewendet (Zeile 8). Das Ergebnis jedes rekursiven Aufrufs ist entweder die ursprüngliche Restliste oder die um den gesuchten Knoten verringerte Restliste. Wir müssen aber auf jeden Fall das Ergebnis mit dem Knoten, der auf die ursprüngliche Restliste verwies, über dasnext-Attribut verknüpfen (Zeile 8), um bei der Rückabwicklung der rekursiven Aufrufe die sich aus den Basisfällen ergebende Restliste mit dem unveränderten Vorspann der Ursprungsliste Knoten für Knoten wieder zu verknüpfen.
Wir definieren eine rekursive Methode remove(), die einen Knoten node und einen ganzzahligen Wert value als Argumente akzeptiert. Die prinzipielle Idee ist die, dass die Methode rekursiv durch die Liste läuft, um den Knoten mit dem Eintrag valuezu finden. Wenn solch ein Knoten gefunden werden kann, wird er entfernt und sein Nachfolger wird zurückgegeben. Falls der Wert in keinem Knoten vorkommt, bleibt die Liste unverändert.
public void remove(int value) { this.head = remove(this.head, value); } private ListNode remove(ListNode node, int value) { // 1 if (node == null) { // 2 return null; // 3 } // 4 if (node.getEntry() == value) { // 5 return node.getNext(); // 6 } // 7 node.setNext(remove(node.getNext(), value)); // 8 return node; // 9 }
Was würde passieren, wenn wir Zeile 8 wie folgt:
remove(node.getNext(), value); // 8
änderten und
1. Methode remove(5) auf die Liste anwendeten?
1. Die Liste bleibt unverändert.
2.Die Liste enthält nur noch die Elemente .
3. Die Liste ist leer.
2. Was wäre das Ergebnis des Aufrufs remove(0)?
Antwort 1 beantwortet die erste Frage richtig. Da keine neue Liste konstruiert wird, liefert die private, rekursive remove()-Methode gemäß Zeile 7 als Ergebnis den Wert des ersten Aufrufs, das head-Attribut, zurück.
Die Antwort auf Frage 2 ist die gleiche wie auf Frage 1.
Schreiben Sie ein Methodenpaar contains(), das rekursiv prüft, ob in der Liste ein Knoten mit einem bestimmten Wert vorhanden ist:
public boolean contains(int value) { //... } private boolean contains(...) { //... }
public boolean contains(int value) { return contains(this.head, value); } private boolean contains(ListNode node, int value) { if (node == null) { return false; } if (node.getEntry() == value) { return true; } return contains(node.getNext(), value); }
Beschreiben Sie den Basisfall der Methode contains() und erörtern Sie, warum die Rekursion konvergiert.
Hier gibt es zwei Basisfälle: der erste ist das Ende der Liste bzw. eine leere Liste, der zweite ist der Fall, dass ein passendes Element gefunden wird. Falls der gesuchte Eintrag gefunden wird, endet das Verfahren nach endlich vielen Schritten. Falls der gesuchte Eintrag nicht gefunden wird, erreichen wir nach endlich vielen Schritten über die next-Attribute das Ende der Liste, das durch den null-Verweis gekennzeichnet ist, und das Verfahren konvergiert durch den ersten Basisfall.
Nicht immer möchte man neue Einträge am Anfang einer Liste einfügen, wie es bisher durch die Methode add() geschieht. Wir wollen die add()-Methode überladen, um die Möglichkeit zu schaffen, einen Knoten mit einem neuen Eintrag an einer gewählten Stelle index in Listen einzufügen.
public void add(int index, int value) { if (index < 0 || index > size()) { throw new IndexOutOfBoundsException("index muss im " + "Bereich von 0 bis " + size() + " liegen."); } this.head = add(this.head, index, value); } private ListNode add(ListNode node, int steps, int value) { // 1 if (steps == 0) { // 2 return new ListNode(value, node); // 3 } // 4 node.setNext(add(node.getNext(), steps - 1, value)); // 5 return node; // 6 }
Die private rekursive add()-Methode bewältigt mehrere Aufgaben:
-
Zunächst muss sie sich rekursiv an die Einfügestelle heranzählen (steps - 1 in Zeile 5).
-
Ist die Einfügestelle erreicht (Zeile 2), muss ein neuer Knoten mit dem erwünschten Eintrag und einer Referenz auf den Nachfolgerknoten erzeugt werden (Zeile 3). Dies ist der Basisfall.
-
Das Ergebnis jedes rekursiven Aufrufs ist eine Teilliste, die mit dem Knoten, der auf die ursprüngliche Teilliste verwies, durch setNext() verknüpft wird (Zeile 5), Hier erfolgt auch die Verkettung des Vorgängerknotens mit dem neuen Knoten.
Die öffentlichen add()-Methode hat vor dem Aufruf der privaten add()-Methode noch die wichtige Aufgabe, zu prüfen, ob die im Parameter index übergebene Einfügestelle zulässig ist.
Verkettete Listen können viele weitere Methoden haben. So könnte man z. B. den Eintrag an einer bestimmten Position abrufen, die Liste leeren, eine Teilliste erzeugen wollen und vieles mehr.
Implementieren sie eine Methode, um den Eintrag an einer bestimmten Position abzurufen (ohne die Liste zu verändern):
public int get(int index) { //... } Bedenken Sie den Fall, dass die Methode mit einem ungültigen Index als Parameter aufgerufen werden könnte. Entwerfen Sie je eine iterative und eine rekursive Lösung.
public int get (int index) { if (index <0 | | index> = size ()) { throw new IndexOutOfBoundsException ( "Ungültiger Index"); } ListNode current = this.head; for (int i = 0; i <index; i + +) { Strom = current.getNext (); } zurück current.getEntry (); } Rekursiv:
public int get (int index) { if (index <0 | | index> = size ()) { throw new IndexOutOfBoundsException ( "Ungültiger Index"); } zurück zu bekommen (this.head, index) getEntry (). } Private ListNode bekommen (ListNode Knoten int Stufen) { if (Schritte == 0) { zurück Knoten; } zurück zu bekommen (node.getNext (), nur wenige Schritte - 1); }
Implementieren Sie eine Methode, um die Liste zu leeren.
public void clear() { //... }
public void clear() { this.head = null; }
Implementieren Sie eine Methode, die eine Teilliste zurückliefert.
public LinkedList subList(int fromIndex, int toIndex) { //... } Die Teilliste soll alle Einträge zwischen fromIndex (einschließlich) und toIndex (ausschließlich) in der richtigen Reihenfolge enthalten. Sind fromIndex und toIndex identisch, so ist die resultierende Liste leer. Bedenken Sie den Fall, dass die Methode mit ungültigen Indizes als Parameter aufgerufen werden könnte. Als ungültig ist auch der Fall fromIndex > toIndex zu werten.
öffentlichen LinkedList Unterliste (int fromIndex, int toIndex) { if (fromIndex <0 | | toIndex> size () | | FromIndex> toIndex) { throw new IndexOutOfBoundsException ( "Ungültiger Index"); } LinkedList list = new LinkedList (); list.head = Unterliste (this.head, fromIndex, toIndex - fromIndex); zurück zur Liste; } Private ListNode Unterliste (ListNode Knoten int Schritte, int size) { if (size == 0) { return null; } if (Schritte == 0) { ListNode subListNode = new ListNode (node.getEntry ()); subListNode.setNext (Unterliste (node.getNext (), 0, size - 1)); zurück subListNode; } zurück Unterliste (node.getNext (), nur wenige Schritte - 1, size); }
Zum Abschluss unserer Betrachtungen über einfach verkettete Listen kommen wir auf den Sortier-Algorithmus „Merge-Sort“ zurück. Nehmen wir an, uns liegt eine umfangreiche unsortierte Liste vom Typ LinkedList vor. Diese soll in eine sortierte Liste vom Typ LinkedList überführt werden. Der Algorithmus „Merge-Sort“ lässt sich für unseren TypLinkedList wie folgt implementieren:
public LinkedList mergeSort() { int length = this.size(); if (length <= 1) { return this; } LinkedList leftSorted = this.subList(0, length / 2).mergeSort(); LinkedList rightSorted = this.subList(length / 2, length).mergeSort(); leftSorted.mergeWith(rightSorted); return leftSorted; } private void mergeWith(LinkedList otherList) { if (otherList.isEmpty()) { return; } if (this.isEmpty()) { this.head = otherList.head; return; } if (otherList.head.getEntry() <= this.head.getEntry()) { int first = otherList.removeFirst(); this.mergeWith(otherList); this.add(first); return; } int first = this.removeFirst(); otherList.mergeWith(this); otherList.add(first); this.head = otherList.head; } private int removeFirst() { if (this.head == null) { throw new IndexOutOfBoundsException("leere Liste"); } int first = this.head.getEntry(); this.head = this.head.getNext(); return first; } Vergleichen Sie die Implementierung mit der Beschreibung des Sortier-Algorithmus „Merge-Sort“ in Kapitel 34.
Eine aufsteigend sortierte Liste für int-Werte können wir ähnlich wie die Klasse LinkedList definieren. Um zu gewährleisten, dass die Liste jederzeit sortiert ist, müssen wir dafür sorgen, dass Einträge von Anfang an gemäß der gewählten Ordnung in die Liste eingefügt werden.
public class SortedList { private ListNode head; public SortedList() { this.head = null; } public void add(int value) { this.head = add(this.head, value); } private ListNode add(ListNode node, int value) { if (node == null) { return new ListNode(value, node); } if (node.getEntry() > value) { return new ListNode(value, node); } node.setNext(add(node.getNext(), value)); return node; }} Die Methode add() fügt jeden neuen Eintrag an der richtigen Stelle in die sortierte Liste ein.
Zeichnen Sie für die sortierte Liste ein Aufrufdiagramm für den Aufruf add(5) im Stil von
Rekursives Einfügen eines Elements
Zeichnen Sie für die sortierte Liste ein Aufrufdiagramm für den Aufruf add(5) im Stil von
Rekursives Einfügen eines Elements
Welche Methoden der Klasse LinkedList könnten wir ohne Nachteil für SortedList identisch übernehmen?
printList(), printReverseList(), size(), sum() (alle Varianten), get(), clear(), subList(). Methoden, die als Parameter Indexpositionen erwarten (get(), subList()), werden allerdings für sortierten Listen selten verwendet.
Was hält uns davon ab, die Klasse LinkedList zu spezialisieren?
Wir hatten in der Klasse LinkedList im vorherigen Abschnitt die Methode add() überladen. Die zweite add()-Methode dient dazu, einen Knoten mit einem neuen Eintrag an einer gewählten Stelle index in eine Liste einzufügen. Für eine sortierte Liste wäre eine solche Funktionalität fatal.
Es wäre sehr schlechter Programmierstil, die Methode entgegen ihrer Zweckbestimmung mit einer unschädlichen Funktionalität zu überschreiben wie etwa
public void add(int index, int value) { this.add(value); // Tun Sie so etwas nie! } Eher wäre zu überlegen, die für beide Klassen nützlichen Methodendefinitionen in eine gemeinsame (ggf. abstrakte) Oberklasse zu verlagern und diese einmal mit LinkedList und einmal mit SortedList zu spezialisieren.
Um den Effizienzvorteil sortierter Listen nutzen zu können, wollen wir nun eine Methode remove()speziell für eine aufsteigend sortierte Liste definieren.
public void remove(int value) { this.head = remove(this.head, value); } private ListNode remove(ListNode node, int value) { // 1 if (node == null) { // 2 return null; // 3 } // 4 if (node.getEntry() > value) { // 5 return node; // 6 } // 7 if (node.getEntry() == value) { // 8 return node.getNext(); // 9 } // 10 node.setNext(remove(node.getNext(), value)); // 11 return node; // 12 } Die Effizienz ergibt sich aus dem zweiten Basisfall (Zeile 5). Sobald bei der rekursiven Ausführung ein Eintrag angetroffen wird, der größer als value ist, steht fest, dass ein Eintrag mit dem Wert value auch in der restlichen Liste nicht mehr gefunden wird.
Welche weiteren Unterschiede bestehen zwischen den remove()-Methoden der Klassen LinkedList und SortedList?
Es bestehen keine weiteren Unterschiede.
Implementieren Sie eine effiziente Methode contains() für SortedList, die prüft, ob in der Liste ein Knoten mit einem bestimmten Wert vorhanden ist.
public boolean contains (int value) { Rückgabe enthält (this.head, value); } private boolean contains (ListNode Knoten, int value) { if (Knoten == null) { return false; } if (node.getEntry ()> value) { return false; } if (node.getEntry () == value) { return true; } Rückgabe enthält (node.getNext (), value); }
Nennen Sie ein Beispiel für eine doppelt Verkettet Liste.
Für einige Abstraktionen ist eine einfach verkettete Liste nicht das optimale Modell. Wenn z. B. eine Warteschlange mit Hilfe einer verketteten Liste implementiert werden soll, die das Einfügen am Ende und das Entfernen am Anfang der Schlange unterstützt, können diese Methoden effizienter implementiert werden, wenn die Elemente der Liste in beide Richtungen, also vorwärts und rückwärts, verkettet sind.
Eine Knoten einer doppelt verketteten Liste kann ähnlich wie der uns bekannte ListNode definiert werden. Für die Einträge wählen wir diesmal den Typ String.
public class DoublyLinkedListNode { private String entry; private DoublyLinkedListNode next; private DoublyLinkedListNode prev;} Eine Warteschlangen stellt typischerweise zwei Methoden enqueue() zum Hinzufügen eines Eintrags und dequeue() zum Entfernen eines eines Eintrags bereit. Sie arbeitet nach dem First In First Out-Prinzip, so dass mit dequeue() immer der Eintrag aus der Warteschlange zurückgegeben wird, der der sich am längsten in der Warteschlage befindet.
Ergänzen Sie den Typ DoublyLinkedListNode um die benötigten Konstruktoren und Methoden. Entwerfen Sie eine KlasseDoublyLinkedList mit den Methoden enqueue() zum Hinzufügen eines String-Eintrags am Ende der Liste und dequeue() zum Entfernen eines String-Eintrags am Anfang der Liste.
public class DoublyLinkedListNode { private String-Eintrag; Private DoublyLinkedListNode next; Private DoublyLinkedListNode prev; öffentlichen DoublyLinkedListNode (String value, DoublyLinkedListNode prevNode) { this.entry = Wert; this.prev = prevNode; this.next = null; } öffentlichen DoublyLinkedListNode getNext () { return next; } public void SetNext (DoublyLinkedListNode nextNode) { this.next = nextNode; }
Bei einigen Problemen reichen lineare Datenstrukturen nicht mehr aus. Wollen wir beispielsweise ein Straßennetz oder die Struktur eines Moleküls nachbilden, so benötigen wir Elemente, die mit mehreren anderen Elementen verbunden sein können. Welche Datenstrukturen werden für solche Problemfälle benötigt?
Für solche Probleme werden häufig Graphen, insbesondere verschiedene Varianten von Bäumen, eingesetzt. Zunächst werden wir Graphen kennen lernen und uns anschließend den Besonderheiten von Bäumen und ihren Implementierungen zuwenden. Zum Abschluss werden wir uns mit der Suche in Graphen beschäftigen.
Was ist ein Graph in Java?
In der Mathematik, genauer in der Graphentheorie, ist ein Graph eine Struktur, die aus einer Menge von Knoten (engl. node) und einer Menge von KantenKanteKante (engl. edge) besteht. Eine Kante verbindet ein Paar von Knoten.
Ein Graph ist ein Tupel:
wobei
-
, die Menge der Knoten und
-
, die Menge der Kanten ist, wobei eine Kante ein Paar von Knoten ist.
Was sind die Besonderheiten von gerichteten Graphen?
Bei einem gerichteten Graphen spricht man von ein- und ausgehende Kanten. Die eingehenden Kanten eines Knotens sind diejenigen Kanten, die als Zielknoten besitzen. Die ausgehenden Kanten besitzen als Startknoten. Die Anzahl der eingehenden Kanten eines Knoten wird als Eingangsgrad bezeichnet, die Anzahl der ausgehenden Kanten als Ausgangsgrad
.
Was in sind die Besonderheiten von ungerichteten Graphen?
Bei ungerichteten Graphen spricht man lediglich vom Grad eines Knotens, der identisch mit der Anzahl allen Kanten ist, die diesen Knoten enthalten.
Welche Eigenschaften haben Konten und Kanten?
Knoten und Kanten können zusätzliche Eigenschaften aufweisen. So können in Knoten zum Beispiel Namen oder Werte und bei Kanten die Länge oder das Gewichte gespeichert werden. Bei einem Straßennetz würde in den Knoten beispielsweise der Name der Stadt und bei Kanten die Entfernung zwischen den beiden Städten, die durch diese Kante verbunden sind, gespeichert werden. Die gespeicherten Daten eines Knotens oder einer Kante werden auch als Label bezeichnet.
Gegeben sei der folgende gerichtete Graph:
Die Knoten sind jeweils durch ihr Label dargestellt. Zeichnen Sie den zugehörigen Graphen.
Ein gerichteter Graph
Bestimmen Sie den Pfad mit der minimalen Entfernung zwischen Dresden und Karlsruhe an Hand der Abbildung.
Der kürzeste Weg von Dresden nach Karlsruhe geht über Erfurt, Würzburg und Stuttgart und hat eine Länge von 580 Kilometern.
Nennen Sie einige Besonderheiten von Graphen.
Ein Pfad, dessen Start- und Zielknoten identisch ist, wird als Zyklus bezeichnet.
Gerichtete Graphen ohne Zyklen werden als gerichtete, azyklische Graphen, (engl. directed acyclic graph, kurz: DAG) bezeichnet.
Wichtige Algorithmen auf Graphen sind zum Beispiel die Suche von Elementen und Pfaden, insbesondere von kürzesten Wegen.
Ein ungerichteter Graph wird als zusammenhängend bezeichnet, wenn es von jedem Knoten einen Pfad zu jedem anderen Knoten gibt. Ein gerichteter Graph wird als stark zusammenhängend bezeichnet, wenn es zwischen allen Knoten einen gerichteten Pfad gibt. Ein gerichteter Graph wird als schwach zusammenhängend
bezeichnet, wenn es zwischen allen Knoten einen ungerichteten Pfad gibt.
Was ist eine Baumdarstellung und wo wird sie höffig eingesetzt?
Im täglichen Leben benutzen wir Baumdarstellungen, um z. B. die Personal- oder Abteilungshierarchie einer Organisation zu beschreiben oder einen Familienstammbaum übersichtlich zu präsentieren. Auch das Dateisystem Ihres Computers ist als Baumstruktur organisiert.
Baum
Ein Baum (engl. tree) ist ein gerichteter, schwach zusammenhängender, azyklischer Graph. Jeder Knoten besitzt einen maximalen Eingangsgrad von 1.
Was sind Bestandteile einer Datenstruktur vom Typ Baum?
Jeder nicht leere Baum hat einen speziellen Knoten, die Wurzel (engl. root). Die Wurzel hat als einziger Knoten einen Eingangsgrad von 0.
Der Startknoten der eingehenden Kante wird als direkter Vorgänger- oder Elternknoten bezeichnet. Alle Knoten, außer der Wurzel, haben genau einen direkten Vorgängerknoten.
Jeder Knoten kann eine endliche Anzahl von direkten Nachfolger- oder Kindknoten besitzen.
Knoten, die keine Nachfolger, also einen Ausgangsgrad von 0, besitzen, werden Blätter (engl. leaf) genannt.
Die Höhe eines Baums ist das Maximum der Knoten, die auf dem Weg von einem Blatt zur Wurzel liegen.
Häufig werden bei der Programmierung Baumdatenstrukturen mit bestimmten Eigenschaften benutzt:
· Ein Binärer Baum ist ein Baum, bei dem jeder Knoten höchstens zwei Nachfolgerknoten besitzt. Binäre Bäume werden bevorzugt als effiziente Suchstrukturen verwendet.
· Bei einem balancierten Baum (engl. balanced tree) B haben alle Unterbäume von B möglichst die gleiche Tiefe, d. h. zwischen der Wurzel und jedem Blatt von B bis auf eine vorgegebene Differenz (meist 1) gleich viele innere Knoten.
· Ein AVL-Baum ist ein binärer Baum, bei dem sich die Höhen der Unterbäume jedes Knotens höchstens um 1 unterscheiden und jeder Unterbaum ein AVL-Baum ist.
Die Abbildung veranschaulicht die Begriffe Wurzel, Knoten und Blatt. In der Informatik wächst ein Baum üblicherweise von oben nach unten, so dass sich seine Wurzel oben und seine Blätter unten befinden. Die Höhe des Baum in der Abbildung ist 4.
Aus dem bisher Gesagten können wir die folgenden Konzepte ableiten:
Die Vorgänger eines Knotens U sind alle Knoten bis zur Wurzel, die direkt oder indirekt Vorgänger von U sind.
Die Nachfolger von U sind seine direkten Nachfolger, die Nachfolger ihrer Nachfolger usw. bis hin zu den Blättern.
Der durch einen Knoten und alle seine Nachfolgerknoten aufgespannte Baum wird als Unterbaum bezeichnet.
Knoten, die den gleichen Vorgängerknoten haben, werden Geschwisterknoten (engl. sibling) genannt.
Angenommen, wir haben ein Buch mit 4 Kapiteln 1, ..., 4, wobei
-
Kapitel 1 aus drei Unterkapiteln 1.1, ..., 1.3 besteht,
-
Kapitel 2 zwei Unterkapitel 2.1 und 2.2 aufweist,
-
Kapitel 3 vier Unterkapitel besitzt und
-
Kapitel 4 drei Unterkapitel hat.
-
Unterkapitel 3.2 bestehe aus zwei Unterkapiteln 3.2.1 und 3.2.2.
Zeichnen Sie einen Baum, der die Struktur des Buches repräsentiert. Die Knoten des Baumes sollen die Nummern der Kapitel und Unterkapitel tragen, und die Geschwisterknoten sollen in aufsteigender Reihenfolge von links nach rechts angeordnet sein.
Kapitelstruktur
Welche vier Durchlaufstrategien gibt es bei Bäumen?
Es wird zwischen vier möglichen Strategien, den Baum systematisch zu durchlaufen, unterschieden:
-
pre-order: wir untersuchen zuerst den betrachteten Knoten, dann den linken und dann den rechten Nachfolger;
-
post-order: wir besuchen zuerst den linken Nachfolger, dann den rechten Nachfolger und schließlich den betrachteten Knoten;
-
in-order: hierbei besuchen wir zuerst den linken Nachfolger, dann den betrachteten Knoten und schließlich den rechten Nachfolger;
-
level-order: zuerst werden alle Knoten auf einer Ebene untersucht, dann alle Nachfolgerknoten jedes Knotens der betrachteten Ebene von links nach rechts.
Die in-order-Strategie kann lediglich bei binären Bäumen verwendet werden. Alle anderen Strategien können auch bei anderen Bäumen angewendet werden.
Die von uns gezeigten Durchlaufstrategien bevorzugen ein links-nach-rechts-Verfahren. Wir hätten ebenso ein rechts-nach-links-Verfahren vorschlagen können, doch der Durchlauf von links nach rechts ist der Standard.
Durchlaufen Sie die beiden in der Abbildung dargestellten Bäume mit der pre-order-, post-order- und level-order-Strategie und geben Sie jeweils an, in welcher Reihenfolge die Knoten besucht werden. Durchlaufen Sie den binären Baum außerdem auch mit Hilfe der in-order-Strategie.
linker Baum:
pre-order: 5, 2, 9, 0, 1, 4, 7, 3, 6, 8
post-order: 9, 0, 4, 1, 2, 7, 6, 8, 3, 5
level-order: 5, 2, 7, 3, 9, 0, 1, 6, 8, 4
rechter Baum:
pre-order: 6, 2, 1, 3, 5, 8, 7, 4, 9
post-order: 3, 5, 1, 2, 7, 9, 4, 8, 6
level-order: 6, 2, 8, 1, 7, 4, 3, 5, 9
in-order: 2, 3, 1, 5, 6, 7, 8, 9, 4
Was sind in Java Binärbäume?
Binäre Bäume sind Datenstrukturen, die in jedem Knoten einen Eintrag speichern und deren Knoten einen maximalen Ausgangsgraf von 2 aufweisen. Ein binärer Baum kann in Java ähnlich wie eine Liste implementiert werden. Bei einem binären Baum muss jeder Knoten jedoch nicht nur einen, sondern zwei Verweise auf seine Nachfolger speichern können.
Definieren Sie die Klasse BinaryTreeNode für unsere Baumknote.
public class BinaryTreeNode { private int entry; private BinaryTreeNode leftChild; private BinaryTreeNode rightChild; public BinaryTreeNode(int e) { this.entry = e; } public BinaryTreeNode(int e, BinaryTreeNode left, BinaryTreeNode right) { this(e); this.leftChild = left; this.rightChild = right; } // Getter und Setter // ...}
Entwerfen Sie die BinaryTree Klasse.
public class BinaryTree { private BinaryTreeNode root; public BinaryTree() { } public BinaryTree(BinaryTreeNode root) { this.root = root; } // Getter und Setter // ...}
