Kapitel 10: Abstrakte Datentypen

Bisher haben wir konkrete Klassen modelliert, wie Date, Person oder Student. Dabei haben Sie gelernt, dass wir mithilfe der OOP, im Gegensatz zu Arrays, Strukturen modellieren, die nicht nur aus einem Datentypen bestehen, wie beispielsweise ein Array von ganzen Zahlen. Mithilfe von Klassen können wir Dinge modellieren, die verschiedene Datentypen in einer Struktur zusammenfassen. So haben wir Vorname, Nachname und Geburtsdatum als beschreibende Attribute in der Klasse Person zusammengefasst. Dabei können wir nicht nur auf primitive Datentypen zurückgreifen, wir können sämtliche in Java verfügbaren Datentypen nutzen, um den Gegenstand unseres Interesses zu modellieren. Insbesondere können wir dazu auch Klassen nutzen, die wir selbst implementiert haben, wie Date in Person. Auf diese Weise gelingt es uns, Beziehungen zwischen Objekten auszudrücken.

Nun wenden wir uns der Frage zu, welche Eigenschaften und Operationen eine Datenstruktur haben muss, unabhängig von ihrer internen Implementierung.

Ein abstrakter Datentyp (ADT) ist eine Datenstruktur zusammen mit darauf definierten Operationen.

Java unterstützt den Umgang mit ADTs durch die Bereitstellung von Klassen und Interfaces.

Interfaces enthalten nur Methodenköpfe und Konstanten. Ein Interface stellt eine Schnittstelle dar und legt damit die Funktionalität seiner Methoden fest, ohne diese zu implementieren. Dies geschieht in einer beliebigen Klasse, die dies zuerst in einer implements-Klausel deklariert und die dann eine Implementation aller Methoden des Interface bereitstellen muss.

Die implements-Klausel etabliert damit quasi einen Vertrag zwischen einem Interface und der Klasse, die verspricht, dieses Interface zu implementieren. Der Nutzer einer Klasse darf dann darauf vertrauen, dass die Klasse diesen Vertrag einhält und sich der Methoden, die das Interface deklariert, bedienen.

Verwendet werden kann ein Interface als Typdeklaration auch ohne Kenntnis der konkreten Implementierung.

Wir betrachten die Datenstrukturen Liste (List), Schlange (Queue), Kellerspeicher (Stack) und Baum (Tree).

Diese Datenstrukturen deklarieren jeweils eine Menge von Operationen, die für den Gebrauch der jeweiligen Datenstruktur typisch sind. Diese Operationen deklarieren wir in Form von Interfaces. Verschiedene Klassen stellen dann konkrete Implementierungen dieser Interfaces dar.

Die Auswahl der Datenstrukturen spiegelt grundsätzliche Strukturen wider, die in der Informatik eine zentrale Rolle spielen. Anhand von Beispielanwendungen werden wir uns verschiedene Einsatzzwecke ansehen und implementieren.

List

Definition: Eine Liste (engl. List) ist eine (ggf. leere) Folge von Elementen zusammen mit einem (ggf. undefinierten) aktuellen Element.

Schnittstelle des ADT List

Tabelle 10.1 Listen-Schnittstelle

Die Ankündigung einer Schnittstelle verwendet das Schlüsselwort interface. Das Interface definiert eine generische Liste. Die Liste kann grundsätzlich Elemente beliebigen Datentyps beinhalten. Jedoch soll der Datentyp festgelegt und vom Compiler geprüft werden können. <T> ist der Platzhalter für einen beliebigen Datentypen.

Bezüglich der Methoden, die von einer späteren Implementierung erwartet werden, werden lediglich die Methodenköpfe notiert.

 1package adt;
 2
 3/**
 4 * Interface für den generischen ADT {@code List}.
 5 *
 6 * @param <T> Datentyp
 7 */
 8public interface List<T> {
 9
10    /**
11     * Prüfung, ob Liste leer.
12     *
13     * @return {@code true}, wenn Liste leer, sonst {@code false}
14     */
15    public boolean empty();
16    
17    /**
18     * Prüfung, ob Liste am Ende.
19     *
20     * @return {@code true}, wenn Liste am Ende, sonst {@code false}
21     */
22    public boolean endpos();
23    
24    /**
25     * An den Anfang der Liste rücken.
26     */
27    public void reset();
28    
29    /**
30     * Eine Position in der Liste weiter rücken.
31     */
32    public void forward();
33    
34    /**
35     * Objekt des aktuellen Listenelements liefern.
36     *
37     * @return Objekt
38     */
39    public T content();
40    
41    /**
42     * Objekt vor dem aktuellen Listenelement einfügen.
43     * Eingefügtes Element wird aktuelles Listenelement.
44     *
45     * @param obj Objekt
46     */   
47    public void insert(T obj);
48    
49    /**
50     * Aktuelles Element aus Liste entfernen.
51     */
52    public void delete();
53}

Listing 10.1: adt.List.java

Konzept zur Implementierung einer einfach verketteten Liste

Bei einer einfach verketteten Liste besitzt ein Element eine Nutzlast, einen Wert beliebigen Datentyps, und einen Verweis auf das nächste Listenelement der Liste. Der Verweis des letzten Listenelements ist null.

Die Verwaltungsstruktur der einfach verketteten Liste hat zwei Attribute. Das sind eine Referenz auf den Listenanfang und das Element, welches vor dem aktuellen Element steht. – Es gibt hiervon abweichende Implementierungen.

Der Nutzer einer Liste braucht von diesen internen Implementierungsdetails nichts zu wissen. Wir implementieren den Datentyp des erforderlichen Listenelements daher als innere Klasse von SingleLinkedList. Das ist die Listenimplementierung, die wir hier realisieren wollen.

  1package adt;
  2
  3/**
  4 * {@code SingleLinkedList} implementiert eine einfach verkettete
  5 * generische Liste ({@link List}).
  6 *
  7 * @param <T> Datentyp
  8 */
  9public class SingleLinkedList<T> implements List<T> {
 10
 11    private class Element {
 12        private T content;
 13        private Element next;
 14    }
 15
 16    private final Element start;  // Zeiger auf Listenanfang
 17    private Element pos;          // Zeiger auf aktuellen Listeneintrag
 18
 19    /** Konstruktor für eine leere Liste. */
 20    public SingleLinkedList() {
 21        pos = start = new Element();
 22        start.next = null;
 23    }
 24
 25
 26    /**
 27     * Prüfung, ob Liste leer.
 28     *
 29     * @return {@code true}, wenn Liste leer, sonst {@code false}
 30     */
 31    @Override
 32    public boolean empty() {
 33        return start.next == null;
 34    }
 35
 36
 37    /**
 38     * Prüfung, ob Liste am Ende.
 39     *
 40     * @return {@code true}, wenn Liste am Ende, sonst {@code false}
 41     */
 42    @Override
 43    public boolean endpos() { return pos.next == null; }
 44
 45
 46    /**
 47     * An den Anfang der Liste rücken.
 48     */
 49    @Override
 50    public void reset() { pos = start; }
 51
 52
 53    /**
 54     * Eine Position in der Liste weiter rücken.
 55     * 
 56     * @throws RuntimeException Ende der Liste
 57     */
 58    @Override
 59    public void forward() {
 60        if (endpos())
 61            throw new RuntimeException("Ende der Liste.");
 62        pos = pos.next;
 63    }
 64
 65
 66    /**
 67     * Objekt des aktuellen Listenelements liefern.
 68     * 
 69     * @throws RuntimeException Ende der Liste
 70     * @return Objekt
 71     */
 72    @Override
 73    public T content() {
 74        if (endpos())
 75            throw new RuntimeException("Ende der Liste.");
 76        return pos.next.content;
 77    }
 78
 79
 80    /**
 81     * Objekt vor dem aktuellen Listenelement einfügen.
 82     * Eingefügtes Element wird aktuelles Listenelement.
 83     *
 84     * @param obj Objekt
 85     */   
 86    @Override
 87    public void insert(T obj) {
 88        Element tmp = new Element();
 89        tmp.content = obj;
 90        tmp.next = pos.next;
 91        pos.next = tmp;
 92    }
 93
 94
 95    /**
 96     * Aktuelles Element aus Liste entfernen.
 97     * 
 98     * @throws RuntimeException Ende der Liste
 99     */
100    @Override
101    public void delete() {
102        if (endpos())
103            throw new RuntimeException("Ende der Liste.");
104        pos.next = pos.next.next;
105    }
106
107
108    /**
109     * Ausgabe der Liste als Zeichenkette.
110     * <p>
111     * <i>Anmerkung</i>: einfacher Nachbau von 
112     * {@link java.util.Arrays#toString(Object[])}
113     *
114     * @return Zeichenkettendarstellung der Liste
115     */
116    @Override
117    public String toString() {
118        StringBuilder s = new StringBuilder();
119        Element index = start;
120        s.append('[');
121        while (index.next != null) {
122            s = s.append(index.next.content);
123            s = s.append(", ");
124            index = index.next;
125        }
126        s.deleteCharAt(s.length() - 1);  // letztes Leerzeichen löschen
127        s.deleteCharAt(s.length() - 1);  // letztes Komma löschen
128        s.append(']');
129        return s.toString();
130    }
131}

