\begin{slide}{Baum-Durchquerungen}

Beispiel: Ausgabe von Operator-Ausdrücken:
\begin{verbatim}
void print (Knoten t) {
  if t ist Blatt { print (t.key); }
  else { print ( t.left );
         print ( t.key );
         print ( t.right );
       }              }
\end{verbatim}

Beispiel: Auswertung von Operator-Ausdrücken:
\begin{verbatim}
int wert (Knoten t) {
  if t ist Blatt { return t.eintrag; }
  else { int l = wert ( t.links );
         int r = wert ( t.rechts );
         return (l `t.key' r);
       }            }
\end{verbatim}

\end{slide}

\begin{slide}{Pre-, In-, Post-Order}

\begin{itemize}
\item pre-order: 
  Wurzel, linker Teilbaum, rechter Teilbaum
\item in-order: 
  linker Teilbaum, Wurzel, rechter Teilbaum
\item post-order: 
  linker Teilbaum, rechter Teilbaum, Wurzel
\end{itemize}

Ordne zu: Operator-Ausdruck drucken,
Türme von Hanoi, Operator-Ausdruck auswerten,
Erlaß einer Regierung bekanntgeben/umsetzen

(autotool) Rekonstruiere den binären Baum aus: \\
pre-order [5, 1, 7, 0, 9, 8, 2, 4, 3], \\
in-order  [7, 1, 0, 5, 2, 8, 4, 9, 3]


\end{slide}

\begin{slide}{Durchquerung ohne Rekursion}

In welcher Reihenfolge werden hier die Knoten besucht?
\begin{verbatim}
void besuch (Knoten<E> t) {
  Stack<Knoten<E>> s = new Stack<Knoten<E>> (); 
  s.push (t);
  while (! s.empty ()) {
    Knoten<E> x = s.pop ();
    print ( x.key );
    if x ist kein Blatt { 
      s.push (x.right);
      s.push (x.left);
 } } }
\end{verbatim}
\end{slide}


%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "informatik"
%%% End: 
