Objektorientierte Programmierung OOP
KE6 Algorithmus und Datenstrukturen
KE6 Algorithmus und Datenstrukturen
Kartei Details
| Karten | 106 |
|---|---|
| Sprache | Deutsch |
| Kategorie | Informatik |
| Stufe | Universität |
| Erstellt / Aktualisiert | 15.01.2013 / 18.05.2022 |
| Weblink |
https://card2brain.ch/box/objektorientierte_programmierung_oop
|
| Einbinden |
<iframe src="https://card2brain.ch/box/objektorientierte_programmierung_oop/embed" width="780" height="150" scrolling="no" frameborder="0"></iframe>
|
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 // ...}
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.