Listing 10.2: adt.SingleLinkedList.java

Die Liste kann sich selbst darstellen. Das ist keine Standardfunktionalität einer Liste, weshalb sie auch nicht im Listen-Interface aufgeführt ist.

 1import adt.List;
 2import adt.SingleLinkedList;
 3import de.pakad.udemy.StdOut;
 4import oop.Date;
 5import oop.Student;
 6
 7/**
 8 * Testclient für die Klasse {@link adt.SingleLinkedList}.
 9 */
10public class SingleLinkedListTest {
11
12    /**
13     * Hauptprogramm.
14     * 
15     * @param args nicht genutzt
16     */
17    public static void main(String[] args) {
18
19        Student s;                                   // Student
20        List<Student> l = new SingleLinkedList<>();  // Studentenliste
21
22        // neuen Studenten erzeugen und am Listenende anfügen
23        s = new Student("Wilhelm", "Wulf", new Date(13, 10, 2006),
24                        "BWL");
25        l.insert(s); l.forward();
26
27        // neuen Studenten erzeugen und am Listenende anfügen
28        s = new Student("Sabine", "Kittler", new Date(3, 4, 2006),
29                        "BWL");
30        l.insert(s); l.forward();
31
32        // neuen Studenten erzeugen und am Listenende anfügen
33        s = new Student("Wolfgang", "Bauer", new Date(2, 1, 2005),
34                        "Informatik");
35        l.insert(s); l.forward();
36
37        // neuen Studenten erzeugen und am Listenende anfügen
38        s = new Student("Viola", "Sauer", new Date(10, 12, 2005),
39                        "Rechtswissenschaften");
40        l.insert(s);
41        
42        StdOut.println(l);
43
44        // Liste auf Anfang und alle Elemente ausgeben
45        l.reset();
46        while (!l.endpos()) {
47            StdOut.println(l.content());
48            l.forward();
49        }
50
51        // Liste auf Anfang und alle Elemente löschen
52        l.reset();
53        while (!l.empty())
54            l.delete();
55    }
56}

Listing 10.3: SingleLinkedListTest.java

Üblicherweise deklariert man, um eine Schnittstelle zu nutzen, die Schnittstelle als Datentyp, Zeile 20. Instanziiert wird dann eine konkrete Implementierung, hier SingleLinkedList. Beziehen sich Schnittstelle und konkrete Implementierung auf denselben Datentypen, reicht es, diesen bei der Datentypangabe der Variablen anzugeben.

Stack

Definition: Ein Stack (Keller) ist eine (gegebenenfalls leere) Folge von Elementen zusammen mit einem sogenannten (gegebenenfalls leeren) Top-Element.

Ein Stack arbeitet nach den LIFO-Prinzip (Last In First Out).

Schnittstelle des ADT Stack

Tabelle 10.2 Stack-Schnittstelle

Semantik der Stack-Operationen

• Ein neu generierter Stack ist leer.
• Nach einer push()-Operation ist ein Stack nicht leer.
• Nach einer push()-pop()-Operation ist ein Stack unverändert.
• Nach einer push()-Operation mit Element $x$ liefert die top()-Operation $x$.

 1package adt;
 2
 3/**
 4 * Interface für den generischen ADT {@code Stack}.
 5 *
 6 * @param <T> Datentyp
 7 */
 8public interface Stack<T> {
 9
10    /**
11     * Prüfung, ob Stack leer.
12     *
13     * @return {@code true}, wenn Stack leer, sonst {@code false}
14     */
15    boolean empty();
16    
17    /**
18     * Objekt vom Typ {@code T} auf den Stapel legen.
19     *
20     * @param obj Objekt
21     */
22    void push(T obj);
23    
24    /**
25     * Objekt des obersten Stack-Elements liefern.
26     *
27     * @return Objekt
28     */
29    T top();
30    
31    /**
32     * Liefern und entfernen des obersten Stack-Elements.
33     *
34     * @return Objekt
35     */
36    T pop();
37}

Listing 10.4: adt.Stack.java

Konzept zur Implementierung eines Stacks mithilfe von Verweisen

Das Konzept ist dem der einfach verketteten Liste sehr ähnlich. Es ist jedoch insofern einfacher, als das neue Elemente jeweils immer als Top-Element eingefügt werden. Ebenso erfolgt das Lesen und Löschen auch nur beim jeweiligen Top-Element, welches auf dem Stack oben liegt.

Die Verwaltungsstruktur eine Verweis-Stacks kommt mit einem Attribut aus, einem Zeiger auf das Top-Element.

Das Konzept der hier angestrebten Implementierung können wir wie folgt visualisieren:

 1package adt;
 2
 3/**
 4 * {@code ReferenceStack} implementiert einen generischen 
 5 * {@link adt.Stack} mithilfe von Verweisen.
 6 *
 7 * @param <T> Datentyp
 8 */
 9public final class ReferenceStack<T> implements Stack<T> {
10    
11    private class Element {
12        private T content;
13        private Element next;
14    }
15
16    private Element top;  // Zeiger auf Top-Element
17
18    /** Konstruktor für einen leeren Stack. */
19    public ReferenceStack() { 
20        top = null; 
21    }
22
23
24    /**
25     * Prüfung, ob Stack leer.
26     *
27     * @return {@code true}, wenn Stack leer, sonst {@code false}
28     */
29    @Override
30    public boolean empty() { 
31        return top ==  null; 
32    }
33
34
35    /**
36     * Objekt vom Typ {@code T} auf den Stapel legen.
37     *
38     * @param obj Objekt
39     */
40    @Override
41    public void push(T obj) {
42        Element tmp = new Element();
43        tmp.content = obj;
44        tmp.next = top;
45        top = tmp;
46    }
47
48
49    /**
50     * Objekt des obersten Stack-Elements liefern.
51     *
52     * @throws RuntimeException Stack ist leer
53     * @return Objekt
54     */
55    @Override
56    public T top() throws RuntimeException {
57        if (empty())
58            throw new RuntimeException("Stack ist leer.");
59        return top.content;
60    }
61
62
63    /**
64     * Liefern und entfernen des obersten Stack-Elements.
65     *
66     * @throws RuntimeException Stack ist leer
67     * @return Objekt
68     */
69    @Override
70    public T pop() throws RuntimeException {
71        if (empty())
72            throw new RuntimeException("Stack ist leer.");
73        T data = top.content;
74        top = top.next;
75        return data;
76    }
77}

Listing 10.5: adt.ReferenceStack.java

Beispielanwendungen für den Gebrauch eines Stacks

Die Formulierung Stack<Integer> im folgenden Beispiel legt nahe, dass zum Speichern von Werten primitiver Datentypen zunächst das Verpacken der Werte mithilfe der bereits erwähnten Wrapper-Klassen erforderlich ist. So würde durch new Integer(i) ein Integer-Objekt erzeugt mit dem (nicht mehr veränderbaren) Wert i. Diese Form gilt allerdings als veraltet. Manche Entwicklungsumgebungen warnen deshalb. Die moderne Variante ruft den Konstruktor nicht direkt auf. Sie lautet: Integer.valueOf(i). Der Wert dieses Objekts kann über die Methode intValue() ermittelt werden.

