/******************************  BreitenSuche.java  ***************************/

import AlgoTools.IO;

/** Klasse BreitenSuche enthaelt statische Methode breitenSuche, 
 *  die mit Hilfe einer Schlange eine iterativ organisierte Breitensuche
 *  auf einem Baum durchfuehrt
 */

public class BreitenSuche {

  public static void breitenSuche(Baum wurzel) {// starte bei wurzel 

    Baum b;                               // Hilfsbaum

    Schlange s = new ArraySchlange(100);  // konstruiere eine Schlange

    if (!wurzel.empty())                  // lege uebergebenen
      s.enq(wurzel);                      // Baum in Schlange 

    while (!s.empty()) {                  // solange Schlange nicht leer

      b = (Baum)s.front();                // besorge Baum aus Schlange 
      s.deq();                            // und entferne vordersten Eintrag
      
      IO.print(b.value());                // gib Wert der Baumwurzel aus

      if (!b.left().empty())              // falls es linken Sohn gibt,
        s.enq(b.left());                  // haenge linken Sohn an Schlange
      if (!b.right().empty())             // falls es rechten Sohn gibt,
        s.enq(b.right());                 // haenge rechten Sohn an Schlange
    }
  }
}