Es gibt verschiedene Möglichkeiten, um aus einem Baum ein Array zu erzeugen. Zum Traversieren des Baums verwendet man die Tiefensuche oder die Breitensuche.
- Tiefensuche:
Die Tiefensuche bei Binärbäumen ist rekursiv definiert. Dabei wird ausgehend vom aktuellen Knoten der Baum in einen linken und rechten Teilbaum zerlegt. Je nachdem, ob der aktuelle Knoten vor, nach oder zwischen den Teilbäumen abgearbeitet wird, unterscheidet man zwischen pre-order, post-order oder in-order.- Pre-order: Zuerst wird der aktuelle Knoten im Array abgelegt. Dann wird der linke und zuletzt der rechte Teilbaum gemäß der pre-order Abfolge rekursiv abgearbeitet.
- Post-order: Zuerst wird der linke, dann der rechte Teilbaum gemäß der post-order Abfolge rekursiv durchlaufen. Dann wird der aktuelle Knoten im Array abgelegt.
- In-order: Zuerst erfolgt der rekursive Abstieg gemäß der in-order Abfolge im linken Teilbaum. Dann wird der aktuelle Knoten im Array abgelegt und zuletzt erfolgt der rekursive Abstieg gemäß der in-order Abfolge im rechten Teilbaum.
- Breitensuche (level-order):
Bei diesem Verfahren wird der Baum beginnen mit dem Wurzelknoten Ebene für Ebene durchlaufen.
Beispiel:
Beim Traversieren der Bäume gemäß der angegebenen Ordnung ergibt sich die Zeichenkette “HelloWorld”.
Pre-Order:
H
/ \
/ \
/ \
e r
/ \ / \
/ \ / \
l W l d
/ \ /
l o o
Post-Order:
d
/ \
/ \
/ \
W l
/ \ / \
/ \ / \
l o o r
/ \ /
H e l
In-Order:
o
/ \
/ \
/ \
l l
/ \ / \
/ \ / \
e W r d
/ \ /
H l o
Mehr dazu: Wikipedia Binärbaum