/******************************  TiefenSuche.java  ****************************/

import AlgoTools.IO;

/** Klasse Tiefensuche enthaelt statische Methode tiefenSuche, 
 *  die mit Hilfe eines Kellers eine iterativ organisierte Tiefensuche
 *  auf einem Baum durchfuehrt (= preorder) 
 */

public class TiefenSuche {

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

    Baum b;                               // Hilfsbaum

    Keller k = new VerweisKeller();       // konstruiere einen Keller

    if (!wurzel.empty())                  // lege uebergebenen
      k.push(wurzel);                     // Baum in Keller

    while (!k.empty()) {                  // solange Keller noch Baeume enthaelt

      b = (Baum)k.top();                  // besorge Baum aus Keller
      k.pop();                            // und entferne obersten Eintrag
      
      do {
        IO.print(b.value());              // gib Wert der Baumwurzel aus
        
        if (!b.right().empty())           // falls es rechten Sohn gibt,
          k.push(b.right());              // lege rechten Sohn auf den Keller
        
        b = b.left();                     // gehe zum linken Sohn
        
      } while (!b.empty());               // solange es linken Sohn gibt
    }
  }
}