Java Standard: Muster Iterator
Erläuterungen
BearbeitenWir wollen hier die Implementierung zweier Sammlungen (einfach verkettete Liste und Binärbaum) und dazu passender Iteratoren besprechen. Zwar soll der Schwerpunkt dabei auf die Betrachtung der Iteratoren gelegt werden, doch gleichwohl ist es nötig auch die Funktionsweise der zugrundeliegenden Sammlungen zu verstehen, da Iteratoren üblicherweise auf die Interna dieser Sammlungen zugreifen müssen - wie im Artikel über das Iterator-Muster erläutert.
Geschrieben sind diese Erläuterungen im Hinblick auf diejenigen unter den Lesern, die bisher über Bäume oder Listen in der Informatik nicht viel mehr wussten, als dass das Java API über Klassen wie TreeMap oder LinkedList verfügt; der über die Funktionsweise dieser Datenstrukturen bereits unterrichtete Leser hingegen kann getrost die einführenden Worte überspringen.
Beginnen werden unsere Betrachtungen aber mit einem genauen Blick auf die beiden Sammlungen.
Verkettete Liste
BearbeitenDie Klasse Liste stellt die Implementierung einer verketteten Liste zur Verfügung. Das Prinzip einer verketteten Liste illustriert die folgende Abbildung:
Die Listenelemente bestehen also aus den eigentlichen Daten (den Nutzdaten) und einem Zeiger auf das nachfolgende Listenelement; die Listenklasse selbst speichert lediglich eine Referenz auf das allererste Element dieser Kette - um Zugriff auf die anderen zu erlangen, muss den Zeigern gefolgt werden, wobei ein Null-Zeiger das Ende der Liste markiert.
Das Einfügen neuer Nutzdaten vollzieht sich in mehreren Schritten:
- Ein neues Listenelement wird erzeugt und die Nutzdaten werden ihm zugewiesen (Zeilen 25 und 40),
- das bisherige erste Listenelement wird zum Nachfolger des neu erstellten Listenelementes gemacht (Zeilen 25 und 41) und
- schließlich wird der
erstes-Zeiger der Listenklasse auf das neu erstellte Listenelement gesetzt (Zeile 25).
Die neuen Daten werden also bei dieser Implementierung vorne in die Liste eingefügt; alle anderen Listenelemente "rutschen" um eine Stelle nach hinten.
Man beachte, dass dies ein eher ungewöhnliches Verhalten darstellt: Natürlicherweise würde man annehmen, dass neue Elemente quasi ans Ende einer Liste "angehängt" werden - dies wird aber keinesfalls durch die Schnittstellendefinition gefordert und der Autor hat sich absichtlich für diese Variante entschieden, demonstriert sie doch auf sehr schöne Weise, wie die Berücksichtigung von Sonderfällen vermieden werden kann: Hätte man sich dafür entschieden, neue Elemente tatsächlich ganz hinten einzufügen, hätte der Fall einer leeren Liste gesondert berücksichtigt werden müssen (ganz zu schweigen von der Notwendigkeit entweder die gesamte Kette zu durchlaufen, um überhaupt an das letzte Element zu gelangen, oder die Listenklasse um eine zusätzliche Referenz auf das letzte Element zu ergänzen).
Binärbaum
BearbeitenDie folgende Abbildung zeigt einen Ausschnitt eines Binärbaumes:
Ein Binärbaum ist wie folgt aufgebaut:
- Er besteht aus sog. Knoten (in der Abbildung als Kreise dargestellt); jeder dieser Knoten speichert ein Nutzdatenobjekt - in der Abbildung ist dies eine Ganzzahl. Wichtig ist dabei nur, dass auf den Nutzdaten eine Ordnung definiert ist (z.B. die übliche "<"-Relation für Zahlenwerte).
- Zusätzlich hat jeder Knoten 0 bis 2 Kindknoten (in der Abbildung sind Kindknoten unterhalb ihres Eltern- oder Vater-Knotens gezeichnet und mit diesem durch Kanten verbunden). Knoten mit wenigstens einem Kind heissen innere Knoten, andernfalls spricht man von Blattknoten.
- Jeder Knoten hat genau einen Elternknoten; die einzige Ausnahme stellt der obersten Knoten dar, die sog. Wurzel des Baumes.
- Die Knotenwerte müssen folgende Bedingungen erfüllen:
- Der Wert des linken Kindknotens ist kleiner als der Wert des Elternknotens
- Der Wert des rechten Kindknotens ist größer als der Wert des Elternknotens oder gleich diesem.
Diese Regeln legen eindeutig fest, ob es sich bei einem gegebenen Gebilde um einen Binärbaum handelt oder nicht. Hier einige Beispiele:
Neue Werte werden wie folgt eingefügt: Durch Vergleichen mit bereits vorhandenen Werten und "Absteigen" (zum linken Kind, falls der einzufügende Wert kleiner ist, andernfalls zum rechten), "hangelt" man sich in dem bestehenden Baum abwärts; nach einigen Schritten wird man auf einen Knoten stoßen, bei dem es auf der entsprechenden Seite nicht mehr weitergeht: Genau an dieser Stelle erzeugt man nun einen neuen Knoten mit dem einzufügenden Wert. Die folgende Abbildung illustriert dieses Vorgehen: Eingefügt werden soll die Zahl 15 in einen bereits bestehenden Baum; der Abstiegspfad ist blau markiert und der schließlich neu erzeugte Knoten rot.
Auf die Darstellung weiterer Operationen, wie Suchen nach oder Löschen von Werten, wollen wir an dieser Stelle verzichten, da sie für den eigentlichen Zweck dieses Artikels, nämlich die Implementierung eines Iterators für Binärbäume zu demonstrieren, nicht erforderlich sind (hier findet sich eine ausführlichere Erläuterung verschiedener Operationen).
Nach dieser allgemein gehaltenen Einführung sei auf einige Besonderheiten in unserer Implementierung hingewiesen:
- Blattknoten enthalten grundsätzlich
nullals Wert. Dies deutet an, dass ein "richtiger" Wert noch nicht gesetzt wurde. - Der Abstieg beim Einfügen eines neuen Wertes erfolgt in den Zeilen 96 und 97; der Abstieg endet, wenn ein Blattknoten erreicht ist (erkennbar eben an jenem
null-Wert). - Neue Werte werden dann immer direkt in die Blattknoten geschrieben und ersetzen das standardmäßige
null(Zeile 99). - Nachdem der Wert eines Blattknotens gesetzt wurde, werden sofort ein rechtes und ein linkes Kind erzeugt; diese erhalten wieder den Standardwert
null(Zeilen 100 und 101).
Ein wenig Nachdenken fördert zu Tage, dass dieses Vorgehen tatsächlich nicht an dem vorgestellten Konzept eines Binärbaumes rüttelt. Der Autor hat sich für diese Implementierung aus demselben Grunde entschieden, der bereits für das Einfügen am Anfang einer Liste geltend gemacht wurde: Der Code der einfuegen()-Methode wird so von allzu vielen Fallunterscheidungen befreit und dadurch wesentlich verkürzt und vereinfacht (folgt man der "reinen Lehre", so muss, nachdem ein Null-Knoten gefunden ist, noch einmal zum Vater zurückgegangen und erneut entschieden werden, auf welcher Seite der neue Knoten einzuhängen ist; außerdem ist der Fall eines noch leeren Baumes wieder gesondert zu berücksichtigen).
Allgemeines zur Iteratorimplementierung
BearbeitenDie Iteratorschnittstelle, die auf der Seite "Iterator-Muster" vorgestellt wurde, soll um zusätzliche Fähigkeiten erweitert werden, was auch eine Änderung des Sammlungs-Interfaces nach sich ziehen wird; hier die Abweichungen im einzelnen:
- Bereits angedeutet wurde die Möglichkeit eine Sammlung auf verschiedene Arten zu durchlaufen. Eine solche Wahl zwischen unterschiedlichen Iteratoren ist hier explizit vorgesehen; dazu wurde das
Sammlungs-Interface dahingehend erweitert, dass die MethodeerzeugeIterator()einen zusätzlichen Parameter erwartet, der angibt, welche Art von Iterator erzeugt werden soll. Verfügbare Iterator-Typen sind als Integer-Konstanten in den jeweiligen Sammlungen definiert (z.B.Liste.VORWAERTS_ITERATORoderBaum. POSTORDER_ITERATOR). Wir haben es hier also mit einem zusätzlichen Fabrikmethoden-Muster zu tun. - Die Iteratoren sollen auch das Zurückbewegen in der Sammlungen unterstützen; dazu sind die Methoden
zurueck()(analog zuweiter()) undgibtVoriges()(Gegenstück zugibtWeiteres()) vorgesehen. Eine generische Möglichkeit diese Operationen zu unterstützen wird am Ende der Besprechung des Listeniterators vorgestellt.
Da insgesamt drei Iteratoren für Binärbäume vorgestellt werden sollen, bietet es sich an, gemeinsame Funktionalität in eine weitere Klasse auszulagern, von der die drei Binärbaumiteratoren dann erben: GenerischerBaumIterator implementiert bereits viele Funktionen vollständig (darunter zurueck() und gibtWeiteres()) und andere zumindest teilweise. Unterklassen müssen dafür Sorge tragen, dass zusätzlich die von GenerischerBaumIterator bereitgestellten Implementierungen aufgerufen werden, wenn sie Methoden überschreiben wollen (z.B. durch super.weiter()).
Generell findet keine Überprüfung auf Gültigkeit statt: Iteratoren für leere Sammlungen zu erzeugen ist ebenso möglich wie ein Aufruf von weiter(), obwohl das Ende einer Sammlung bereits erreicht ist (in beiden Fällen wird vermutlich eine NullPointerException die Folge sein). Der Grund hierfür ist durch den Zweck dieser Implementierung gegeben: Die Funktionsweise von Iteratoren möglichst klar zu demonstrieren - und nicht etwa Teil einer Bibliothek zu werden.
Listeniterator
BearbeitenKommen wir nun zum Hauptanliegen dieses Artikels: der Implementierung von Iteratoren. Für die verkettete Liste folgt die Implementierung der Skizze, die bereits im Artikel zum Iterator-Muster entwickelt wurde:
- Die Iteratorklasse verfügt über einen Zeiger auf das aktuelle Element der zugrundeliegenden Sammlung (
aktuellesin Zeile 46). - Beim Erzeugen eines neuen Iterators (Zeile 51) oder infolge manuellen Zurücksetzens durch Aufruf der
start()-Methode wird dieser Zeiger auf das erste Listenelement gesetzt (Zeile 55). Man beachte, dassListenIteratoreine innere Klasse ist: Dies erlaubt den uneingeschränkten Zugriff auf Felder der KlasseListe - Der Algorithmus zur Bestimmung des nachfolgenden Elementes ist ebenfalls denkbar einfach: Jedes Listenelement enthält ja schließlich bereits einen Zeiger auf seinen Nachfolger, von welchem die
weiter()-Methode in Zeile 65 Gebrauch macht. - Das Ende der Liste ist schließlich erreicht, wenn - wie bei der Beschreibung der Listenimplementierung erläutert - der
naechstes-Zeiger den Wertnullenthält; genau auf diesen Fall testetgibtWeiteres()(Zeile 73).
An der Einfachheit der Implementierung lässt sich erkennen, dass eine verkettete Liste ein sehr "Iteratoren-freundlicher" Sammlungstypus ist.
Wir wollen hier aber einen erweiterten Iterator zur Verfügung stellen, der auch über eine zurueck() Methode verfügt - was ist zu tun? Für diesen Fall böte es sich an, die Listenelemente noch um einen Zeiger auf ihren Vorgänger zu erweitern - die Liste also in eine doppelt Verkettete umzuwandeln. Wenn aber die Möglichkeit die Sammlung selbst zu verändern nicht besteht (dies kommt vor allem dann vor, wenn für eine bereits existierende Sammlung, auf deren Quellcode man keinen Zugriff hat, nachträglich ein Iterator zu entwickeln ist), bleibt noch der Ausweg, welchen wir auch hier beschreiten wollen, den Iterator mit einem zusätzlichen Stack auszustatten, auf den bereits besuchte Listenelemente gelegt werden (Zeile 64): Zurückzugehen heißt dann einfach das oberste Listenelement von dem Stapel wieder herunterzunehmen und zum aktuellen Element zu machen (Zeile 69). Dass es ein voriges Element nicht gibt, verrät schließlich ein leerer Stack (Zeile 77).
Zum Abschluss dieses Abschnitts sei angemerkt, dass der Trick mit dem Stack immer funktioniert, solange wir dem Konzept "aktuelles Element und (nebeneffektfreier!) Nachfolgeralgorithmus" treu bleiben - ganz gleich um was für eine Sammlung es sich handelt. Dementsprechend übernehmen wir ihn auch stillschweigend für den Binärbaumiterator.
Binärbaumiterator
BearbeitenAls etwas "widerspenstiger" wird sich der Binärbaum erweisen - das Grundprinzip soll aber auch hier dasselbe sein: Ein Zeiger auf das aktuelle Sammlungsobjekt (hier eben ein Knoten) und ein Algorithmus, welcher den Nachfolger bestimmt. Um aber einen Nachfolger tatsächlich bestimmen zu können, müssen wir uns zunächst einmal Klarheit darüber verschaffen, in welcher Anordnung wir die eingetragenen Elemente auszugeben gedenken - dies wird, wie gesagt, von der Iteratorschnittstelle nicht festgelegt und wir genießen hier eine gewisse Freiheit.
Wir wollen insgesamt vier Möglichkeiten vorstellen, die Knoten eines Baumes abzulaufen (und immerhin noch drei davon auch implementieren):
- Breitensuche: Die Höhe eines Baumknotens ist definiert als die Anzahl der Schritte bis zur Wurzel; so hat die Wurzel selbst die Höhe 0, die direkten Kinder der Wurzel haben die Höhe 1, deren Kinder die Höhe 2 usw. Bei der Breitensuche ("ebenenweise") werden zuerst alle Knoten der Höhe 0 ausgegeben, dann alle Knoten der Höhe 1, gefolgt von denen der Höhe 2 usw. Ein beispielhafter Durchlauf ist in in der nachfolgenden Grafik ganz links eingezeichnet; die Ausgabe lautet: 10, 4, 20, 1, 7, 17, 19.
- Preorder-Tiefensuche: Bei dieser Variante wird immer zuerst der Elternknoten besucht, dann das linke und zuletzt das rechte Kind. Diese Regel ist rekursiv anzuwenden: Hat beispielsweise ein linker Kindknoten L selbst "Nachkommen", so werden diese als nächste abgearbeitet und erst dann der rechte Geschwisterknoten von L. Dieser rekursive Ansatz führt dazu, dass ein Ast erst vollständig abgearbeitet wird, bevor ein anderer, der auf gleicher Höhe "abzweigt", an die Reihe kommt; ein solches rekursives Vorgehen wird als Tiefensuche bezeichnet - im Gegensatz zur Breitensuche, bei der verschiedene Äste "gleichzeitig" (genauer: abwechselnd) betrachtet werden. Die zweite Abbildung von links illustriert dies; die Reihenfolge der besuchten Knoten lautet: 10, 4, 1, 7, 20, 17, 19.
- Inorder-Tiefensuche: Im Unterschied zur Preorder-Suche wird bei dieser Spielart zuerst der linke Kindknoten, dann der Knoten selbst und zum Schluss der rechte Kindknoten besucht - gleichfalls rekursiv. Ruft man sich die Anordnungsregeln in einem Binärbaum in Erinnerung (linker Wert kleiner, rechter größer), wird auch die Namensgebung klar: Bei der Inorder-Suche werden die Knoten in der Reihenfolge besucht, wie sie durch ihre Zahlenwerte vorgegeben wird (eben: "in order"), und die Ausgabe ist demzufolge sortiert: 1, 4, 7, 10, 17, 19, 20 in der dritten Abbildung von links.
- Postorder-Tiefensuche: Bei der letzten Variante der Tiefensuche lautet die Reihenfolge: Linkes Kind, rechtes Kind, Knoten selbst. Wie in der rechten Abbildung zu sehen ist, lautet die Ausgabe: 1, 7, 4, 19, 17, 20, 10.
 |
 |
 |
 |
