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

import AlgoTools.IO;

/** Klasse BreitenSuche enthaelt statische Methode breitenSuche, 
 *  die mit Hilfe einer Schlange eine iterative 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()) s.enq(wurzel);   // lege uebergebenen 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
    }
  }
}