Binary Search Tree

• Ein Baum ist eine Datenstruktur welche eine Wurzel und beliebig viele Blätter hat, wobei man sich den Baum um 180° gedreht vorstellen muss (siehe Grafik unten, 8 ist die Wurzel, alle anderen Elemente sind die Blätter)
• Beim Einfügen eines Wertes verhält sich ein binärer Suchbaum folgendermaßen:
  1. Der übergebene Wert wird in eine Node (Knoten verpackt)
  2. Ist der Baum leer, so wird der aktuelle Knoten zur Wurzel
  3. Ist der Baum nicht leer so wird geprüft ob der Wert des aktuellen Knotens < oder >= der Wurzel ist
     • < (Kleiner)
       • Der linke Platzhalter der Wurzel ist leer -> Aktueller Knoten wird in den linken Platzhalter gesetzt
       • Der linke Platzhalter der Wurzel ist nicht leer -> Zurück zu 3), jedoch wird nicht mehr mit der Wurzel geprüft sondern mit dem linken Platzhalter
     • >= (Größer gleich)
       • Der rechte Platzhalter der Wurzel ist leer -> Aktueller Knoten wird in den linken Platzhalter gesetzt
       • Der rechte Platzhalter der Wurzel ist nicht leer -> Zurück zu 3), jedoch wird nicht mehr mit der Wurzel geprüft sondern mit dem rechten Platzhalter
     • Dies erfordert einen rekursiven Aufruf, das heißt, die Methode ruft sich selbst auf
• Der binäre Suchbaum soll fürs erste einfach nur mit Ganzzahlen (int)  funktionieren.
• Erstelle die Datenstruktur für einen Binären Suchbaum in der Klasse BinarySearchTree.
  • Erstelle folgende Methoden
    • public void addValue(int value) { ... }
    • public void traverseInOrder() { ... }
      • Diese Methode soll den Baum in In-Order durchlaufen und die Werte der Elemente ausgeben
    • public List<Integer> getElementsInOrder() { ... }
      • Soll die Liste der Elemente In-Order zurückgeben
• Erstelle die Klasse Node für die Blätter des Baums
  • Eine Node enthält einen Wert
  • Platzhalter für die Node auf der linken Seite
  • Platzhalter für die Node auf der rechten Seite
• Teste deine BinarySearchTree Klasse ausgiebig mit Unit tests
• Kannst du deine Datenstruktur verwenden um eine Liste zu sortieren?