====== Ein Binärbaum mit Java ======

Ein (Binär)Baum ist eine rekursive Datenstruktur. Bei jedem Knoten des Baums zeigen ''left'' und ''right'' jeweils auf einen weiteren Baum:


{{ :faecher:informatik:oberstufe:adt:baeume:javabaum:recurse.drawio.png |}}

Die **Blätter** des Baums zeichnen sich dadurch aus, dass ''left'' und ''right'' auf ''null'' zeigen, also nicht auf weitere "Unterbäume" verweisen.

===== Eine Implementation in Java =====

Mit diesen Überlegungen kann man sich die folgende Implementation in Java ansehen: https://codeberg.org/qg-info-unterricht/binaerbaum-einstieg

Es gibt nur eine Klasse ''Binaerbaum'' die eigentlich Knotenobjekte darstellt. Der Baum selbst wird repräsentiert durch das Knotenobjekt des Wurzelknotens. 

Durch [[https://de.wikipedia.org/wiki/%C3%9Cberladen|überladen]] des Konstruktors wird Polymorphie des Konstruktors erzwungen, man kann also verschiedene Knoten erzeugen: 

  * Innere Knoten: Erhalten als Argumente einen Datenwert und die Wurzelknoten der Unterbäume ''links'' und ''rechts''
  * Blattknoten: Erhalten einen (oder keinen) Datenwert.  ''links'' und ''rechts'' wird auf ''null'' gesetzt.

----
{{:aufgabe.png?nolink  |}}
=== (A1) ===

Untersuche die Klasse ''Binaerbaum'' und ihre Methoden im Projekt. Erzeuge mit Hilfe der zur Verfügung stehenden Methoden den in der Abbildung gezeigten Baum mit Integer-Werten:

  * Top-Down, beginnend beim Wurzelknoten
  * Bottom-Up, beginnend bei den Blättern

{{ :faecher:informatik:oberstufe:adt:baeume:javabaum:aa1.drawio.png |}}

  * Verifiziere jeweils durch die Inspizieren Funktion von BlueJ, dass die Baumstruktur wie gefordert stimmt, indem due beim Wurzelknoten beginnend den Pfaden folgst.
  * Teste die Methode ''isBlatt'' und verifiziere die Funktionsweise an mehreren Knoten.

++++ Hilfestellung |
{{ :faecher:informatik:oberstufe:adt:baeume:javabaum:2024-05-01_20-03.png?nolink |}}
++++

----
{{:aufgabe.png?nolink  |}}
=== (A2) ===

Implementiere die Methoden ''baueBaumTopDown'' und ''baueBaumBottomUp''  in der Klasse ''Zahlenbaum'', so dass der dargestellt Baum aus Integerwerten entsteht.

++++ Lösungsvorschlag |
{{ :faecher:informatik:oberstufe:adt:baeume:javabaum:2024-05-01_20-31.png?nolink |}}
++++