Tatsächlich kann aber auf diese Umwege verzichtet werden. Java unterstützt seit geraumer Zeit ein automatisches Boxing und Unboxing, sodass wir primitive Datentypen nicht mehr explizit in deren Wrapper-Klassen ver- und entpacken müssen. – Das nutzen wir hier.

Reversierung einer Zahlenfolge mithilfe eines Stacks:

 1import adt.Stack;
 2import adt.ReferenceStack;
 3import de.pakad.udemy.StdIn;
 4import de.pakad.udemy.StdOut;
 5
 6/**
 7 * Umkehrung einer interaktiv einzugebenden Zahlenfolge
 8 * mithilfe der Klasse {@link adt.ReferenceStack}.
 9 */
10public class Reverse {
11
12    /**
13     * Hauptprogramm.
14     * 
15     * @param args nicht genutzt
16     */
17    public static void main(String[] args) {
18        Stack<Integer> s = new ReferenceStack<>();
19        int[] a = StdIn.readlnInts("Zahlenfolge: ");
20
21        for (int i = 0; i < a.length; i++)
22            s.push(a[i]);
23
24        StdOut.println("Umgekehrte Reihenfolge:");
25        while (!s.empty()) {
26            // anzeigen und entfernen in zwei Schritten
27            StdOut.printf("%d ", s.top());
28            s.pop();
29        }
30        StdOut.println();
31    }
32}

Listing 10.6: Reverse.java

Das pop() den Wert des obersten Stack-Elements liefert, könnten wir top() durch pop() ersetzen und so das Erfragen und Löschen des obersten Stack-Elements in einem Schritt erledigen. Zur Demonstration aller Methoden des Stacks wird das hier jedoch in zwei Schritten vorgenommen.

 1import adt.Stack;
 2import adt.ReferenceStack;
 3import de.pakad.udemy.StdIn;
 4import de.pakad.udemy.StdOut;
 5
 6/**
 7 * Ein einfacher Klammer-Prüfer.
 8 * <p>
 9 * Es wird geprüft, ob runde und/oder eckige Klammern korrekt
10 * paarweise in Programmcodes verwendet werden.
11 * <p>
12 * <strong>Hinweis</strong>: Wenn Klammern in Strings verwendet
13 *                           werden, zeigt {@code Brackets} einen
14 *                           Fehler an, wenn dadurch die paarweise
15 *                           Anordnung der Klammern gestört wird.
16 *                           Einen Fehler im Code muss das jedoch
17 *                           nicht bedeuten.
18 */
19public class Brackets {
20
21    /**
22     * Hauptprogramm. Die Eingabe wird von der Standardeingabe gelesen.
23     * 
24     * @param args nicht genutzt
25     */
26    public static void main(String[] args) {
27        char[] chars;
28        boolean error = false;
29        Stack<Character> s = new ReferenceStack<>();
30
31        // komplette Standardeingabe lesen und als Array von
32        // Zeichen speichern
33        chars = StdIn.readChars();
34        for (char ch : chars) {  // for-each-Schleife
35            switch (ch) {
36                case '(', '[' -> s.push(ch);
37                case ')' -> {
38                    if (!s.empty() && s.top() == '(') s.pop();
39                    else                              error = true;
40                }
41                case ']' -> {
42                    if (!s.empty() && s.top() == '[') s.pop();
43                    else                              error = true;
44                }
45            }
46        }
47        if (!error && s.empty())
48            StdOut.println("Korrekt geklammert.");
49        else
50            StdOut.println("Nicht korrekt geklammert.");
51    }
52}

Listing 10.7: Brackets.java

Das Programm berücksichtigt nicht, dass Klammern im Text oder als konstante Zeichen nicht zwingend korrekt, im Sinne der Java-Syntax, geklammert sein müssen. Auf sich selbst angewendet meldet das Programm daher einen Fehler bezüglich der Klammer-Symbole.

$ java Brackets < HelloWorld.java
Korrekt geklammert.
$ java Brackets < Brackets.java  
Nicht korrekt geklammert.
$ _

Das folgende Programm liest einen arithmetischen Ausdruck in der üblichen Infix-Notation und wandelt ihn in einen Postfix-Ausdruck um. Computer arbeiten intern damit. D. h., erst kommen die Operanden und darauf folgt die Operation, die für die zwei vorausgegangenen Operanden ausgeführt werden soll. Auf diese Weise, die sich auch „Umgekehrt polnische Notation" nennt, kann man sich Klammern grundsätzlich sparen.

 1import adt.ReferenceStack;
 2import adt.Stack;
 3import de.pakad.udemy.StdIn;
 4import de.pakad.udemy.StdOut;
 5
 6/**
 7 * {@code Postfix} konvertiert einen einfachen Infix-Ausdruck nach 
 8 * Postfix.
 9 * <p>
10 * Eine syntaktisch korrekte Eingabe wird vorausgesetzt. Zulässig sind 
11 * die Operatoren +, -, * und /. Als Operanden sind ausschließlich die 
12 * Kleinbuchstaben a-z zulässig. Ein Ausdruck ist lückenlos einzugeben.
13 */
14public class Postfix {
15
16    /**
17     * Hauptprogramm. Der Ausdruck für die Infix2Postfix-Umwandlung
18     * wird interaktiv eingegeben. 
19     * <p>
20     * <strong>Achtung</strong>: Eine Eingabeaufforderung erfolgt nicht!
21     * <p>
22     * Das Programm kann in einer Pipe verwendet werden.                          
23     * 
24     * @param args nicht genutzt
25     */
26    public static void main(String[] args) {
27        Stack<Character> s = new ReferenceStack<>();
28        char[] expression = StdIn.readlnChars();
29
30        for (char ch : expression) {
31            switch (ch) {
32                case '(' -> s.push(ch);         // auf den Stapel
33                // Keller bis vor '(' ausgeben und leeren
34                case ')' -> {
35                    while (s.top() != '(')
36                        StdOut.print(s.pop());
37                    s.pop();                    // '(' entfernen
38                }
39                // Keller bis vor die erste öffnende Klammer ausgeben
40                // und leeren
41                case '+', '-' -> {
42                    while (!s.empty() && s.top() != '(')
43                        StdOut.print(s.pop());
44                    s.push(ch);                 // letztes Zeichen merken
45                }
46                // solange Keller '*' oder '/' enthält, ausgeben
47                // und entfernen
48                case '*', '/' -> {
49                    if (!s.empty() && (
50                        s.top() == '*' || s.top() == '/' )
51                    )
52                        StdOut.print(s.pop());
53                    s.push(ch);                 // letztes Zeichen merken
54                }
55                // falls Operand vorliegt, direkt ausgeben
56                default -> {
57                    if (ch >= 'a' && ch <= 'z')
58                        StdOut.print(ch);
59                }
60            }
61        }
62        // wenn beim Eingabeende noch Zeichen auf dem Stack liegen, 
63        // dann ausgeben
64        while (!s.empty())
65            StdOut.print(s.pop());
66    }
67}

Listing 10.8: Postfix.java

$ java Postfix
(a+b)/(d-c)*e
ab+dc-/e*
$ java Postfix       
((a-b)/(c-d-e/f))+(a+b+c)
ab-cd-ef/-/ab+c++
$ _

Achtung: Fehlerhaft gesetzte Klammern können zu einem Programmabbruch führen.

Queue

Definition: Eine Queue (Schlange) ist eine (gegebenenfalls leere) Folge von Elementen zusammen mit einem sogenannten (gegebenenfalls undefinierten) Front-Element.

Eie Queue arbeitet nach den FIFO-Prinzip (First In First Out).

Schnittstelle des ADT Queue

