/** Ein binaerer Suchbaum mit ganzen Zahlen als Datensatz:
  * Vorlage fuer die A1 von algo-pr06 und fuer die A1 von algo-h07.
  * Als Operationen stehen `contains' und `insert' zur Verfuegung.
  */
public class BinarySearchTree {

  /** Die Knotenklasse als statische innere Klasse. */
  public static class Node {
    /** der eigentliche Wert des Knotens */
    private int  value;
    /** der linke Nachfolger des Knotens */
    private Node left;
    /** der rechte Nachfolger des Knotens */
    private Node right;

    /**
     * den Knoten aus seinem Wert erzeugen
     * @param  value  eigentlicher Knoteninhalt
     */
    public Node(int value) {
      this.value = value;
    }

    public String toString() {
      return this.value + " ";
    }

    /**
     * Getter fuer den Knotenwert
     * @return  Knotenwert
     */
    public int getValue() {
      return this.value;
    }

    /**
     * Getter fuer das linke Kind des Knotens
     * @return  linkes Kind
     */
    public Node getLeft() {
      return this.left;
    }

    /**
     * Getter fuer das rechte Kind des Knotens
     * @return  rechtes Kind
     */
    public Node getRight() {
      return this.right;
    }

    /**
     * Setter fuer den Knotenwert
     * @param  value  neuer Knoteninhalt
     */
    public void setValue(int value) {
      this.value = value;
    }

    /**
     * Setter fuer das linke Kind des Knotens
     * @param  node  neues linkes Kind
     */
    public void setLeft(Node node) {
      this.left = node;
    }

    /**
     * Setter fuer das rechte Kind des Knotens
     * @param  node  neues rechtes Kind
     */
    public void setRight(Node node) {
      this.right= node;
    }
  }

  /** Baumwurzel */
  protected Node root;

  /**
   * Herausfinden, ob ein gewisser Datensatz schon im binaeren Suchbaum enthalten ist.
   *
   * @param   data  zu suchender Datensatz
   * @return        true: Datensatz ist vorhanden; false: Datensatz ist nicht vorhanden.
   */
  public boolean contains(int data) {
    Node temp = root;
    while(temp != null) {
      if (temp.getValue() == data) {
        return true;
      }
      if (temp.getValue() > data) {
        temp = temp.getLeft();
      } else {
        temp = temp.getRight();
      }
    }
    return false;
  }

  /**
   * Einen neuen Datensatz in den binaeren Suchbaum einfuegen.
   *
   * @param   data  einzufuegender Datensatz
   * @return        true: Datensatz wurde eingefuegt; false: Datensatz war schon vorhanden.
   */
  public boolean insert(int data) {
    if (root == null) {
      root = new Node(data);
      return true;
    }

    Node temp = root;
    while(temp.getValue() != data) {
      if (temp.getValue() > data) {
        if(temp.getLeft() == null) {
          temp.setLeft(new Node(data));
          return true;
        }
        temp = temp.getLeft();
      } else {
        if (temp.getRight() == null) {
          temp.setRight(new Node(data));
          return true;
        }
        temp = temp.getRight();
      }
    }
    return false;
  }

        /** diese Klasse testen
            @param  args  Parameter des Programmaufrufs */
  public static void main(String[] args) {
    BinarySearchTree tree = new BinarySearchTree();
    for (int i = 0; i < 20; i++) {
      int x = (int) (Math.random() * 50);
      System.out.println(x);
      tree.insert(x);
    }
    for (int i = 0; i < 50; i++) {
      System.out.println(i + ": " + tree.contains(i));
    }
  }
}