\documentclass[loesungsseite]{schuleab}
\usepackage[utf8]{inputenc}
\usepackage{schulinf}

% Dieses Dokument ist in der Zusammenarbeit von Informatikreferendaren und
% ehemaligen Informatikreferendaren der Studienseminare (heute ZfsL) Arnsberg,
% Hamm und Solingen entstanden.
%
% Das Dokument steht unter der Lizenz: Creative Commons by-nc-sa Version 4.0
% http://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
% http://ddi.uni-wuppertal.de/material/materialsammlung/
% zur Verfügung.
%
% Das LaTeX-Paket zum Setzen der Dokumente der Sammlung steht
% unter  http://www.ctan.org/pkg/schule
% zur Verfügung.

\usepackage[pdfauthor={Referendare der Informatikfachseminare Arnsberg, Hamm und Solingen}]{hyperref}
\includexmp{lizenz}
\cclizenz{byncsaeu}
\footerQRLink{materialsammlung_qr_url.pdf}

\svnid{$Id: ab_03_traversierung.tex 1254 2015-06-13 16:22:07Z pieper $}

\dokName{Traversierung}
\jahrgang{Q1}

\begin{document}

\section*{Traversierung}

Es gibt Fälle, in denen man alle Elemente eines Baumes in eine lineare Liste 
bringen möchte. Dabei kommt es entscheidend darauf an, in welcher Reihenfolge 
die Elemente im Baum in die Liste eingefügt werden. Die unterschiedlichen 
Reihenfolgen führen zu verschiedenen Arten der sogenannten Traversierung. 
Zur Verdeutlichung wird der folgende Baum herangezogen:

\begin{center}
	\begin{tikzpicture}
	[level distance=8mm,level/.style={sibling distance=2cm/#1}]

	\node{D} 
		child {node {B} 
			child{node{A}}
			child{node {C}}
		}
		child {node {E}};
	\end{tikzpicture}
\end{center}

\begin{description}
	\item[Pre-Order (W-L-R)] Bei dieser Traversierung, auch Tiefensuche genannt, wird zuerst die Wurzel (W) betrachtet. Anschließend wird der linke (L) und dann der rechte (R) Teilbaum durchlaufen. Das Beispiel liefert dann: D B A C E.
	\item[Post-Order (L–R–W)] Diese trägt auch den Namen Nebenreihenfolge. Bei ihr wird als erstes der linke (L) und dann der rechte (R) Teilbaum durchlaufen. Zum Schluss wird die Wurzel (W) betrachtet. Das Beispiel liefert dann: A C B E D.
	\item[In-Order (L-W-R)] Bei ihr spricht man auch von der symmetrischen Reihenfolge. Es wird der linke (L) Teilbaum durchlaufen. Danach folgt die Wurzel (W) und am Ende der rechte (R) Teilbaum. Das Beispiel liefert dann: A B C D E.
\end{description}

\subsection*{Aufgaben}
\begin{enumerate}
	\item Traversieren Sie die folgenden Bäume mit allen drei Traversierungsarten.
	\begin{center}
		\begin{tikzpicture}
		[level distance=8mm,level/.style={sibling distance=1.7cm/(#1-0.4)}]

		\node(A) {G} 
			child {node {D} 
				child{node{J}}
				child{node {C}}
			}
			child {node {X}
				child {node {L}}
				child {node{W}
					child{node{B}}
					child{node{M}}
				}
			};

		\node [right=of A, xshift=4.5cm] {W} 
			child {node {G} 
				child{node{A}}
				child{node {D}
					child{node{X}}
					child{node{Y}
						child[missing]{}
						child{node{Z}}
					}
				}
			}
			child {node {S}
				child {node {T}
					child {node {N}}
					child[missing]{}
				}
				child {node{M}
					child{node{L}}
					child[missing]{}
				}
			};
		\end{tikzpicture}
	\end{center}
	\item Ein Baum wurde Post-Order traversiert. Das Ergebnis 
	  lautet G D V Z H K L Q W E R. Geben Sie einen Ursprungsbaum an, der dieses 
	  Ergebnis liefert.
\end{enumerate}

\loesung{
	\begin{enumerate}
		\item Pre-Order: G D J C X L W B M und W G A D X Y Z S T N M L \\
			Post-Order: J C D L B M W X G und A X Z Y D G N T L M S W \\
			In-Order: J D C G L X B W M und A G X D Y Z W N T S L M
		\item Für die Ausgabe gibt es mehrere Möglichkeiten, wie der Ausgangsbaum ausgesehen haben kann. 
	\end{enumerate}
}

\textbf{Hinweis:} Es gibt noch zwei weitere bekannte Möglichkeiten:
\begin{description}
	\item[Reverse In-Order (R–W–L)] Bei dieser anti-symmetrischen Reihenfolge wird zuerst der rechte (R) Teilbaum durchlaufen. Darauf folgt die Betrachtung der Wurzel (W) und am Ende der linke (L) Teilbaum. Das Beispiel liefert: E D C B A.
	\item[Level-Order] Sie ist auch bekannt unter dem Namen Breitensuche. Bei ihr werden beginnend an der Baumwurzel alle Ebenen von links nach rechts durchlaufen. Das Beispiel liefert: D B E A C.
\end{description}



\end{document}
