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

import AlgoTools.IO;

/** Klasse Tiefensuche enthaelt statische Methode tiefenSuche, 
 *  die mit Hilfe eines Kellers eine iterative 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()) k.push(wurzel);  // lege uebergebenen 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
    }
  }
}