Tabelle 10.3 Queue-Schnittstelle

 1package adt;
 2
 3/**
 4 * Interface für den generischen ADT {@code Queue}.
 5 *
 6 * @param <T> Datentyp
 7 */
 8public interface Queue<T> {
 9
10    /**
11     * Prüfung, ob Schlange leer.
12     *
13     * @return {@code true}, wenn Schlange leer, sonst {@code false}
14     */
15    boolean empty();
16
17    /**
18     * Anfügen eines Objekts vom Typ {@code T} an das
19     * Ende der Schlange.
20     *
21     * @param obj Wert
22     */
23    void enqueue(T obj);
24
25    /**
26     * Erstes Element aus der Schlange liefern.
27     *
28     * @return Objekt
29     */
30    T front();
31
32    /**
33     * Erstes Element aus Schlange liefern und entfernen.
34     *
35     * @return Objekt
36     */
37    T dequeue();
38}

Listing 10.9: adt.Queue.java

Konzept zur Implementierung einer Queue mithilfe von Verweisen

Das Konzept ist dem der einfach verketteten Liste sehr ähnlich. Es ist jedoch insofern einfacher, als das neue Elemente immer am Ende eingefügt werden. Dann erfolgt das Lesen und Löschen erfolgt jeweils am Beginn der verketteten Elemente, die in die Schlange eingereiht sind.

Die Verwaltungsstruktur einer Verweis-Queue benötigt zwei Attribute, einen Zeiger auf Kopf und einen auf das Ende der Schlange.

Das Konzept der hier angestrebten Implementierung können wir wie folgt visualisieren:

 1package adt;
 2
 3/**
 4 * Eine mittels Referenzen implementierte Warteschlange, die das  Interface
 5 * {@link adt.Queue} implementiert.
 6 *
 7 * @param <T> Datentyp
 8 */
 9public class ReferenceQueue<T> implements Queue<T> {
10
11    private class Element {
12        private T content;
13        private Element prev;
14    }
15
16    private Element head;  // Zeiger auf den Kopf der Schlange
17    private Element tail;  // Zeiger auf das Ende der Schlange
18
19    /**
20     * Konstruktor für eine leere Queue.
21     */
22    public ReferenceQueue() { 
23        head = tail = null; 
24    }
25
26
27    /**
28     * Prüfung, ob Schlange leer.
29     *
30     * @return {@code true}, wenn Schlange leer, sonst {@code false}
31     */
32    @Override
33    public boolean empty() { 
34        return head == null; 
35    }
36
37
38    /**
39     * Anfügen eines Objekts Typ {@code T} an das
40     * Ende der Schlange.
41     *
42     * @param obj Objekt
43     */
44    @Override
45    public void enqueue(T obj) {
46        Element tmp = new Element();
47        tmp.content = obj;
48        if (empty())
49            // wenn Schlange leer, dann Element gleich Kopf-Element
50            head = tmp;
51        else
52            // sonst hinten anfügen
53            tail.prev = tmp;
54        tail = tmp;  // neues Element bildet das Ende der Schlange
55    }
56
57
58    /**
59     * Erstes Element aus der Schlange liefern.
60     *
61     * @throws RuntimeException Schlange ist leer
62     * @return Objekt
63     */
64    @Override
65    public T front() throws RuntimeException {
66        if (empty())
67            throw new RuntimeException("Schlange ist leer.");
68        return head.content;
69    }
70
71
72    /**
73     * Erstes Element aus Schlange liefern und entfernen.
74     *
75     * @throws RuntimeException Schlange ist leer
76     * @return Objekt
77     */
78    @Override
79    public T dequeue() throws RuntimeException {
80        if (empty())
81            throw new RuntimeException("Schlange ist leer.");
82        T data =  head.content;
83        head = head.prev;
84        return data;
85    }
86}

Listing 10.10: adt.ReferenceQueue.java

 1import adt.Queue;
 2import adt.ReferenceQueue;
 3import de.pakad.udemy.StdOut;
 4import oop.Date;
 5import oop.Student;
 6
 7/**
 8 * Testclient für {@link adt.ReferenceQueue}.
 9 */
10public class ReferenceQueueTest {
11    /**
12     * Hauptprogramm.
13     * 
14     * @param args nicht genutzt
15     */
16    public static void main(String[] args) {
17
18        Student s;                                  // Student
19        // Schlange von Studenten
20        Queue<Student> q = new ReferenceQueue<>();  
21
22        // neuen Studenten erzeugen und am Listenende anfügen
23        s = new Student("Wilhelm", "Wulf", new Date(13, 10, 2006),
24                        "BWL");
25        q.enqueue(s);
26
27        // neuen Studenten erzeugen und am Listenende anfügen
28        s = new Student("Sabine", "Kittler", new Date(3, 4, 2006),
29                        "BWL");
30        q.enqueue(s);
31
32        // neuen Studenten erzeugen und am Listenende anfügen
33        s = new Student("Wolfgang", "Bauer", new Date(2, 1, 2005),
34                        "Informatik");
35        q.enqueue(s);
36
37        // neuen Studenten erzeugen und am Listenende anfügen
38        s = new Student("Viola", "Sauer", new Date(10, 12, 2005),
39                        "Rechtswissenschaften");
40        q.enqueue(s);
41        StdOut.println(q.dequeue());
42
43        // restliche Schlange ausgeben und Elemente löschen
44        while (!q.empty()) {
45            StdOut.println(q.dequeue()); // lesen/löschen 
46        }
47    }
48}

Listing 10.11: ReferenceQueueTest.java

Konzept zur Implementierung eines Ringpuffers

Ein Ringpuffer (engl. Ringbuffer) stellt eine spezielle Art von Warteschlange dar, die gewöhnlich nur eine begrenzte Kapazität zur Verfügung stellt, wie beispielsweise der Pufferspeicher unserer Tastatur.

Weil ein RingBuffer eine Queue ist, implementiert er das Interface Queue. Ich verwende hier intern, um die eingereihten Elemente zu speichern ein Array. Das dabei genutzte Prinzip, einen Ring zu modellieren, kennen Sie bereits aus der Implementierung des Abzählreims Josephus.java (Kreisaufstellung der Kinder), Seite .

 1package adt;
 2
 3/**
 4 * Implementierung einer {@link adt.Queue} als {@code RingBuffer}, einem
 5 * Ring-Speicher.
 6 *
 7 * @param <T> Datentyp der zu speichernden Elemente
 8 */
 9public class RingBuffer<T> implements Queue<T> {
10
11    private final Object[] data; // T[] ist in Java nicht erlaubt
12    private final int capacity;
13    private int count;
14    private int head;
15
16    /**
17     * Konstruktor für einen {@code RingBuffer}. Die Kapazität
18     * muss mindestens 10 betragen. Sie ist, nachdem der Puffer
19     * erstellt wurde, fix.
20     *
21     * @throws RuntimeException Kapazität kleine als 10
22     * @param capacity Anzahl der zu speichernden Elemente
23     */
24    public RingBuffer(int capacity) throws RuntimeException {
25        if (capacity < 10)
26            throw new RuntimeException("Mindestkapazität ist 10.");
27        this.capacity = capacity;
28        this.data = new Object[capacity];
29        this.head = 0;
30        this.count = 0;
31    }
32
33
34    /**
35     * Prüfung, ob Puffer leer.
36     *
37     * @return {@code true}, wenn Puffer leer, sonst {@code false}
38     */
39    @Override
40    public boolean empty() { 
41        return count == 0; 
42    }
43
44
45    /**
46     * Anfügen eines Objekts  vom Typ {@code T} an das
47     * Ende des Puffers.
48     *
49     * @throws RuntimeException Puffer ist voll
50     * @param obj Objekt
51     */
52    @Override
53    public void enqueue(T obj) throws RuntimeException {
54        if (count == capacity)
55            throw new IndexOutOfBoundsException("RingBuffer ist voll.");
56        data[(head + count) % capacity] = obj;
57        count++;
58    }
59
60
61    /**
62     * Erstes Element aus dem Puffer liefern.
63     *
64     * @throws RuntimeException Puffer ist leer
65     * @return Objekt
66     */
67    @Override
68    public T front() throws RuntimeException {
69        if (empty())
70            throw new IndexOutOfBoundsException("RingBuffer ist leer.");
71        @SuppressWarnings("unchecked")
72        T value= (T)data[head];
73        return value;
74    }
75
76
77    /**
78     * Erstes Element aus Puffer liefern und entfernen.
79     *
80     * @throws RuntimeException Puffer ist leer
81     * @return Objekt
82     */
83    @Override
84    public T dequeue() throws RuntimeException {
85        if (empty())
86            throw new IndexOutOfBoundsException("RingBuffer ist leer.");
87        @SuppressWarnings("unchecked")
88        T value= (T)data[head];
89        data[head] = null;  // Referenz zu alten Objekten lösen
90        head = (head + 1) % capacity;
91        count--;
92        return value;
93    }
94}  

