% Dieses Dokument ist in der Zusammenarbeit von angehenden und
% ausgebildeten Informatiklehrkräften entstanden.
% Der Herausgeber dieses Dokuments ist die Fachgruppe Informatische
% Bildung in NRW der Gesellschaft für Informatik.
%
% Das Dokument steht unter der Lizenz: Creative Commons by-nc-sa Version 4.0
% https://creativecommons.org/licenses/by-nc-sa/4.0/deed.de
%
% Nach dieser Lizenz darf das Dokument beliebig kopiert und bearbeitet werden,
% sofern das Folgeprodukt wiederum unter gleichen Lizenzbedingungen vertrieben
% und auf die ursprünglichen Urheber verwiesen wird.
% Eine kommerzielle Nutzung ist ausdrücklich ausgeschlossen.
%
% Die Namensnennung durch einen Verweis und die Lizenzangabe der ursprünglichen
% Urheber auf den Materialien für Schülerinnen und Schüler ist erforderlich.
%
% Die Sammlung der Dokumente steht unter
% https://matsam.fg-ibn.gi.de
% zur Verfügung.
%
% Das LaTeX-Paket zum Setzen der Dokumente der Sammlung steht
% unter https://www.ctan.org/pkg/schule
% zur Verfügung.

\chapter{Der erste Baum}
\label{cap:baum}

\begin{uebersichtBox}
In diesem Kapitel dreht sich alles darum, aus den Ergebnissen der binären Suche eine neue Datenstruktur zu konzipieren, die deren Vorteile in sich beinhaltet.
\end{uebersichtBox}

\begin{lernzieleBox}
    Nach Bearbeitung dieses Kapitels
    \begin{smallitemize}
        \item können Sie die Eigenschaften eines binären Suchbaums und dessen einzelnen Bestandteile benennen.
        \item können Sie einen binären Baum auf eine bestimmte Art und Weise durchlaufen.
    \end{smallitemize}
\end{lernzieleBox}

\section{Wir entwerfen eine neue Datenstruktur}
Nachdem Sie im letzten Kapitel das Prinzip der \enquote{Binären Suche} kennengelernt haben, soll es in diesem Kapitel darum gehen, eine Datenstruktur zu entwickeln, die die Vorteile der binären Suche ausnutzt. Der Einfachheit halber arbeiten wir an dieser Stelle zuerst nur mit einer Menge von Zahlen. Generell lässt sich dieses Prinzip aber auf jede beliebige Art von Elementen übertragen -- \textit{vorausgesetzt,} dass die Elemente auf irgendeine Art und Weise miteinander vergleichbar sind (oder mathematisch ausgedrückt: einer Ordnungsrelation unterliegen). Wenn das Prinzip soweit klar ist, werden wir uns wieder unserer CD-Sammlung zuwenden.

Das Problem an der linearen Liste ist, dass die Zahlen nach wie vor darin nur in aufsteigend sortierter Reihenfolge vorliegen, ein direkter Zugriff auf die Elemente aber so, wie wir sie in der binären Suche benötigen, nicht möglich ist. Was liegt also näher, als eine neue Datenstruktur zu entwickeln, die die Vorteile der Suche nach einem bestimmten Element schon bei ihrem Aufbau berücksichtigt und so die Suchanfragen minimiert.

Damit wollen wir uns auf den folgenden Seiten beschäftigen.
\begin{aufgabe}
    Gegeben ist die Liste der Zahlen von 1 bis 9 in aufsteigender Reihenfolge:
    \begin{center}
        1, 2, 3, 4, 5, 6, 7, 8, 9.
    \end{center}
    \begin{teilaufgaben}
        \teilaufgabe Wenden Sie die binäre Suche an, um das Element 2 in der Liste zu finden. Notieren Sie dabei wiederum jede Zahl, die Sie betrachten. Verfahren Sie ebenso mit der Zahl 9.

        \textbf{Erinnerung:} Betrachten wir eine ungerade Zahl von Elementen, runden wir das Ergebnis für die Mitte ab!

        \teilaufgabe Überlegen Sie eine Möglichkeit, Ihr Ergebnis und der Weg, den Sie von Element zu Element gegangen sind, graphisch in \textit{einer} Zeichnung darzustellen. Beachten Sie dabei auch, in welche \enquote{Richtung} Sie sich von Element zu Element bewegt haben. Vervollständigen Sie diese Zeichnung so, dass die Suche nach allen Elementen (also auch nach der 1,3,4,\ldots) daraus abgelesen werden kann. (Schauen Sie nach dieser Aufgabe noch \textbf{nicht} in die Lösungen, sondern bearbeiten Sie erst die nächste Aufgabe.)

        \teilaufgabe Zeichnen Sie Ihre Idee auf ein DIN A4-Blatt und vergleichen Sie diese mit einem Partner. Versuchen sie, ihre Ideen zu kombinieren, dass eine sinnvolle Darstellung entsteht.
    \end{teilaufgaben}
