Java Standard: Muster Iterator

Aus Wikibooks

Erläuterungen[Bearbeiten]

Wir 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[Bearbeiten]

Die 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[Bearbeiten]

Die 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 null als 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[Bearbeiten]

Die 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 Methode erzeugeIterator() 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_ITERATOR oder Baum. 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 zu weiter()) und gibtVoriges() (Gegenstück zu gibtWeiteres()) 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[Bearbeiten]

Kommen 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 (aktuelles in 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, dass ListenIterator eine innere Klasse ist: Dies erlaubt den uneingeschränkten Zugriff auf Felder der Klasse Liste
  • 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 Wert null enthält; genau auf diesen Fall testet gibtWeiteres() (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[Bearbeiten]

Als 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.
Breitensuche bei einem Binärbaum
Preorder Durchlauf eines Binärbaumes
Inorder Durchlauf eines Binärbaumes
Postorder Durchlauf eines Binärbaumes
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).
Unterhalb des rechten Kindes
Ein höherliegender Knoten
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).