Listing 10.12: adt.RingBuffer.java

Der Testclient zeigt die Anwendung eines Ringpuffers.

 1import adt.RingBuffer;
 2import adt.Queue;
 3import de.pakad.udemy.StdErr;
 4import de.pakad.udemy.StdOut;
 5
 6/**
 7 * Testclient für die Klasse {@link adt.RingBuffer}.
 8 */
 9public class RingBufferTest {
10
11    /**
12     * Hauptprogramm. Einfaches Treiber-Programm zum Testen der Routinen
13     * der Klasse {@link adt.RingBuffer}.
14     * 
15     * @param args nicht genutzt
16     */
17    public static void main(String[] args) {
18        Queue<Integer> queue = new RingBuffer<>(15);
19
20        for (int i = 0; i < 16; i++)
21            try {
22                queue.enqueue(i);
23            } catch (RuntimeException e) {
24                StdErr.println(e);
25            }
26
27        StdOut.println(queue.front());              // 0
28        StdOut.println(queue.dequeue());            // 0
29        StdOut.println(queue.dequeue());            // 1
30        StdOut.println(queue.dequeue());            // 2
31        queue.enqueue(15);
32        while (!queue.empty())
33            StdOut.printf("%d ", queue.dequeue());  // 3, 4, ..., 15
34        StdOut.println();
35    }
36}

Listing 10.13: RingBufferTest.java

Konzept zur Implementierung einer Prioritätswarteschlange

Eine Prioritätswarteschlange (engl. Priority Queue) ist eine weitere spezielle Art vom Datentyp Queue. Bei Ihr steht nicht die Reihenfolge des Einreihens im Vordergrund. Eine Prioritätswarteschlange liefert als nächstes Element stets das Element mit der höchsten Priorität. Das bedeutet, wir müssen beim Einreihen eines neuen Elements darauf achten, das Element mit der höchsten Priorität am Kopf der Schlange zu positionieren.

Wir unterscheiden Min- und Max-Prioritätswarteschlangen. Bei einer Min-Prioritätswarte­schlange hat das Element mit dem kleinsten Wert die höchste Priorität. Bei Max-Warteschlan­gen ist es genau umgekehrt.

Das soeben Gesagte impliziert die Notwendigkeit, die verschiedenen Elemente ordnen zu können. Dazu müssen sie vergleichbar sein. Unsere Prioritätswarteschlange akzeptiert daher ausschließlich Objekte, die dieser Anforderung direkt oder indirekt (über Vererbung) genügen.

Eine sehr einfache Art und Weise, Objekte vergleichbar zu machen, ist es, das Interface Comparable zu implementieren. Alle Objekte, die dieses Interface implementieren sind vergleichbar.

Als Beispiel betrachten wir eine Klasse PrintJobs. Diese dient ausschließlich zu Demonstrationszwecken. In einer Helpdesk-Anwendung werden Druckaufträge verwaltet. Jeder Druckauftrag erhält eine Priorität und wird in eine Warteschlange eingefügt. Dabei steht 0 für die höchste Priorität.

Das Interface Comparable verlangt danach, eine Methode compareTo() zu implementieren. Ist die eigene Instanz anhand des Vergleichskriteriums kleiner als das Vergleichsobjekt, liefert die Methode einen negativen Rückgabewert. Bei Gleichheit wird 0 zurückgegeben, andernfalls ein positiver Wert.

 1/**  Modellierung eines einfaches Druckauftrags. */
 2public class PrintJob implements Comparable<PrintJob> {
 3
 4    private final String jobId;
 5    private final String user;
 6    private final int pages;
 7    private final int priority;
 8
 9    /**
10     * Konstruktor für einen Druckauftrag.
11     * 
12     * @param priority Priorität
13     * @param jobId Job-ID
14     * @param user Anwendername
15     * @param pages Anzahl Seiten
16     */
17    public PrintJob(int priority, String jobId, String user, int pages) {
18        this.priority = priority;
19        this.jobId = jobId;
20        this.user = user;
21        this.pages = pages;
22    }
23
24
25    /**
26     * Rückgabe der Job-ID.
27     * 
28     * @return Job-ID
29     */
30    public String getJobId() {
31        return jobId;
32    }
33
34
35    /**
36     * Rückgabe der Zeichenkettendarstellung eines Druckauftrags.
37     *
38     * @return Druckauftrag (Zeichenkettendarstellung)
39     */
40    @Override
41    public String toString() {
42        return String.format("%d - (%s) %s: %d Seiten", 
43                             priority, jobId, user, pages );
44    }
45
46
47    /**
48     * Vergleich der Prioritäten zweier Druckaufträge.
49     * 
50     * @return -1 wenn aktueller Auftrag kleiner als Vergleichsauftrag<br>
51     *          0 wenn beide Aufträge gleich sind<br>
52     *          1 sonst
53     */
54    @Override
55    public int compareTo(PrintJob other) {
56        if (priority < other.priority)       return -1;
57        else if (priority == other.priority) return  0;
58        else return                                  1;
59    }
60}

Listing 10.14: PrintJob.java

Die Klasse PrintJob, rudimentär implementiert, implementiert das Interface Comparable in der oben erläuterten Art und Weise. Druckjobs können anhand ihrer jeweiligen Priorität verglichen werden. Wir können Sie in der folgenden Prioritätswarteschlange verwalten.

  1package adt;
  2
  3/**
  4 * {@code ListPriorityQueue} implementiert eine generische
  5 * Prioritätswarteschlange auf Basis einer einfach verketteten
  6 * Liste (@link adt.SingleLinkedList).
  7 * 
  8 * Das Element mit dem niedrigsten Wert hat die höchste Priorität.
  9 * Haben zwei Elemente die gleiche Priorität, dann wird das zuerst
 10 * eingestellte Element auch zuerst zurückgeliefert.
 11 * 
 12 * @param <T> Datentyp
 13 */
 14public class ListPriorityQueue<T extends Comparable<? super T>> 
 15    implements Queue<T> {
 16
 17    private final SingleLinkedList<T> list = new SingleLinkedList<>();
 18    private int size = 0;
 19
 20
 21    /**
 22     * Prüfung, ob Schlange leer.
 23     *
 24     * @return {@code true}, wenn Schlange leer, sonst {@code false}
 25     */
 26    @Override
 27    public boolean empty() { return size == 0; }
 28
 29
 30    /**
 31     * Rückgabe der Größe (Anzahl möglicher Elemente) der Queue.
 32     * 
 33     * @return Größe
 34     */
 35    public int getSize() { return size; }
 36
 37
 38    /**
 39     * Einfügen eines Objekts {@code obj} vom Typ {@code T} in die
 40     * Schlange.
 41     * 
 42     * Hohe Priorität (kleiner Wert) wird vorn eingefügt. Bei gleicher
 43     * Priorität entscheidet die Einfügereihenfolge.
 44     *
 45     * @param obj Objekt
 46     */
 47    @Override
 48    public void enqueue(T obj) {
 49        // Position vor dem ersten Element
 50        list.reset();
 51
 52        // Wir suchen die erste Stelle, wo element "höher priorisiert" 
 53        // ist (kleiner = höhere Priorität): element < aktuelles 
 54        //                                   -> davor einfügen
 55        while (!list.endpos()) {
 56            T current = list.content();
 57            if (obj.compareTo(current) < 0) {
 58                break;
 59            }
 60            list.forward();
 61        }
 62        list.insert(obj);
 63        size++;
 64    }
 65
 66
 67    /**
 68     * Erstes Element aus der Schlange liefern.
 69     *
 70     * @return Objekt
 71     */
 72    @Override
 73    public T front() {
 74        if (empty()) {
 75            throw new IllegalStateException("Queue ist leer.");
 76        }
 77        list.reset();
 78        return list.content();
 79    }
 80
 81
 82    /**
 83     * Erstes Element aus Schlange liefern und entfernen.
 84     *
 85     * @return Objekt
 86     */
 87    @Override
 88    public T dequeue() {
 89        if (empty()) {
 90            throw new IllegalStateException("Queue ist leer.");
 91        }
 92        list.reset();
 93        T first = list.content(); // erstes Element
 94        list.delete();            // erstes Element löschen
 95        size--;
 96        return first;
 97    }
 98
 99
100    /**
101     * Liefert eine Zeichenkettendarstellung der Schlange
102     * mit den darin enthaltenen Elementen.
103     * 
104     * @return Zeichenkettendarstellung
105     */
106    @Override
107    public String toString() { return list.toString(); }
108}

