Bäume und Baumsuche
Die Datenstruktur «Baum» trifft man in der Informatik immer wieder an. So stellt z.B. ein hierarchisches Dateisystem mit Ordner, Unterordner und Dateien eine Baumstruktur dar.
Im Gegensatz zum «normalen» Baum, der in den Himmel wächst, werden die Baumstrukturen meistens nach unten dargestellt:
Ein Baum besteht aus Knoten (engl. Nodes) – das sind die Start-, End- und Verzweigungspunkte und Kanten (engl. Edges) – das sind die Verbindungen zwischen den Knoten. Dem obersten Knoten sagt man auch Wurzel (engl. root) und den Endknoten – dort wo keine weiteren Knoten mehr kommen – sagt man Blätter (engl. leaves).
Suche im Baum
Zwei wichtige Möglichkeiten sind die Tiefen- und die Breitensuche. Bei der Breitensuche wird der Baum Ebene für Ebene durchsucht, während bei der Tiefensuche von der Wurzel her so tief wie möglich entlang eines Pfads vorgedrungen wird, bevor ein anderer Ast ausprobiert wird.
Zeichne in den folgenden Baum mit verschiedenen Farben den Suchpfad ein für Tiefensuche und Breitensuche:
