BinTreeNode.java

/**
 * Ein Knoten in einem binaeren Baum.
 *
 * Der gespeicherte Wert ist unveraenderlich,
 * die Referenzen auf die Nachfolger koennen aber
 * geaendert werden.
 *
 * Die Klasse bietet Methoden, um Werte aus einem Baum
 * zu suchen und einzufuegen. Die Methode zur Suche gibt
 * es noch in einer optimierten Variante, um
 * rotate-to-root Baeume zu verwalten.
 */
public class BinTreeNode {
  /**
   * Linker Nachfolger
   */
  private BinTreeNode left;
  /**
   * Rechter Nachfolger
   */
  private BinTreeNode right;
  /**
   * Wert, der in diesem Knoten gespeichert ist
   */
  private final int value;

  /**
   * Erzeugt einen neuen Knoten ohne Nachfolger
   * @param val Wert des neuen Knotens
   */
  public BinTreeNode(int val) {
    this.value = val;
    this.left = null;
    this.right = null;
  }

  /**
   * Erzeugt einen neuen Knoten mit den gegebenen Nachfolgern
   * @param val Wert des neuen Knotens
   * @param left linker Nachfolger des Knotens
   * @param right rechter Nachfolger des Knotens
   */
  public BinTreeNode(int val, BinTreeNode left, BinTreeNode right) {
    this.value = val;
    this.left = left;
    this.right = right;
  }
  
  /**
  * @return Wert des aktuellen Knotens
  *
  */	
  public int getValue() {
    return this.value;
  }

  /**
   * @return Der gespeicherte Wert, umgewandelt in einen String
   */
  public String getValueString() {
    return Integer.toString(this.value);
  }

  /**
   * @return true, falls der Knoten einen linken Nachfolger hat, sonst false 
   */	
  public boolean hasLeft() {
    return this.left != null;
  }
  /**
   * @return true, falls der Knoten einen rechten Nachfolger hat, sonst false 
   */	
  public boolean hasRight() {
    return this.right != null;
  }


  /**
   * @return linker Nachfolger des aktuellen Knotens
   */		
  public BinTreeNode getLeft() {
    return this.left;
  }
  /**
   * @return rechter Nachfolger des aktuellen Knotens
   */	
  public BinTreeNode getRight() {
    return this.right;
  }

  /**
   * Sucht in diesem Teilbaum nach x, ohne den Baum zu veraendern.
   * @param x der gesuchte Wert
   * @return true, falls x enthalten ist, sonst false
   */
  public boolean simpleSearch(int x) {
    //TODO
	  if(this.getValue()==x)
	  {
		  return true;
	  }
	  else if(this.getValue()>x&&this.hasLeft())
	  {
		  return this.getLeft().simpleSearch(x);
	  }
	  else if(this.getValue()<x&&this.hasRight())
	  {
		  return this.getRight().simpleSearch(x);
	  }
	  else
	  {
		  return false;
	  }
  }

  /**
   * Fuegt x in diesen Teilbaum ein.
   * @param x der einzufuegende Wert
   */
  public void insert(int x) {
   //TODO
	  if(this.getValue() == x)
	  {
		  
	  }
	  else if(this.getValue()>x&&this.hasLeft())
	  {
		  left.insert(x);
	  }
	  else if(this.getValue()<x&&this.hasRight())
	  {
		  right.insert(x);
	  }
	  else if(this.getValue()>x&&!this.hasLeft())
	  {
		  this.left = new BinTreeNode(x);
	  }
	  else if(this.getValue()<x&&!this.hasRight())
	  {
		  this.right = new BinTreeNode(x);
	  }
  }

  /**
   * Sucht in diesem Teilbaum nach x und rotiert den Endpunkt der Suche in die
   * Wurzel.
   * @param x der gesuchte Wert
   * @return die neue Wurzel des Teilbaums
   */
  public BinTreeNode rotationSearch(int x) {
    // Auskommentiert, da es nicht vollständig funktioniert um keine Compile oder Runtime Errors in der Abgabe zu haben

    /*if(this.hasLeft()) {
    if(this.getLeft().getValue() == x) {
      System.out.println("Left.value == x (" + this.getLeft().getValue() + " == " + x + "); this.value = " + this.value);
      /*BinTreeNode temp = this.left;
      System.out.println("Set temp to " + temp);
      this.left = this.left.getRight();
      System.out.println("Set this.left to " + this.left);
      this.left.right = temp;
      System.out.println("Set this.left.right to " + this.left.right);
      return temp;
    } else if(this.left.getValue() > x) {
      System.out.println("recursively search left subtree " + this.left);
      this.left.rotationSearch(x);
    }
  }

  if(this.hasRight()) {
    if(this.getRight().getValue() == x) {
        System.out.println("Right.value == x; this.value = " + this.value);
        BinTreeNode temp = this.right;
        System.out.println("Set temp to " + temp);
        this.right = this.right.getLeft();
        System.out.println("Set this.right to " + this.right);
        this.right.left = temp;
        System.out.println("Set this.right.left to " + this.right.left);
        return temp;
    } else if(this.right.getValue() < x) {
      System.out.println("recursively search right subtree " + this.right);
      this.right.rotationSearch(x);
    }
  }*/

    
	  return this;
  }

  /**
   * @return Geordnete Liste aller Zahlen, die in diesem Teilbaum gespeichert sind.
   */
  public String toString() {
    String output = "";
    if(hasLeft()) {
      output += left.toString() + ", ";
    }

    output += value;

    if(hasRight()) {
      output += ", " + right.toString();
    }

	  return output;
  }
 
  /**
   * Erzeugt eine dot Repraesentation in str
   * @param str Stringbuilder Objekt zur Konstruktion der Ausgabe
   * @param nullNodes Hilfsvariable, um Nullknoten zu indizieren. Anfangswert sollte 0 sein. 
   * @return Den nullNodes Wert fuer den behandelten Baum
   */
  public int toDot(StringBuilder str, int nullNodes) {
    if(this.hasLeft()) {
      str.append(this.getValueString() + " -> " + this.left.getValueString() + ";"
        + System.lineSeparator());
      nullNodes = this.left.toDot(str, nullNodes);
    } else {
      str.append("null" + nullNodes + "[shape=point]" + System.lineSeparator()
        + this.getValueString() + " -> null" + nullNodes + ";" + System.lineSeparator());
      nullNodes += 1;
    }
    if(this.hasRight()) {
      str.append(this.getValueString() + " -> " + this.right.getValueString() + ";"
        + System.lineSeparator());
      nullNodes = this.right.toDot(str, nullNodes);
    } else {
      str.append("null" + nullNodes + "[shape=point]" + System.lineSeparator()
        + this.getValueString() + " -> null" + nullNodes + ";" + System.lineSeparator());
      nullNodes += 1;
    }
    return nullNodes;
  }

}