Listing 10.15: adt.ListPriorityQueue.java

Die Beispielanwendung zeigt, wie Aufträge in die Warteschlange eingereiht und in welche Reihenfolge sie wieder ausgegeben werden, geordnet nach ihren jeweiligen Prioritäten. Bei Aufträgen gleicher Priorität wird der zuerst eingereihte Auftrag auch zuerst ausgegeben.

 1import adt.Queue;
 2import de.pakad.udemy.StdOut;
 3import adt.ListPriorityQueue;
 4
 5/**
 6 * Testclient für eine PriorityQueue ({@link adt.ListPriorityQueue})
 7 */
 8public class ListPriorityQueueTest {
 9
10    /**
11     * Hauptprogramm.      
12     *  
13     * @param args nicht genutzt
14     */
15    public static void main(String[] args) {
16        Queue<PrintJob> pq = new ListPriorityQueue<>();
17
18        pq.enqueue(new PrintJob(5, "P01", "Karsten", 250));
19        pq.enqueue(new PrintJob(3, "P02", "Susi", 30));
20        pq.enqueue(new PrintJob(2, "P03", "Ben", 100));
21        pq.enqueue(new PrintJob(5, "P04", "Georg", 99));
22        pq.enqueue(new PrintJob(0, "P06", "Sabine", 75));
23
24        while (!pq.empty()) {
25            StdOut.println(pq.dequeue());
26        }
27    }
28}

Listing 10.16: ListPriorityQueueTest.java

Zusammenfassung Queue

Die verschiedenen Beispiele haben unterschiedlichste Schlangen implementiert. Hierbei haben Sie gelernt, wie mächtig und flexibel das Konzept der Interfaces in Java ist. Alle drei vorgestellen ADTs, ReferenceQueue, RingBuffer und ListPriorityQueue implementieren das Interface Queue. Sie sind daher alle Schlangen. Allerdings implementieren sie jeweils unterschiedliche Anwendungslogiken. Wie sie das realisieren, bleibt dem Anwender verborgen. Dieser verlangt einfach nach einer Queue, spezifiziert deren Typ je nach Anwendungsfall und kann sie dann auf standardisierte Art und Weise nutzen. Diese Standardisierung, die wir auch bezüglich Comparable genutzt haben, stellt einen nicht zu unterschätzenden Gewinn für unsere eigenen Programm- und Datentypentwürfe dar.

Tree

Definition: Ein Binary Tree (binärer Baum) ist entweder leer oder besteht aus einem Knoten, dem ein Datenelement und zwei binäre Bäume zugeordnet sind.

Tabelle 10.4 Tree-Schnittstelle

 1package adt;
 2
 3/**
 4 * Interface für den generischen ADT {@code Tree}.
 5 *
 6 * @param <T> Datentyp
 7 */
 8public interface Tree<T> {
 9
10    /**
11     * Prüfung, ob der Baum leer ist.
12     *
13     * @return {@code true}, wenn Baum leer, sonst {@code false}
14     */
15    boolean empty();
16    /**
17     * Rückgabe des linken Teilbaums.
18     *
19     * @return linker Teilbaum
20     */
21    Tree<T> left();
22    /**
23     * Rückgabe des rechten Teilbaums.
24     *
25     * @return rechter Teilbaum
26     */
27    Tree<T> right();
28    /**
29     * Rückgabe des in der Wurzel gespeicherten Datenobjekts.
30     *
31     * @return Wert
32     */
33    T content();
34}

Listing 10.17: adt.Tree.java

Achtung: Verdeutlichen Sie sich, dass die Operationen left() und right() jeweils wieder einen Baum liefern, nicht nur einen einzelnen Knoten.

Konzept zur Implementierung eines binären Baumes mithilfe von Verweisen

Ein Baum besteht, mithilfe von Verweisen implementiert, aus Knotenelementen, die neben einer Datenlast je zwei Verweise besitzen, einen Verweis auf den linken Sohn und einen Verweis auf den rechten Sohn. Diese können auch leer sein. Zur Konstruktion eines Baumes dienen verschiedene Konstruktoren.

  1package adt;
  2
  3import java.util.NoSuchElementException;
  4
  5/**
  6 * Referenz-basierter binärer Baum.
  7 *
  8 * <p>Hinweis: Der Konstruktor {@code ReferenceTree(l, content, r)} 
  9 * verlinkt die Teilbäume (keine Kopie). Dadurch können mehrere 
 10 * Baumobjekte dieselben Knoten teilen.</p>
 11 * 
 12 * <p>Teilbäume werden verlinkt. Das spart Kopien, bedeutet aber: 
 13 * mehrere Tree-Objekte können dieselben Knoten referenzieren. 
 14 * Mutierende Operationen müssen daher sorgfältig implementiert 
 15 * werden.</p>
 16 *
 17 * @param <T> Datentyp der Elemente
 18 */
 19public class ReferenceTree<T> implements Tree<T> {
 20
 21    /**
 22     * Baumknoten (gekapselt, für Nachfolger zugreifbar)
 23     */
 24    protected static class Node<T> {
 25        /** Knoteninhalt */
 26        protected T content;
 27        /** linker Teilbaum oder {@code null} */
 28        protected Node<T> left;
 29        /** rechter Teilbaum oder {@code null} */
 30        protected Node<T>right;
 31
 32        /** Konstruktor für einen neuen Knoten.
 33         * 
 34         * @param content Inhalt
 35         */
 36        protected Node(T content) {
 37            this.content = content;
 38        }
 39    }
 40
 41    /** Wurzelknoten */
 42    protected Node<T> root;
 43
 44    /**
 45     * Erzeugt einen leeren Baum.
 46     */
 47    public ReferenceTree() {
 48        root = null;
 49    }
 50
 51
 52    /**
 53     * Erzeugt einen Baum mit genau einem Element als Wurzel.
 54     *
 55     * @param obj Wert (nicht {@code null})
 56     */
 57    public ReferenceTree(T obj) {
 58        if (obj == null) {
 59            throw new IllegalArgumentException("Kein Wert angegeben");
 60        }
 61        root = new Node<>(obj);
 62    }
 63
 64
 65    /**
 66     * Erzeugt einen Baum aus linkem Teilbaum, Wurzelinhalt und 
 67     * rechtem Teilbaum. Teilbäume werden verlinkt (keine Kopie).
 68     *
 69     * @param l linker Teilbaum (oder {@code null})
 70     * @param content Wurzelinhalt (nicht {@code null})
 71     * @param r rechter Teilbaum (oder {@code null})
 72     */
 73    public ReferenceTree(ReferenceTree<T> l, 
 74                         T content, 
 75                         ReferenceTree<T> r) {
 76        if (content == null) {
 77            throw new IllegalArgumentException("Kein Wert angegeben");
 78        }
 79        root = new Node<T>(content);
 80        if (l != null)
 81            root.left = l.root;
 82        if (r != null)
 83         root.right = r.root;
 84    }
 85
 86
 87    /**
 88     * Interner Konstruktor, um eine Teilbaum-View aus einem 
 89     * Knoten zu erzeugen.
 90     *
 91     * @param node Knoten
 92     */
 93    private ReferenceTree(Node<T> node) {
 94        this.root = node;
 95    }
 96
 97    /* ------------------------------------------------------------
 98     * ADT-Methoden (öffentlich, wie im Interface Tree<T>)
 99     * ------------------------------------------------------------ */
100
101    /**
102     * Prüfung, ob der Baum leer ist.
103     *
104     * @return {@code true}, wenn Baum leer, sonst {@code false}
105     */
106    @Override
107    public boolean empty() { 
108        return root == null; 
109    }
110
111
112    /**
113     * Rückgabe des linken Teilbaums.
114     *
115     * @throws RuntimeException  wenn Baum leer
116     * @return linker Teilbaum
117     */
118    @Override
119    public Tree<T> left() {
120        if (empty()) 
121            throw new RuntimeException("Baum ist leer.");
122        return new ReferenceTree<>(root.left);
123    }
124
125
126    /**
127     * Rückgabe des rechten Teilbaums.
128     *
129     * @throws RuntimeException  wenn Baum leer
130     * @return rechter Teilbaum
131     */
132    @Override
133    public Tree<T> right() {
134        if (empty()) 
135            throw new RuntimeException("Baum ist leer.");
136        return new ReferenceTree<>(root.right);
137    }
138
139
140    /**
141     * Rückgabe des in der Wurzel gespeicherten Datenobjekts.
142     *
143     * @return Objet
144     */
145    @Override
146    public T content() throws NoSuchElementException {
147        if (empty()) 
148            throw new NoSuchElementException("Baum ist leer.");
149        return root.content;
150    }
151}