\end{aufgabe}
\begin{loesung}
    \begin{teilaufgaben}
        \teilaufgabe Zur 2: 5, 3, 2\\
            Zur 9: 5, 8, 9

        \teilaufgabe Eine mögliche Darstellung für alle Suchdurchläufe:
            \begin{center}
                \begin{tikzpicture}[level distance=13mm, level/.style={sibling distance=24mm/#1}, every node/.style={draw,circle,fill=white}]
                    \node[circle, draw] (root) {5}
                        child {node {3}
                            child {node {2}
                                child {node {1}}
                                child[missing] {node {x}}
                            }
                            child {node {4}}
                        }
                        child {node {8}
                            child {node {7}
                                child {node {6}}
                                child[missing] {node {x}}
                            }
                            child {node {9}}
                        };
                \end{tikzpicture}
            \end{center}
            Die Idee dahinter ist, dass man -- ausgehend von der betrachteten Zahl -- eine Linie nach rechts oder links zeichnet, die \enquote{getroffene} Zahl dort notiert und diesen Vorgang wiederholt, bis die Zahl gefunden wurde.
    \end{teilaufgaben}
\end{loesung}

Sollten Sie mit der Aufgabe nicht klarkommen, können Sie sich im Kasten unten eine Anregung holen.

\begin{nothelferBox}
    \begin{enumerate}
        \item Mit welchem der Elemente beginnt Ihre Suche \textbf{immer}? Dieses Element sollte in Ihrer Darstellung oben stehen.
        \item Wie viele Möglichkeiten haben Sie, um von einem Element zum nächsten zu gelangen? Zeichnen Sie die möglichen nachfolgenden Elemente unterhalb des aktuellen Elements und beachten Sie dabei die \enquote{Richtung}, in die Sich sich auf sie zu bewegst.
  \end{enumerate}
\end{nothelferBox}

\section{Der binäre Suchbaum}
Die untenstehende Darstellung zeigt Ihnen einen sogenannten \textbf{binären Suchbaum}.
\begin{center}
    \begin{tikzpicture}[level distance=13mm, level/.style={sibling distance=24mm/#1}, every node/.style={draw,circle,fill=white}]
        \node[circle, draw] (root) {5}
            child {node {3}
                child {node {2}
                    child {node {1}}
                    child[missing] {node {x}}
                }
                child {node {4}}
            }
            child {node {8}
                child {node {7}
                    child {node {6}}
                    child[missing] {node {x}}
                }
                child {node {9}}
            };
    \end{tikzpicture}
\end{center}
Der binäre Suchbaum ist aus den einzelnen Suchanfragen entstanden und zeichnet den Weg nach, den wir bei der Suche nach einem bestimmten Element zurückgelegt haben. Haben wir beispielsweise nach dem Element \tikz{\node[draw, circle]{\footnotesize 6};} gesucht, so wurde dabei der folgende Weg zurückgelegt:
\begin{center}
    \begin{tikzpicture}[every node/.style={draw,circle,node distance=1.5cm}]
        \node (f) {5};
        \node[right of=f] (a) {8};
        \node[right of=a] (si) {7};
        \node[right of=si,thick] (se) {6};

        \path[draw,] (f) -- (a) -- (si) -- (se);
    \end{tikzpicture}
 \end{center}
\begin{theorieBox}
    Bäume sind eine der wichtigsten dynamischen Datenstrukturen in der Informatik. Bevor wir auf weiterführende Eigenschaften der Bäume zu sprechen kommen, folgen zuerst einige grundlegende Definitionen:
    \begin{itemize}
        \item Die Elemente, aus denen ein Baum besteht, werden \textbf{Knoten} genannt. Der oberste Knoten in einem Baum heißt \textbf{Wurzel}\footnote{Dies entspricht nicht unbedingt der Intuition, da die Wurzel in unseren Bäumen immer oben ist. Man kann sich den Begriff leichter merken, wenn man sich klarmacht, dass alle anderen Knoten an der Wurzel \enquote{hängen}.}.

        \item Die Verbindungslinien zwischen zwei Knoten heißen \textbf{Kanten}.

        \item Da es sich bei unserem Suchbaum um einen \emph{binären} Baum\footnote{Erinnern Sie sich daran, woher der Begriff \enquote{Binäre Suche} stammt.} handelt, kann ein Knoten \textbf{maximal zwei} direkte Nachfolger haben. Knoten, die keinen Nachfolger haben, nennt man \textbf{Blatt}.

        \item Die \textbf{Höhe} eines Baums ist definiert als der längste Weg von der Wurzel zu einem Blatt. Wir bewegen uns dabei von oben nach unten entlang der Kanten. Im obigen Beispiel hat der Baum eine Höhe von $h=4$.
    \end{itemize}
    Binäre Suchbäume dienen u.\,a. dazu, Daten (vor allem Daten, die sich häufig verändern) aufzunehmen und zu speichern. Durch ihre Struktur (auf die wir später noch genauer zu sprechen kommen werden), lassen sich Bäume effizient nach bestimmten Daten durchsuchen.
\end{theorieBox}

Es gibt viele verschiedene Arten von Bäumen in der Informatik, wir beschäftigen uns im Rahmen dieses Leitprogramms aber überwiegend mit den binären Suchbäumen. Warum dieser Baum \enquote{binärer} Baum heißt, haben wir uns bereits verdeutlicht. Im Folgenden wollen wir einige Eigenschaften untersuchen, die binäre Suchbäume für uns interessant machen.

\section{Eigenschaften des binären Suchbaums}
\label{eigBinBaum}
Bevor wir uns mit der elementarsten Eigenschaft des binären Suchbaums befassen können, benötigen wir eine weitere Definition: Den sogenannten Teilbaum.
\begin{center}
    \begin{tikzpicture}[level distance=13mm, level/.style={sibling distance=30mm/#1}, every node/.style={draw,circle,fill=white}]
        \node[circle, draw] (root) {5}
            child {node[draw=red] {3}
                child {node[draw=red] {2}
                    child {node[draw=red] {1}}
                    child[missing] {node {x}}
                }
                child {node[draw=red] {4}}
            }
            child {node {8}
                child {node[draw=blue] {7}
                    child {node[draw=blue] {6}}
                    child[missing] {node {x}}
                }
            child {node {9}}
            };
        \begin{pgfonlayer}{background}
            \node[draw=red,rectangle,rounded corners,fill=yellow!20, fit=(root-1) (root-1-1) (root-1-2) (root-1-1-1)] {};
            \node[draw=blue,rectangle,rounded corners,fill=blue!20, fit=(root-2-1) (root-2-1-1)] {};
        \end{pgfonlayer}
    \end{tikzpicture}
\end{center}
Ein \textbf{Teilbaum} eines binären Suchbaums sind alle Knoten, die von einem bestimmten Knoten aus erreichbar sind. Im Beispiel sind zwei solche Teilbäume eingezeichnet. Den obersten Knoten dieser Teilbäume nennen wir ebenfalls \textbf{Wurzel}, diesmal jedoch die Wurzel eines Teilbaums. Zusätzlich unterscheiden wir zwischen einem \textbf{linken} und einem \textbf{rechten} Teilbaum: Im oberen Beispiel ist der linke Teilbaum von 3 der Teilbaum mit den Knoten 1 und 2, der rechte Teilbaum ist der Knoten 4. Enthält ein Teilbaum keine Knoten, bezeichnen wir ihn als \textbf{leer}.

Es folgen einige Aufgaben, mit denen Sie Ihr Verständnis für den Begriff des Teilbaums überprüfen können.
\begin{aufgabe}
    \begin{teilaufgaben}
        \teilaufgabe Aus welchen Knoten besteht der Teilbaum mit der Wurzel 8?
        \teilaufgabe Welche Knoten gehören zum linken, welche zum rechten Teilbaum des blau eingezeichneten Teilbaums?
        \teilaufgabe Ist der Teilbaum mit einem Blatt als Wurzel ebenfalls ein Teilbaum?
        \teilaufgabe Ein Knoten kann maximal von zwei verschiedenen Teilbäumen die Wurzel sein. Nehmen Sie Stellung.
    \end{teilaufgaben}
\end{aufgabe}
\begin{loesung}
    \begin{teilaufgaben}
        \teilaufgabe 8 -- 7 -- 6 -- 9

        \teilaufgabe Der linke Teilbaum besteht aus dem Knoten mit der Zahl 6, der rechte Teilbaum ist leer.

        \teilaufgabe Ja, denn es kommt nicht darauf an, ob ein Knoten tatsächlich Nachfolger hat oder nicht.

        \teilaufgabe Die Aussage ist falsch. Der Teilbaum ist definiert als die Menge aller Knoten, die von einer gegebenen Wurzel aus erreichbar sind. Damit kann jeder Knoten nur Wurzel genau eines Teilbaums sein.
    \end{teilaufgaben}
\end{loesung}

Im Folgenden wollen wir eine Eigenschaft untersuchen, die besonders im Hinblick darauf wichtig ist, wenn wir unseren Suchbaum \enquote{von Grund auf aufbauen} oder Elemente in den Baum einfügen wollen, ohne seine leichte Durchsuchbarkeit direkt zu zerstören. Bearbeiten Sie hierzu folgende Aufgabe:
\begin{aufgabe}
    Betrachten Sie einen beliebigen Teilbaum mit der Wurzel $w$. Welche elementare Eigenschaft fällt Ihnen auf, wenn Sie die Werte innerhalb der Knoten miteinander vergleichen? Begründen Sie dies!
\end{aufgabe}
\begin{loesung}
    Bei einem gegebenen Teilbaum mit Wurzel $w$ sind alle Knoten in der linken Seite des Teilbaums \textbf{kleiner} als die Wurzel selbst. Die Knoten auf der rechten Seite dagegen sind alle \textbf{größer} als das Element in der Wurzel.

    Verdeutlicht man sich, wie der Baum aufgebaut wurde, so wird diese Eigenschaft unmittelbar ersichtlich: Das mittlere Element (hier die 5) hat die Menge der Zahlen genau in zwei Hälften geteilt: eine mit kleineren und eine mit größeren Zahlen darin. Somit wird diese Zahl von uns als Wurzel festgelegt. Dieser Schritt wird nun für jede der Hälften wiederholt und jede der Zahlen wird damit zur Wurzel eines eigenen Teilbaums.
\end{loesung}

\begin{nothelferBox}
    Betrachten Sie zuerst einen einzelnen Knoten und dessen linken und rechten Nachfolger. Welche Relation besteht zwischen diesem Knoten und seinen Nachfolgern? Versuchen Sie anschließend, Ihr Ergebnis auf Teilbäume auszuweiten.
\end{nothelferBox}

\section{Wo ist die Ordnung hin?}
Nach den ziemlich theoretischen letzten Abschnitten kehren wir nun wieder etwas mehr zur konkreten Anwendung zurück.

Wir erinnern uns: Unser erster binärer Suchbaum ist als Produkt aus der binären Suche entstanden, indem wir die Reihenfolge der besuchten Elemente in eine graphische Darstellung gebracht haben. Das würde allerdings bedeuten, dass wir, um einen Baum aufzubauen, immer zuerst eine sortierte Menge von Elementen benötigen, auf die wir dann einzeln die binäre Suche anwenden, um unseren Baum Knoten um Knoten aufzubauen. Das klingt insgesamt nicht sehr effizient und nutzt auch nicht die Vorteile aus, die der Baum als Datenstruktur hat. Unser Ziel sollte es also sein, einen Baum durch die Vorgabe einer Menge von Elementen so aufbauen zu können, dass die Eigenschaft aus \autoref{eigBinBaum} erfüllt bleibt. Und natürlich sollte unser Baum ebenfalls die Möglichkeit haben, die in ihm abgelegten Elemente auch wieder in der richtigen Reihenfolge ausgeben zu können -- denn wenn man einen Baum an sich betrachtet, ist es nicht unbedingt direkt möglich, zu sagen, in welche Reihenfolge die Elemente ausgegeben werden müssen.

Den Aspekt des Aufbaus verschieben wir nun vorerst auf das nächste Kapitel und beschäftigen uns hier mit dem sogenannten \enquote{Baumdurchlauf} und welche Möglichkeiten es hierfür gibt. Hierzu betrachten wir folgenden Baum mit einigen der Interpreten aus Ihrer CD-Sammlung:
\begin{center}
    \footnotesize
    \begin{tikzpicture}[level distance=1.8cm,
            level/.style={sibling distance=7cm/#1},
            every node/.style={draw,ellipse,fill=white,text width=1.8cm, minimum height=.9cm, text centered}]
        \node (root) {Ivy Quainoo}
            child {node {David Guetta}
                child {node {Boy}
                    child {node {AC/DC}}
                    child[missing] {node {x}}
                }
                child {node {Eisblume}}
            }
            child {node {Rihanna}
                child {node {Michel Telo}
                    child {node {Lana Del Rey}}
                    child[missing] {node {x}}
                }
                child {node {The Overtones}
                    child {node {Silbermond}}
                    child[missing] {node {x}}
                }
            };
    \end{tikzpicture}
\end{center}

Wie Sie sich sicher schnell vergewissern können, ist die Eigenschaft aus \autoref{eigBinBaum} auch für diesen Baum erfüllt. Wie wollen uns nun einen Algorithmus überlegen, nach dem man vorgehen kann, um die Elemente in sortierter Reihenfolge aus dem Baum abzulesen.

\begin{aufgabe}
    Entwickeln Sie einen Algorithmus in Umgangssprache, der den Baum in der richtigen Reihenfolge wieder ausgibt.
\end{aufgabe}
\begin{loesung}
    Wir verdeutlichen uns den Ablauf zuerst anhand des Beispiels. Der Einfachheit halber (und da alle Anfangsbuchstaben verschieden sind), sind im Baum nur die Anfangsbuchstaben der jeweiligen Interpreten eingetragen.
    \NewTblrTheme{blank}{
        \DefTblrTemplate{firsthead}{default}{}%
        \DefTblrTemplate{middlehead,lasthead}{default}{}%
        \DefTblrTemplate{contfoot-text}{default}{}%
    }
    \begin{longtblr}[theme=blank]{colspec = {XX[c]}, hline{2-Y} = {0.5pt},vline{2}={0.5pt}}
        Wir beginnen an der Wurzel. Da uns bekannt ist, dass alle Elemente links der Wurzel definitiv vor der Wurzel ausgegeben werden müssen, steigen wir in den linken Teilbaum ein. &
        \footnotesize
        \begin{tikzpicture}[baseline, level distance=1cm,
                level/.style={sibling distance=2cm/#1},
                every node/.style={draw,circle,fill=white, text centered}]
            \node[draw=red,fill=red!20,thick] (root) {I}
                child {node {D}
                    child {node {B}
                        child {node {A}}
                        child[missing] {node {x}}
                    }
                    child {node {E}}
                }
                child {node {R}
                    child {node {M}
                        child {node {L}}
                        child[missing] {node {x}}
                    }
                    child {node {T}
                        child {node {S}}
                        child[missing] {node {x}}
                    }
                };
            \path[red,thick,draw,->] (root) -- (root-1);
        \end{tikzpicture} \\

        Wir betrachten erneut den linken Teilbaum, diesmal mit Knoten D als Wurzel (Begründung: s.o.) und setzen dieses Verfahren so lange fort, bis wir beim kleinsten Element angelangt sind. Dieses Element geben wir anschließend aus. &
        \footnotesize
        \begin{tikzpicture}[baseline, level distance=1cm,
                level/.style={sibling distance=2cm/#1},
                every node/.style={draw,circle,fill=white, text centered}]
            \node[draw=red,fill=red!20,thick] (root) {I}
                child {node[draw=red,fill=red!20,thick] {D}
                    child {node[draw=red,fill=red!20,thick] {B}
                        child {node[draw=blue,fill=blue!20,thick] {A}}
                        child[missing] {node {x}}
                    }
                    child {node {E}}
                }
                child {node {R}
                    child {node {M}
                        child {node {L}}
                        child[missing] {node {x}}
                    }
                    child {node {T}
                        child {node {S}}
                        child[missing] {node {x}}
                    }
                };

            \path[red,thick,draw,->] (root) -- (root-1) -- (root-1-1) -- (root-1-1-1);
        \end{tikzpicture} \\

        Nun steigen wir eine Ebene im Baum auf. Wir wissen, dass die Elemente im rechten Teilbaum von B (falls er existiert) \textbf{größer} sind als B und demnach erst danach ausgegeben werden müssen. Alle kleineren Elemente sind bereits abgearbeitet, also können wir an dieser Stelle das B ausgeben. &
        \footnotesize
        \begin{tikzpicture}[baseline, level distance=1cm,
                level/.style={sibling distance=2cm/#1},
                every node/.style={draw,circle,fill=white, text centered}]
            \node[draw=red,fill=red!20,thick] (root) {I}
                child {node[draw=red,fill=red!20,thick] {D}
                    child {node[draw=blue,fill=blue!20,thick] {B}
                        child {node[draw=black!20,thick] {\color{black!20}A}}
                        child[missing] {node {x}}
                    }
                    child {node {E}}
                }
                child {node {R}
                    child {node {M}
                        child {node {L}}
                        child[missing] {node {x}}
                    }
                    child {node {T}
                        child {node {S}}
                        child[missing] {node {x}}
                    }
                };
            \path[red,thick,draw,->] (root-1-1-1) -- (root-1-1);
        \end{tikzpicture} \\

        Wir steigen wiederum eine Ebene auf, da B's rechter Teilbaum leer ist, und geben das D aus. Danach steigen wir in den rechten Teilbaum von D ein, da sich dort alle Elemente befinden, die größer sind als D, aber kleiner als I. &
        \footnotesize
        \begin{tikzpicture}[baseline, level distance=1cm,
                level/.style={sibling distance=2cm/#1},
                every node/.style={draw,circle,fill=white, text centered}]
            \node[draw=red,fill=red!20,thick] (root) {I}
                child {node[draw=blue,fill=blue!20,thick] {D}
                    child {node[draw=black!20,thick] {\color{black!20}B}
                        child {node[draw=black!20,thick] {\color{black!20}A}}
                        child[missing] {node {x}}
                    }
                    child {node[draw=red,fill=red!20,thick] {E}}
                }
                child {node {R}
                    child {node {M}
                        child {node {L}}
                        child[missing] {node {x}}
                    }
                    child {node {T}
                        child {node {S}}
                        child[missing] {node {x}}
                    }
                };
            \path[red,thick,draw,->] (root-1-1) -- (root-1);
            \path[red,thick,draw,->] (root-1) -- (root-1-2);
            \path[black!20,thick,draw] (root-1-1-1) -- (root-1-1);
        \end{tikzpicture} \\

        Anschließend geben wir das E aus, da es sich um ein Blatt handelt und sowohl rechter als auch linker Teilbaum leer sind. &
        \footnotesize
        \begin{tikzpicture}[baseline, level distance=1cm,
                level/.style={sibling distance=2cm/#1},
                every node/.style={draw,circle,fill=white, text centered}]
            \node[draw=red,fill=red!20,thick] (root) {I}
                child {node[draw=black!20,thick] {\color{black!20}D}
                    child {node[draw=black!20,thick] {\color{black!20}B}
                        child {node[draw=black!20,thick] {\color{black!20}A}}
                        child[missing] {node {x}}
                    }
                    child {node[draw=blue,fill=blue!20,thick] {E}}
                }
                child {node {R}
                    child {node {M}
                        child {node {L}}
                        child[missing] {node {x}}
                    }
                    child {node {T}
                        child {node {S}}
                        child[missing] {node {x}}
                    }
                };
            \path[black!20,thick,draw] (root-1-1-1) -- (root-1-1) -- (root-1);
            \path[red,thick,draw,->] (root-1-2) -- (root-1) -- (root);
        \end{tikzpicture} \\

        Da nun alle Knoten des linken Teilbaums der Wurzel I ausgegeben wurden (und somit alle Elemente, die kleiner sind als I), steigen wir auf bis zur Wurzel und geben diese aus. &
        \footnotesize
        \begin{tikzpicture}[baseline, level distance=1cm,
            level/.style={sibling distance=2cm/#1},
            every node/.style={draw,circle,fill=white, text centered}]
            \node[draw=blue,fill=blue!20,thick] (root) {I}
                child {node[draw=black!20,thick] {\color{black!20}D}
                    child {node[draw=black!20,thick] {\color{black!20}B}
                        child {node[draw=black!20,thick] {\color{black!20}A}}
                        child[missing] {node {x}}
                    }
                    child {node[draw=black!20,thick] {\color{black!20}E}}
                }
                child {node {R}
                    child {node {M}
                        child {node {L}}
                        child[missing] {node {x}}
                    }
                    child {node {T}
                        child {node {S}}
                        child[missing] {node {x}}
                    }
                };
            \path[red,thick,draw,->] (root-1-2) -- (root-1) -- (root);
            \path[black!20,thick,draw] (root-1-1-1) -- (root-1-1) -- (root-1);
        \end{tikzpicture} \\

        Anschließend müssen die Knoten des rechten Teilbaums ausgegeben werden. Wir steigen in den rechten Teilbaum ein, hin zum R. &
        \footnotesize
        \begin{tikzpicture}[baseline, level distance=1cm,
                level/.style={sibling distance=2cm/#1},
                every node/.style={draw,circle,fill=white, text centered}]
            \node[draw=black!20,thick] (root) {\color{black!20}I}
                child {node[draw=black!20,thick] {\color{black!20}D}
                    child {node[draw=black!20,thick] {\color{black!20}B}
                        child {node[draw=black!20,thick] {\color{black!20}A}}
                        child[missing] {node {x}}
                    }
                    child {node[draw=black!20,thick] {\color{black!20}E}}
                }
                child {node[draw=red,fill=red!20,thick] {R}
                    child {node {M}
                        child {node {L}}
                        child[missing] {node {x}}
                    }
                    child {node {T}
                        child {node {S}}
                        child[missing] {node {x}}
                    }
                };
            \path[red,thick,draw,->] (root) -- (root-2);
            \path[black!20,thick,draw] (root-1-1-1) -- (root-1-1) -- (root-1) -- (root-1-2) -- (root-1) -- (root);
        \end{tikzpicture} \\

        An dieser Stelle verdeutlichen wir uns nochmals die Eigenschaft aus \autoref{eigBinBaum} - alle Knoten im rechten Teilbaum von I sind \textbf{größer} als I. Für R gilt wiederum: Alle Knoten im linken Teilbaum von  R sind \textbf{kleiner} als R, alle im rechten Teilbaum \textbf{größer}. Also steigen wir als nächstes in den \textbf{linken} Teilbaum von R hinab. Dort verfahren wir nach dem gleichen Schema. &
        \footnotesize
        \begin{tikzpicture}[baseline, level distance=1cm,
                level/.style={sibling distance=2cm/#1},
                every node/.style={draw,circle,fill=white, text centered}]
            \node[draw=black!20,thick] (root) {\color{black!20}I}
                child {node[draw=black!20,thick] {\color{black!20}D}
                    child {node[draw=black!20,thick] {\color{black!20}B}
                        child {node[draw=black!20,thick] {\color{black!20}A}}
                        child[missing] {node {x}}
                    }
                    child {node[draw=black!20,thick] {\color{black!20}E}}
                }
                child {node[draw=red,fill=red!20,thick] {R}
                    child {node[draw=red,fill=red!20,thick] {M}
                        child {node[draw=red,fill=red!20,thick] {L}}
                        child[missing] {node {x}}
                    }
                    child {node {T}
                        child {node {S}}
                        child[missing] {node {x}}
                    }
                };
            \path[red,thick,draw,->] (root-2) -- (root-2-1) -- (root-2-1-1);
            \path[black!20,thick,draw] (root-1-1-1) -- (root-1-1) -- (root-1) -- (root-1-2) -- (root-1) -- (root) -- (root-2);
        \end{tikzpicture} \\

        Da wir nun bei einem Blatt angekommen sind, geben wir L aus und steigen eine Ebene im Baum auf zum M. &
        \footnotesize
        \begin{tikzpicture}[baseline, level distance=1cm,
                level/.style={sibling distance=2cm/#1},
                every node/.style={draw,circle,fill=white, text centered}]
            \node[draw=black!20,thick] (root) {\color{black!20}I}
                child {node[draw=black!20,thick] {\color{black!20}D}
                    child {node[draw=black!20,thick] {\color{black!20}B}
                        child {node[draw=black!20,thick] {\color{black!20}A}}
                        child[missing] {node {x}}
                    }
                    child {node[draw=black!20,thick] {\color{black!20}E}}
                }
                child {node[draw=red,fill=red!20,thick] {R}
                    child {node[draw=red,fill=red!20,thick] {M}
                        child {node[draw=blue,fill=blue!20,thick] {L}}
                        child[missing] {node {x}}
                    }
                    child {node {T}
                        child {node {S}}
                        child[missing] {node {x}}
                    }
                };
            \path[red,thick,draw,->] (root-2-1-1) -- (root-2-1);
            \path[black!20,thick,draw] (root-1-1-1) -- (root-1-1) -- (root-1) -- (root-1-2) -- (root-1) -- (root) -- (root-2);
        \end{tikzpicture} \\

        Ms rechter Teilbaum ist leer, demnach geben wir M aus und steigen auf zum R. &
        \footnotesize
        \begin{tikzpicture}[baseline, level distance=1cm,
                level/.style={sibling distance=2cm/#1},
                every node/.style={draw,circle,fill=white, text centered}]
            \node[draw=black!20,thick] (root) {\color{black!20}I}
                child {node[draw=black!20,thick] {\color{black!20}D}
                    child {node[draw=black!20,thick] {\color{black!20}B}
                        child {node[draw=black!20,thick] {\color{black!20}A}}
                        child[missing] {node {x}}
                    }
                    child {node[draw=black!20,thick] {\color{black!20}E}}
                }
                child {node[draw=red,fill=red!20,thick] {R}
                    child {node[draw=blue,fill=blue!20,thick] {M}
                        child {node[draw=black!20,thick] {\color{black!20}L}}
                        child[missing] {node {x}}
                    }
                    child {node {T}
                        child {node {S}}
                        child[missing] {node {x}}
                    }
                };
            \path[black!20,thick,draw] (root-1-1-1) -- (root-1-1) -- (root-1) -- (root-1-2) -- (root-1) -- (root) -- (root-2) -- (root-2-1) -- (root-2-1-1);
            \path[red,thick,draw,->] (root-2-1) -- (root-2);
        \end{tikzpicture} \\

        Da alle Elemente im linken Teilbaum von R ausgegeben wurden, geben wir R aus und steigen danach in den rechten Teilbaum von R ein. &
        \footnotesize
        \begin{tikzpicture}[baseline, level distance=1cm,
                level/.style={sibling distance=2cm/#1},
                every node/.style={draw,circle,fill=white, text centered}]
            \node[draw=black!20,thick] (root) {\color{black!20}I}
                child {node[draw=black!20,thick] {\color{black!20}D}
                    child {node[draw=black!20,thick] {\color{black!20}B}
                        child {node[draw=black!20,thick] {\color{black!20}A}}
                        child[missing] {node {x}}
                    }
                    child {node[draw=black!20,thick] {\color{black!20}E}}
                }
                child {node[draw=blue,fill=blue!20,thick] {R}
                    child {node[draw=black!20,thick] {\color{black!20}M}
                        child {node[draw=black!20,thick] {\color{black!20}L}}
                        child[missing] {node {x}}
                    }
                    child {node[draw=red,fill=red!20,thick] {T}
                        child {node[draw=red,fill=red!20,thick] {S}}
                        child[missing] {node {x}}
                    }
                };
            \path[black!20,thick,draw] (root-1-1-1) -- (root-1-1) -- (root-1) -- (root-1-2) -- (root-1) -- (root) -- (root-2) -- (root-2-1) -- (root-2-1-1);
            \path[red,thick,draw,->] (root-2) -- (root-2-2) -- (root-2-2-1);
        \end{tikzpicture} \\

        Wir kommen beim Blatt S an, geben es aus und steigen zum letzten verbleibenden Knoten T auf. &
        \footnotesize
        \begin{tikzpicture}[baseline, level distance=1cm,
                level/.style={sibling distance=2cm/#1},
                every node/.style={draw,circle,fill=white, text centered}]
            \node[draw=black!20,thick] (root) {\color{black!20}I}
                child {node[draw=black!20,thick] {\color{black!20}D}
                    child {node[draw=black!20,thick] {\color{black!20}B}
                        child {node[draw=black!20,thick] {\color{black!20}A}}
                        child[missing] {node {x}}
                    }
                    child {node[draw=black!20,thick] {\color{black!20}E}}
                }
                child {node[draw=black!20,thick] {\color{black!20}R}
                    child {node[draw=black!20,thick] {\color{black!20}M}
                        child {node[draw=black!20,thick] {\color{black!20}L}}
                        child[missing] {node {x}}
                    }
                    child {node[draw=red,fill=red!20,thick] {T}
                        child {node[draw=blue,fill=blue!20,thick] {S}}
                        child[missing] {node {x}}
                    }
                };

            \path[black!20,thick,draw] (root-1-1-1) -- (root-1-1) -- (root-1) -- (root-1-2) -- (root-1) -- (root) -- (root-2) -- (root-2-1) -- (root-2-1-1);
            \path[red,thick,draw,->] (root-2-2-1) -- (root-2-2);
        \end{tikzpicture} \\

        Anschließen geben wir T aus. Da Ts rechter Teilbaum leer ist, beenden wir die Ausgabe an dieser Stelle. &
        \footnotesize
        \begin{tikzpicture}[baseline, level distance=1cm,
                level/.style={sibling distance=2cm/#1},
                every node/.style={draw,circle,fill=white, text centered}]
            \node[draw=black!20,thick] (root) {\color{black!20}I}
                child {node[draw=black!20,thick] {\color{black!20}D}
                    child {node[draw=black!20,thick] {\color{black!20}B}
                        child {node[draw=black!20,thick] {\color{black!20}A}}
                        child[missing] {node {x}}
                    }
                    child {node[draw=black!20,thick] {\color{black!20}E}}
                }
                child {node[draw=black!20,thick] {\color{black!20}R}
                    child {node[draw=black!20,thick] {\color{black!20}M}
                        child {node[draw=black!20,thick] {\color{black!20}L}}
                        child[missing] {node {x}}
                    }
                    child {node[draw=blue,fill=blue!20,thick] {T}
                        child {node[draw=black!20,thick] {\color{black!20}S}}
                        child[missing] {node {x}}
                    }
                };

            \path[black!20,thick,draw] (root-1-1-1) -- (root-1-1) -- (root-1) -- (root-1-2) -- (root-1) -- (root) -- (root-2) -- (root-2-1) -- (root-2-1-1) -- (root-2-1) -- (root-2) -- (root-2-2) -- (root-2-2-1);
            \path[red,thick,draw,->] (root-2-2-1) -- (root-2-2);
        \end{tikzpicture} \\
    \end{longtblr}
    Die endgültige Ausgabe lautet demnach: A, B, D, E, I, L, M, R, S, T.

    Wir können den Algorithmus nun in eine umgangssprachliche (rekursive) Form bringen:
    \begin{smallitemize}
        \item Steige an der Wurzel in den Baum ein
        \item Mache für jeden Knoten -- von der Wurzel aus -- folgende Schritte:
        \begin{smallitemize}
            \item Steige in den linken Teilbaum ein und beginne für jeden Knoten diese Abfolge von Schritten. Ist der linke Teilbaum leer, gehe zum nächsten Schritt.
            \item Gib den Knoten aus.
            \item Steige in den rechten Teilbaum ein und beginne für jeden Knoten diese Abfolge von Schritten.
        \end{smallitemize}
    \end{smallitemize}
\end{loesung}

Im unteren Kasten sind einige Fragen aufgelistet, die Ihnen Anhaltspunkte liefern können, worauf Sie bei der Formulierung achten müssen.
\begin{nothelferBox}
    \begin{itemize}
        \item Welches Element ist das erste in der Liste? Welchen Weg müssen Sie zurücklegen, um dieses Element zu erreichen? Danken Sie dabei immer an die in \autoref{eigBinBaum} festgestellte Eigenschaft!
        \item Betrachten Sie den Teilbaum mit \enquote{David Guetta} als Wurzel. Bewegen Sie sich nun entlang der Kanten zum ersten Element, danach zum zweiten und so weiter. Was sagt dies über die Reihenfolge aus, die Sie bei der Ausgabe beachten mussten?
        \item Versuchen Sie bei Ihrem Algorithmus die Teilbäume eines Knotens in Betracht zu ziehen. Welchen der Teilbäume müssen Sie zuerst bearbeiten?
    \end{itemize}
\end{nothelferBox}

Diesen Algorithmus nennt man \emph{Inorder-Durchlauf}, da er die Knoten in der richtigen Reihenfolge (also \enquote{in order} ausgibt).

\newpage
\begin{lernkontrolleBox}
    Gegeben ist folgender binärer Baum:
    \begin{center}
        \begin{tikzpicture}[level distance=1.1cm,
                level/.style={sibling distance=5cm/#1},
                every node/.style={draw,circle,fill=white, text centered}]
            \node (root) {a}
                child {node {b}
                    child {node {d}
                        child {node {h}}
                        child {node {i}}
                    }
                    child {node {e}}
                }
                child {node {c}
                    child {node {f}
                        child[missing] {node {x}}
                        child {node {j}}
                    }
                    child {node {g}
                        child {node {k}}
                        child {node {l}}
                    }
                };
        \end{tikzpicture}
    \end{center}
    Die Buchstaben sind hier Stellvertreter für verschiedene vergleichbare Elemente, die auch nach der Eigenschaft aus Abschnitt \ref{eigBinBaum} angeordnet sind.

    Bearbeiten Sie die nachfolgenden Aufgaben:
    \begin{kontrollaufgabe}
        Die Blätter des Baums sind h, i, j, k und l.
        \begin{mcumgebung}
            \choice[\mcrichtig] Falsch
            \choice Richtig
        \end{mcumgebung}
    \end{kontrollaufgabe}
    \begin{kontrollloesung}
        \mcloesung Es fehlt e.
    \end{kontrollloesung}

    \begin{kontrollaufgabe}
        In einem binären Suchbaum findet man das größte Elemente, indem man so lange den Kanten nach rechts folgt, bis man ein Blatt erreicht hat.
        \begin{mcumgebung}
            \choice Falsch
            \choice[\mcrichtig] Richtig
        \end{mcumgebung}
    \end{kontrollaufgabe}
    \begin{kontrollloesung}
        \mcloesung
    \end{kontrollloesung}

    \begin{kontrollaufgabe}
        Die Nachfolger von b sind:
        \begin{mcumgebung}(2)
            \choice[\mcrichtig] d
            \choice[\mcrichtig] e
            \choice h
            \choice i
        \end{mcumgebung}
    \end{kontrollaufgabe}
    \begin{kontrollloesung}
        \mcloesung
    \end{kontrollloesung}

    \begin{kontrollaufgabe}
        Geben Sie die Reihenfolge an, in der die Knoten beim \enquote{Inorder-Durchlauf} besucht werden. Denken Sie daran, dass die eingetragenen Buchstaben nur Platzhalter sind!
    \end{kontrollaufgabe}
    \begin{kontrollloesung}
        h, d, i, b, e, a, f, j, c, k, g, l.
    \end{kontrollloesung}
\end{lernkontrolleBox}

\newpage

\begin{loesungenBox}
\end{loesungenBox}
\printsolutionstype[chapter=\thechapter]{aufgabe}

\paragraph{Lernkontrolle}$~$\\

\printsolutionstype[chapter=\thechapter]{kontrollaufgabe}