class Knoten  // ---------------------------------------
{  int inhalt;
   Knoten links, rechts;
   Knoten (int wert)
   { this.inhalt = wert;  this.links = null;  this.rechts = null; }
} // class Knoten

class BinaerBaum // ------------------------------------
{ Knoten wurzel = null;

  void fuegeEin(Knoten ast, int wert)
  { if (wert < ast.inhalt)
         { // links einfuegen
           if (ast.links == null)
                ast.links = new Knoten(wert);
           else fuegeEin(ast.links, wert);
         }
    else { // rechts einfuegen
           if (ast.rechts == null)
                ast.rechts = new Knoten(wert);
           else fuegeEin(ast.rechts, wert);
         }
  } // fuegeEin

  void fuegeEin(int wert)
  { if (wurzel == null)
         wurzel = new Knoten(wert);
    else fuegeEin(wurzel, wert);
  } // FuegeEin

  void laufeDurch(Knoten ast)
  { if (ast != null)
         { laufeDurch (ast.links);
           Out.print(ast.inhalt); Out.println();
           laufeDurch (ast.rechts);
         }
  } // laufeDurch

  void laufeDurch()
  { laufeDurch(wurzel);
  } // laufeDurch

  boolean gefunden(Knoten ast, int zahl)
  { if (ast == null) return false;
    else if (zahl == ast.inhalt) return true;
    else if (zahl < ast.inhalt) return gefunden(ast.links, zahl);
    else return gefunden(ast.rechts, zahl);
  } // gefunden

  boolean gefunden(int zahl)
  { return gefunden(wurzel, zahl);
  } // gefunden
} // class BinaerBaum

class BinBaumBsp1 // ----------------------------------
{ static BinaerBaum baum;

  public static void main(String[] arg)
  { int zahl = 0;
    String muell;
    baum = new BinaerBaum();
    Out.print("Bitte Zahlen eingeben. Ende mit -1."); Out.println();
    while (zahl != -1)
    { Out.print("Bitte Zahl eingeben: ");
      zahl = In.readInt();   muell = In.readLine();
      if (zahl != -1) baum.fuegeEin(zahl);
    } // while
    baum.laufeDurch();
    Out.println();
    Out.print("Nach welcher Zahl soll gesucht werden? ");
    int suchzahl = In.readInt();
    Out.print("Die Zahl " + suchzahl + " wurde");
    if (baum.gefunden(suchzahl))
         Out.println(" gefunden.");
    else Out.println(" nicht gefunden.");
  } // main
} // class BinBaumBsp1