Listing 10.18: adt.ReferenceTree.java

Traversierungen

Zur Ausgabe eines Baumes, müssen wir die einzelnen Knoten abwandern können. Das nennen wir Traversierung. Eine Traversierung eines binären Baumes besteht aus dem systematischen Besuchen aller Knoten in einer bestimmten Reihenfolge.

• Preorder: Vater, linker Sohn, rechter Sohn
• Inorder: linker Sohn, Vater, rechter Sohn
• Postorder: linker Sohn, rechter Sohn, Vater

D. h., dass für jeden besuchten Knoten stets in derselben Art weiter traversiert wird, die Traversierungen also rekursiv definiert sind.

Für den Baum in der obigen Abbildung ergeben sich dann die folgenden Traversierungen:

Preorder:   / + F * A  B - X Y
Inorder:    F + A * B  / X - Y
Postorder:  F A B * +  X Y - /

Bevor wir zum Test einen Baum konstruieren, benötigen wir eine Möglichkeit, die Baumknoten abzuschreiten und auszugeben. Wir implementieren einfache Traversen.

Wir brauchen nur die Definition der einzelnen Traversierungen 1:1 in Code umsetzen. Ein leerer Baum stellt die jeweilige Rekursionsbremse, den Basisfall, dar.

 1package adt;
 2
 3import de.pakad.udemy.StdOut;
 4
 5/** Einfache Traversierungen für binäre Bäume. */
 6public class Traverse {
 7
 8    /**
 9     * Preorder-Baumtraverse.
10     *
11     * @param tree Baum
12     * @param <T> Datentyp der Elemente im Baum
13     */
14    public static <T> void preorder(Tree<T> tree) {
15        if (!tree.empty()) {
16            StdOut.print(tree.content());
17            preorder(tree.left());
18            preorder(tree.right());
19        }
20    }
21
22
23    /**
24     * Inorder-Baumtraverse.
25     *
26     * @param tree Baum
27     * @param <T> Datentyp der Elemente im Baum
28     */
29    public static <T> void inorder(Tree<T> tree) {
30        if (!tree.empty()) {
31            inorder(tree.left());
32            StdOut.print(tree.content());
33            inorder(tree.right());
34        }
35    }
36
37
38    /**
39     * Inorder-Baumtraverse mit Klammern.
40     *
41     * @param tree Baum
42     * @param <T> Datentyp der Elemente im Baum
43     */
44    public static <T> void bracketinorder(Tree<T> tree) {
45        if (!tree.empty()) {
46            if (!tree.left().empty()) IO.print('(');
47            bracketinorder(tree.left());
48            StdOut.print(tree.content());
49            bracketinorder(tree.right());
50            if (!tree.right().empty()) IO.print(')');
51        }
52    }
53
54
55    /**
56     * Postorder-Baumtraverse mit Klammern.
57     *
58     * @param tree Baum
59     * @param <T> Datentyp der Elemente im Baum
60     */
61    public static <T> void postorder(Tree<T> tree) {
62        if (!tree.empty()) {
63            postorder(tree.left());
64            postorder(tree.right());
65            StdOut.print(tree.content());
66        }
67    }
68}

Listing 10.19: adt.Traverse.java

Das Programm TraverseTest.Java konstruiert mithilfe der Konstruktoren den Baum aus Abbildung 1.4.

 1import adt.ReferenceTree;
 2import adt.Traverse;
 3import de.pakad.udemy.StdOut;
 4
 5/**
 6 * Testclient für verschiedene einfache Traversen ({@link adt.Traverse}).
 7 */
 8public class TraverseTest {
 9
10    /**
11     * Aufbau eines Beispielbaumes.
12     * 
13     * @return Baum
14     */
15    private static ReferenceTree<Character> buildTree() {
16        ReferenceTree<Character> a = new ReferenceTree<>('A');
17        ReferenceTree<Character> b = new ReferenceTree<>('B');
18        ReferenceTree<Character> m = new ReferenceTree<>(a, '*', b);
19        ReferenceTree<Character> f = new ReferenceTree<>('F');
20        ReferenceTree<Character> p = new ReferenceTree<>(f, '+', m);
21        ReferenceTree<Character> x = new ReferenceTree<>('X');
22        ReferenceTree<Character> y = new ReferenceTree<>('Y');
23        ReferenceTree<Character> s = new ReferenceTree<>(x, '-', y);
24        
25        return new ReferenceTree<>(p, '/', s);
26    }
27
28
29    /**
30     * Aufbau eines binären Baums (fixer arithmetischer Ausdruck).
31     * 
32     * @param args nicht genutzt
33     */
34    public static void main(String[] args) {
35
36        ReferenceTree<Character> tree = buildTree();
37
38        StdOut.print("Preorder.......: ");
39        Traverse.preorder(tree); StdOut.println();
40        StdOut.print("Inorder........: ");
41        Traverse.inorder(tree); StdOut.println();
42        StdOut.print("BracketInorder.: ");
43        Traverse.bracketinorder(tree); StdOut.println();
44        StdOut.print("Postorder......: ");
45        Traverse.postorder(tree); StdOut.println();
46    }
47}

Listing 10.20: TraverseTest.java

$ java TraverseTest
Preorder.......: /+F*AB-XY
Inorder........: F+A*B/X-Y
BracketInorder.: ((F+(A*B))/(X-Y))
Postorder......: FAB*+XY-/
$ _

Tiefensuche

Der Vorteil der Rekursion ist es, als Programmierer kein eigenes Protokoll darüber führen zu müssen, welche Knoten des zu traversierenden Baums noch nicht vollständig behandelt worden sind. Diese Aufgabe übernimmt, ganz automatisch, der Aufrufstapel der noch nicht vollständig abgearbeiteten rekursiven Methodenaufrufe.

Mit der Tiefen- und Breitensuche (nächster Unterabschnitt, Seite ), stelle ich Ihnen zwei Traversierungsstrategien vor, die iterativ vorgehen. Die Protokollierung über die Schritte, die jeweils noch zu tun sind, führen wir selbst Protokoll. Dazu nutzen wir die bereits besprochenen Datentypen, Stack und Queue.

