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.

Baum
Baum

Im Gegensatz zum «normalen» Baum, der in den Himmel wächst, werden die Baumstrukturen meistens nach unten dargestellt:

https://commons.wikimedia.org/wiki/File:BinärBaum_Beschriftung.jpg
Baumstruktur

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:

Baumstruktur
Baumstruktur