| Die blauen Zahlen geben - zusammen mit den Pfeilen - die Reihenfolge an, in der die Knoten besucht werden. | |||
Implementieren wollen wir hier nur die drei Spielarten der Tiefensuche. Doch haben wir bereits alles beisammen, was wir dafür wissen müssen? Die Antwort lautet leider: Nein. Bisher haben wir nämlich lediglich eine rekursive Beschreibung dieser Techniken geliefert - diese könnten wir sehr schnell und leicht implementieren; hier z.B. die Inorder-Tiefensuche:
public void inorder(BaumKnoten bk) {
if (bk.daten == null) return;
inorder(bk.links);
System.out.println(bk.daten);
inorder(bk.rechts);
}
Die anderen beiden Varianten unterschieden sich dann lediglich in der Reihenfolge der letzten drei Anweisungen. Doch erlaubt uns das Konzept eines Iterators eben gerade nicht die Verwendung dieses rekursiven Schemas! Denn wir müssten ja, nachdem das nächste Element gefunden ist, den gesamten bis dahin aufgebauten Stack sichern, um beim nächsten Aufruf von weiter() an genau derselben Stelle im "Turm der rekursiven Aufrufe" weitermachen zu können (tatsächlich konnte man aber auch genau das tun: Nämlich alle bisher besuchten Knoten auf einem Stapel sichern; wir wollen aber hier versuchen ohne diese zusätzliche Datenstruktur auszukommen). Wir müssen uns also noch Kriterien überlegen, wie für einen Knoten dessen Nachfolger bestimmt werden kann - unabhängig davon, wie wir ursprünglich zu diesem Knoten gelangt sind.
Wir stellen diese Kriterien exemplarisch für die Inorder-Tiefensuche vor und geben die entsprechenden Code-Zeilen an. Für die anderen beiden Varianten verzichten wir auf eine explizite Vorstellung und beschränken uns auf den Code. Nun aber zur Inorder-Tiefensuche:
- Erste Feststellung: Egal bei welchem Knoten wir uns befinden, der Nachfolger kann nie ein Knoten unterhalb des linken Kindes sein (denn alle diese Knoten kamen bereits früher dran!).
- Folgerung: Es bleiben zwei Möglichkeiten übrig: Ein Knoten unterhalb des rechten Kindes ist der Nachfolger, oder aber ein höherliegender (letzteres nur, wenn es kein rechtes Kind gibt - man erinnere sich an das rekursive Schema: Kinder vollständig abarbeiten (d.h. mit allen eigenen Kindern, Kindeskindern, ...); erst dann geht es wieder "zurück" nach oben).
- Für den Fall, dass es ein rechtes Kind gibt: Der Nachfolger ist derjenige Knoten unterhalb des rechten Kindes, der am weitesten links liegt. In Zeile 218 wird zuerst zum rechten Kind abgezweigt (
aktueller.rechts) und von diesem ausgehend dann solange wie möglich nach links (linkerAbstieg(aktueller.rechts)). Hat das rechte Kind selbst keinen linken Nachkommen, ist es natürlich selbst der Nachfolger. - Für den Fall, dass es kein rechtes Kind gibt: Nun gilt es im Baum wieder nach oben zu klettern (Zeile 216). Dabei können zwei Fälle auftreten (Zeile 226):
- Wir kommen von links zum Vater: In diesem Fall ist der Vater der nächste Knoten und wir können den Aufstieg beenden.
- Wir kommen von rechts zum Vater: In diesem Fall war der Vaterknoten bereits dran und wir müssen weiter aufsteigen (natürlich gilt es für den nächsten Schritt ebenfalls wieder die zwei Fälle zu unterscheiden).
- Für den Fall, dass es ein rechtes Kind gibt: Der Nachfolger ist derjenige Knoten unterhalb des rechten Kindes, der am weitesten links liegt. In Zeile 218 wird zuerst zum rechten Kind abgezweigt (
 |
 |
| Nachfolger bei Inorder-Tiefensuche; A = aktueller und N = nachfolgender | |
- Noch nicht beantwortet ist bisher die Frage, welcher Knoten der allererste ist, mit welchem es also anzufangen gilt. Dies bereitet uns aber inzwischen keine Schwierigkeiten mehr, denn der kleinste und damit erste Wert steht in dem am weitesten links liegenden Knoten - wir erreichen ihn indem wir bei der Wurzel beginnend fortwährend links abzweigen (Zeile 210).
Dies beschließt im Grunde die Besprechung des Binärbaumiterators. An einige Details sei nochmals erinnert: Gemeinsame Funktionalität (wie das Zurückgeben des aktuellen Elementes, die bereits beim Listeniterator vorgestellte Stack-Verwaltung etc) wurde in eine gemeinsame Oberklasse ausgelagert; aus diesem Grund ist auch das Kriterium für das Erreichen des letzten Knotens bei allen drei Varianten der Tiefensuche ein gemeinsames: Ein Zähler wird bei jedem Aufruf von weiter() inkrementiert (Zeile 161) und mit der Gesamtzahl der im Baum befindlichen Knoten verglichen (Zeile 172). Auch die Stackverwaltung für das Zurückgehen befindet sich in der gemeinsamen Oberklasse.
Code
Bearbeiten 1 import java.util.Stack;
2
3 interface Sammlung {
4 public void einfuegen(Object o);
5 public Iterator erzeugeIterator(int typ);
6 }
7
8
9 interface Iterator {
10 public void start();
11 public Object gibElement();
12 public void weiter();
13 public void zurueck();
14 public boolean gibtWeiteres();
15 public boolean gibtVoriges();
16 }
17
18
19 class Liste implements Sammlung {
20 public static final int VORWAERTS_ITERATOR = 0;
21
22 ListenElement erstes = null;
23
24 public void einfuegen(Object o) {
25 this.erstes = new ListenElement(o, this.erstes); // fuege neues Element am Anfang der Liste ein.
26 }
27
28 public Iterator erzeugeIterator(int typ) {
29 if (typ == VORWAERTS_ITERATOR)
30 return new ListenIterator();
31 else
32 return null;
33 }
34
35 class ListenElement {
36 Object daten;
37 ListenElement naechstes;
38
39 public ListenElement(Object daten, ListenElement naechstes) {
40 this.daten = daten;
41 this.naechstes = naechstes;
42 }
43 }
44
45 class ListenIterator implements Iterator {
46 ListenElement aktuelles = null;
47 Stack<ListenElement> stack;
48
49 ListenIterator() {
50 stack = new Stack<ListenElement>();
51 start();
52 }
53
54 public void start() {
55 aktuelles = erstes; // Wir gehen in diesem Beispiel davon aus, dass die Liste nicht leer ist.
56 stack.empty();
57 }
58
59 public Object gibElement() {
60 return aktuelles.daten;
61 }
62
63 public void weiter() {
64 stack.push(aktuelles);
65 aktuelles = aktuelles.naechstes;
66 }
67
68 public void zurueck() {
69 aktuelles = stack.pop();
70 }
71
72 public boolean gibtWeiteres() {
73 return aktuelles.naechstes != null;
74 }
75
76 public boolean gibtVoriges() {
77 return !stack.isEmpty();
78 }
79 }
80 }
81
82 class Baum implements Sammlung {
83 public static final int PREORDER_ITERATOR = 0;
84 public static final int INORDER_ITERATOR = 1;
85 public static final int POSTORDER_ITERATOR = 2;
86
87 BaumKnoten wurzel = new BaumKnoten(null);
88 int anzElemente = 0;
89
90 public void einfuegen(Object o) {
91 if (!(o instanceof Comparable)) // zum Einfuegen in einen Baum muss eine Ordnung definiert sein
92 return;
93
94 BaumKnoten aktuellerBk = wurzel;
95
96 while (aktuellerBk.daten != null)
97 aktuellerBk = (aktuellerBk.daten.compareTo((Comparable)o) < 0) ? aktuellerBk.links : aktuellerBk.rechts;
98
99 aktuellerBk.daten = (Comparable)o;
100 aktuellerBk.links = new BaumKnoten(aktuellerBk);
101 aktuellerBk.rechts = new BaumKnoten(aktuellerBk);
102
103 anzElemente++;
104 }
105
106 public void anzeigen() {
107 anzeigen(wurzel, "");
108 }
109
110 private void anzeigen(BaumKnoten bk, String prefix) {
111 if (bk.daten == null) {
112 System.out.println(prefix + "-");
113 return;
114 }
115
116 System.out.println(prefix + bk.daten.toString());
117 anzeigen(bk.links, prefix+"| ");
118 anzeigen(bk.rechts, prefix+"| ");
119 }
120
121 public Iterator erzeugeIterator(int typ) {
122 switch (typ) {
123 case PREORDER_ITERATOR : return new PreorderBaumIterator();
124 case INORDER_ITERATOR : return new InorderBaumIterator();
125 case POSTORDER_ITERATOR : return new PostorderBaumIterator();
126 default: return null;
127 }
128 }
129
130 class BaumKnoten {
131 Comparable daten = null;
132 BaumKnoten links = null;
133 BaumKnoten rechts = null;
134 BaumKnoten vater;
135
136 public BaumKnoten(BaumKnoten v) {
137 vater = v;
138 }
139 }
140
141 class GenerischerBaumIterator implements Iterator {
142 BaumKnoten aktueller;
143 int zaehler;
144 Stack<BaumKnoten> stack;
145
146 public GenerischerBaumIterator() {
147 System.out.println("generischer Baumiterator Konstruktor wird ausgefuehrt");
148 stack = new Stack<BaumKnoten>();
149 start();
150 }
151
152 public void start() {
153 stack.empty();
154 zaehler = 0;
155 }
156
157 public Object gibElement() {
158 return aktueller.daten;
159 }
160
161 public void weiter() {
162 zaehler++;
163 stack.push(aktueller);
164 }
165
166 public void zurueck() {
167 zaehler--;
168 aktueller = stack.pop();
169 }
170
171 public boolean gibtWeiteres() {
172 return (zaehler+1 < anzElemente);
173 }
174
175 public boolean gibtVoriges() {
176 return !stack.isEmpty();
177 }
178 }
179
180 class PreorderBaumIterator extends GenerischerBaumIterator {
181 public void start() {
182 super.start();
183 aktueller = wurzel;
184 }
185
186 public void weiter() {
187 super.weiter();
188 if (aktueller.links.daten != null)
189 aktueller = aktueller.links;
190 else
191 aktueller = rechtsAbzweigen(aktueller);
192 }
193
194 // solange nach oben bewegen bis eine "Abzweigung" nach rechts möglich ist
195 private BaumKnoten rechtsAbzweigen(BaumKnoten bk) {
196 if (bk.rechts.daten != null)
197 return bk.rechts;
198 else {
199 while (bk.vater.rechts == bk)
200 bk = bk.vater;
201
202 return rechtsAbzweigen(bk.vater);
203 }
204 }
205 }
206
207 class InorderBaumIterator extends GenerischerBaumIterator {
208 public void start() {
209 super.start();
210 aktueller = linkerAbstieg(wurzel);
211 }
212
213 public void weiter() {
214 super.weiter();
215 if (aktueller.rechts.daten == null)
216 aktueller = rechterAufstieg(aktueller);
217 else
218 aktueller = linkerAbstieg(aktueller.rechts);
219 }
220
221 private BaumKnoten linkerAbstieg(BaumKnoten bk) {
222 return (bk.links.daten == null) ? bk : linkerAbstieg(bk.links);
223 }
224
225 private BaumKnoten rechterAufstieg(BaumKnoten bk) {
226 return (bk.vater.links == bk) ? bk.vater : rechterAufstieg(bk.vater);
227 }
228 }
229
230 class PostorderBaumIterator extends GenerischerBaumIterator {
231 public void start() {
232 super.start();
233 aktueller = abstieg(wurzel);
234 }
235
236 public void weiter() {
237 super.weiter();
238 if (aktueller == aktueller.vater.rechts || aktueller.vater.rechts.daten == null)
239 aktueller = aktueller.vater;
240 else
241 aktueller = abstieg(aktueller.vater.rechts);
242 }
243
244 private BaumKnoten abstieg(BaumKnoten bk) {
245 if (bk.links.daten != null)
246 return abstieg(bk.links);
247 else if (bk.rechts.daten != null)
248 return abstieg(bk.rechts);
249 else
250 return bk;
251 }
252 }
253 }
254
255 public class IteratorTest {
256 public static void main(String[] args) {
257 Sammlung liste = new Liste();
258 Sammlung baum = new Baum();
259
260 bevoelkere(liste);
261 bevoelkere(baum);
262 ((Baum)baum).anzeigen();
263
264 gibAus(liste, Liste.VORWAERTS_ITERATOR);
265 gibAus(baum, Baum.PREORDER_ITERATOR);
266 gibAus(baum, Baum.INORDER_ITERATOR);
267 gibAus(baum, Baum.POSTORDER_ITERATOR);
268 }
269
270 public static void bevoelkere(Sammlung s) {
271 int anzahl = 10;
272 java.util.Random rand = new java.util.Random();
273
274 for (int i = 0; i < anzahl; i++) {
275 Integer ni = new Integer(rand.nextInt() & 0x7fffffff);
276 s.einfuegen(ni);
277 }
278 }
279
280 public static void gibAus(Sammlung s, int typ) {
281 Iterator i = s.erzeugeIterator(typ);
282
283 System.out.println(i.gibElement());
284 while (i.gibtWeiteres()) {
285 i.weiter();
286 System.out.println(i.gibElement());
287 }
288 while (i.gibtVoriges()) {
289 i.zurueck();
290 System.out.println(i.gibElement());
291 }
292 System.out.println();
293 }
294 }
Links
Bearbeiten- The structure Package Source Implementierung von Bäumen und anderen Sammlungstypen mit Iteratoren (bei den Baumiteratoren wurde ein anderer, stackbasierter Ansatz verfolgt).