Die Tiefensuche (DFS = Depth-First Search) besucht in einer Preorder-Reihenfolge. Zuerst wird der Vater eines (Teil-)Baums verarbeitet, dann der linke und am Ende der jeweils rechte Sohn.

Der Vater kann problemlos verarbeitet werden. Wir haben uns aber zu merken, dass es eventuell einen rechten Sohn gibt, bevor wir zur Verarbeitung eines potenziell linken Sohns schreiten. Andernfalls kommen wir an den nicht mehr heran. Die dafür geeignete Datenstruktur, das Protokoll zu führen, ist der Stack.

 1package adt;
 2
 3import de.pakad.udemy.StdOut;
 4
 5/** Tiefensuche auf binärem Bäumen */
 6public final class DFS {
 7    /**
 8     * Tiefensuche auf Baum {@code tree}.
 9     *
10     * @param tree Baum
11     * @param <T> Datentyp der Elemente im Baum
12     */
13    public static <T> void dfs(Tree<T> tree) {
14        Tree<T> t;
15        Stack<Tree<T>> stack = new ReferenceStack<>();
16
17        // initial wird der gesamte Baum auf den Stack gelegt
18        if (!tree.empty())
19            stack.push(tree);
20
21        // jetzt beginnt die Traversierung
22        while (!stack.empty()) {           // solange Keller nicht leer
23            t = stack.pop();               // hole Baum vom Keller
24            do {
25                StdOut.print(t.content()); // Wurzel ausgeben
26                if (!t.right().empty())    // wenn rechter Sohn existiert
27                    stack.push(t.right()); // rechten Sohn merken
28                t = t.left();              // gehe zum linken Sohn
29            } while (!t.empty());          // solange es linken Sohn gibt
30        }
31    }
32}

Listing 10.21: adt.DFS.java

Breitensuche

Die Breitensuche (BFS = Breadth-First Search) traversiert einen Baum, von der Wurzel ausgehend, Ebene für Ebene. Dabei wird in jeder Ebene von links nach rechts vorgegangen. Die geeignete Datenstruktur, das erforderliche Protokoll zu verwalten, ist die Queue.

 1package adt;
 2
 3import de.pakad.udemy.StdOut;
 4
 5/** Breitensuche auf binärem Bäumen */
 6public final class BFS {
 7    /**
 8     * Breitensuche auf Baum {@code tree}.
 9     *
10     * @param tree Baum
11     * @param <T> Datentyp der Elemente im Baum
12     */
13    public static <T> void bfs(Tree<T> tree) {
14        Tree<T> t;
15        Queue<Tree<T>> queue = new ReferenceQueue<>();
16
17        // initial wird der gesamte Baum in die Schlange eingefügt
18        if (!tree.empty())
19            queue.enqueue(tree);
20
21        // jetzt beginnt die Traversierung
22        while (!queue.empty()) {           // solange Schlange nicht leer
23            t = queue.dequeue();           // hole Baum aus Schlange
24            StdOut.print(t.content());     // Wurzel ausgeben
25            if (!t.left().empty())         // wenn linker Sohn existiert
26                queue.enqueue(t.left());   // linken Sohn merken
27            if (!t.right().empty())        // wenn linker Sohn existiert
28                queue.enqueue(t.right());  // linken Sohn merken
29        }
30    }
31}

Listing 10.22: adt.BFS.java

 1import adt.DFS;
 2import adt.BFS;
 3import adt.ReferenceTree;
 4import de.pakad.udemy.StdOut;
 5/**
 6 * Testclient für die iterativen Traversen {@link adt.DFS}
 7 * und {@link adt.BFS}
 8 */
 9public class DFSBFSTest {
10    /**
11     * Aufbau eines Beispielbaumes.
12     * 
13     * @return Baum
14     */
15    private static ReferenceTree<Character> buildTree() {
16        ReferenceTree<Character> a = new ReferenceTree<>('A');
17        ReferenceTree<Character> b = new ReferenceTree<>('B');
18        ReferenceTree<Character> m = new ReferenceTree<>(a, '*', b);
19        ReferenceTree<Character> f = new ReferenceTree<>('F');
20        ReferenceTree<Character> p = new ReferenceTree<>(f, '+', m);
21        ReferenceTree<Character> x = new ReferenceTree<>('X');
22        ReferenceTree<Character> y = new ReferenceTree<>('Y');
23        ReferenceTree<Character> s = new ReferenceTree<>(x, '-', y);
24        return new ReferenceTree<>(p, '/', s);
25    }
26
27    /**
28     * Treiber füllt den Baum und traversiert ihn.
29     * 
30     * @param args nicht genutzt
31     */
32    public static void main(String[] args) {
33        ReferenceTree<Character> tree = buildTree();
34
35        StdOut.print("Tiefensuche....: ");
36        DFS.dfs(tree); StdOut.println();
37        StdOut.print("Breitensuche...: ");
38        BFS.bfs(tree); StdOut.println();
39    }
40}

Listing 10.23: DFSBFSTest.java

Aufbau eines Postfix-Baums

Das Programm BuildPostfixTree.java liest interaktiv einen Postfix-Ausdruck ein und generiert daraus einen binären Baum. Dieser kann dann mittels entsprechender Traversen ausgeben werden, zum Beispiel als Infix-Ausdruck.

 1import adt.*;
 2import de.pakad.udemy.StdIn;
 3import de.pakad.udemy.StdOut;
 4
 5/**
 6 * Interaktives Einlesen eines Postfix-Ausdrucks, Generierung
 7 * eines binären Baums und dessen Traversierung.
 8 */
 9public class BuildPostfixTree {
10
11    /**
12     * Aufbau eines Postfix-Baums. 
13     * 
14     * @param Postfix-Ausdruck
15     * @return Baum
16     */
17    public static ReferenceTree<Character> buildTree(char[] expression) {
18        ReferenceTree<Character> t, l, r;
19        Stack<ReferenceTree<Character>> s = new ReferenceStack<>();
20
21        for (int i=0; i<expression.length; i++) {
22            char ch = expression[i];
23            if (ch!='+' && ch!='-' && ch!='*' && ch!='/')
24                // ch ist Operand -> Blatt erzeugen
25                t = new ReferenceTree<>(ch);
26            else {
27                // ch ist Operator -> Baum erzeugen
28                r = s.pop();  // rechter Sohn
29                l = s.pop();  // linker Sohn
30                t = new ReferenceTree<>(l, ch, r);
31            }
32            s.push(t);        // Baum auf Stapel ablegen
33        }
34        return s.top();       // Ergebnisbaum liefern
35    }
36
37
38    /**
39     * Treiber liest einen Postfix-Ausdruck ein und
40     * generiert einen entsprechenden Baum.
41     * 
42     * @param args nicht genutzt
43     */
44    public static void main(String[] args) {
45        char[] ex = StdIn.readlnChars("Postfix-Ausdruck: ");
46        Tree<Character> tree = buildTree(ex);
47        StdOut.print("Inorder.........: ");
48        Traverse.inorder(tree); StdOut.println();
49    }
50}

Listing 10.24: BuildPostfixTree.java

Beispielsitzung:

$ java BuildPostfixTree 
Postfix-Ausdruck: FAB*+XY-/
Inorder.........: F+A*B/X-Y
$ _

Enumerationen

Mit den bisher besprochenen Traversierungen haben wir uns ein Problem eingehandelt. Wir vermengen in Ihnen die Traversierung mit der Verarbeitung der Daten. Die bestand lediglich aus einer Ausgabe der jeweiligen Daten eines Baumknotens. Wollen wir jedoch etwas anderes tun, müssen wir die Traversen neu implementieren. – Gesucht ist also ein Verfahren, welches Traversierung und Datenverarbeitung trennt.

Eine Enumeration ist ein Objekt, das den sequentiellen Zugriff auf die Elemente einer Sammlung erlaubt, ohne deren interne Struktur offenzulegen.

Sie realisiert damit das Iterator-Prinzip:

Ein Objekt stellt schrittweise seine Elemente bereit, ohne preiszugeben, wie diese intern gespeichert sind.

Beachte: Während einer Traversierung sollte die Datenstruktur nicht verändert werden.