Objektorientierte Programmierung OOP

Der kürzeste Weg von Dresden nach Karlsruhe geht über Erfurt, Würzburg und Stuttgart und hat eine Länge von 580 Kilometern.

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.

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.

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.

Kapitelstruktur

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.

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

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    // ...}

public class BinaryTree {    private BinaryTreeNode root;        public BinaryTree() {    }        public BinaryTree(BinaryTreeNode root) {        this.root = root;    }        // Getter und Setter    // ...}

    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);

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.

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());    }}

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 () + "");    }    }

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);    }}

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);    }}

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.

Suchbaum

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.

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.

    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;    }

    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;    }

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;}

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.

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;    }

    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;    }

Wenn die Datenelemente gemäß einer Ordnungsrelation sortiert werden. Der Suchalgorithmus kann diese Eigenschaft nutzen, um ein bestimmtes Element in der sortierten Menge zu finden.

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;                }            }        }}

Es werden 18 Vergleiche und 12 Vertauschungen benötigt.

   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;                }            }        }    }

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;            }        }    }

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;            }        }    }

Es werden 28 Vergleiche und 6 Vertauschungen benötigt.

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;            }        }    }

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.

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.

  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);    }

In jedem Schritt wird n um eins verringert. Somit nähert sich n immer weiter an den Basisfall 0 an.

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);    }