\documentclass{bschlangaul-aufgabe}
\bLadePakete{java,baum}
\begin{document}
\bAufgabenMetadaten{
  Titel = {Frühjahr 2014 (46115) - Thema 2 Aufgabe 3},
  Thematik = {Binärer Suchbaum 17, 7, 21, 3, 10, 13, 1, 5},
  Referenz = 46115-2014-F.T2-A3,
  RelativerPfad = Examen/46115/2014/03/Thema-2/Aufgabe-3.tex,
  ZitatSchluessel = examen:46115:2014:03,
  BearbeitungsStand = mit Lösung,
  Korrektheit = unbekannt,
  Ueberprueft = {unbekannt},
  Stichwoerter = {Binärbaum},
  EinzelpruefungsNr = 46115,
  Jahr = 2014,
  Monat = 03,
  ThemaNr = 2,
  AufgabeNr = 3,
}

\begin{enumerate}

%%
% (a)
%%

\item Fügen Sie die Zahlen 17, 7, 21, 3, 10, 13, 1, 5 nacheinander in
der vorgegebenen Reihenfolge in einen binären Suchbaum ein und zeichnen
Sie das Ergebnis!\index{Binärbaum}
\footcite{examen:46115:2014:03}

\begin{bAntwort}
\begin{center}
\begin{tikzpicture}[b binaer baum]
\Tree
[.17
  [.7
    [.3
      [.1 ]
      [.5 ]
    ]
    [.10
      \edge[blank]; \node[blank]{};
      [.13 ]
    ]
  ]
  [.21 ]
]
\end{tikzpicture}
\end{center}
\end{bAntwort}

%%
% (b)
%%

\item Implementieren Sie in einer objektorientierten Programmiersprache
eine rekursiv festgelegte Datenstruktur, deren Gestaltung sich an
folgender Definition eines binären Baumes orientiert!

Ein binärer Baum ist entweder ein leerer Baum oder besteht aus einem
Wurzelelement, das einen binären Baum als linken und einen als rechten
Teilbaum besitzt. Bei dieser Teilaufgabe können Sie auf die
Implementierung von Methoden (außer ggf. notwendigen Konstruktoren)
verzichten!

\begin{bAntwort}
\bPseudoUeberschrift{Klasse „Knoten“}

\begin{minted}{java}
class Knoten {
  public int wert;
  public Knoten links;
  public Knoten rechts;
  public Knoten elternKnoten;

  Knoten(int wert) {
    this.wert = wert;
    links = null;
    rechts = null;
    elternKnoten = null;
  }

  public Knoten findeMiniumRechterTeilbaum() {
  }

  public void anhängen (Knoten knoten) {
  }
}
\end{minted}

\bPseudoUeberschrift{Klasse „BinärerSuchbaum“}

\begin{minted}{java}

public class BinärerSuchbaum {
  public Knoten wurzel;

  BinärerSuchbaum(Knoten wurzel) {
    this.wurzel = wurzel;
  }

  BinärerSuchbaum() {
    this.wurzel = null;
  }

  public void einfügen(Knoten knoten) {
  }

  public void einfügen(Knoten knoten, Knoten elternKnoten) {
  }

  public Knoten suchen(int wert) {
  }

  public Knoten suchen(int wert, Knoten knoten) {
  }

}
\end{minted}

\end{bAntwort}
%%
% (c)
%%

\item Beschreiben Sie durch Implementierung in einer gängigen
objektorientierten Programmiersprache, wie bei Verwendung der obigen
Datenstruktur die Methode \bJavaCode{loescheKnoten(w)} gestaltet sein muss,
mit der der Knoten mit dem Eintrag \bJavaCode{w} aus dem Baum entfernt werden
kann, ohne die Suchbaumeigenschaft zu verletzen!

\begin{bAntwort}
\bJavaExamen[firstline=64,lastline=93]{46115}{2014}{03}{suchbaum/BinaererSuchbaum}
\end{bAntwort}
\end{enumerate}

\begin{bAntwort}
\bPseudoUeberschrift{Klasse „BinärerSuchbaum“}

\bJavaExamen{46115}{2014}{03}{suchbaum/BinaererSuchbaum}

\bPseudoUeberschrift{Klasse „Knoten“}

\bJavaExamen{46115}{2014}{03}{suchbaum/Knoten}
\end{bAntwort}
\end{document}