Bäume
Bäume gehören zu den wichtigsten Datenstrukturen: Entscheidungsbäume, Syntaxbäume, Ableitungsbäume, Codebäume, Suchbäume, ...
Ein Baum ist
ein azyklischer einfacher, zusammenhängender Graph, d. h. er enthält keine Schleifen und Zyklen: zwischen jedem Paar von Knoten besteht höchstens eine Kante
Orientierter Baum: Ein orientierter Baum ist ein gerichteter, zusammenhängender und zyklenfreier Graph mit einem ausgezeichneten Knoten (Wurzel). Jeder Knoten im Graph ist von der Wurzel aus auf genau einem Weg erreichbar. (Vertikale Orientierung)
(Orientierte) Bäume sind verallgemeinerte Listenstrukturen:
Element (Knoten) hat i.a. mehrere Nachfolger (Söhne).
Wurzel: einziger Knoten ohne Vorgänger
Blätter: Knoten ohne Nachfolger
Verwendung von Bäumen zur Speicherung von Schlüsseln und Realisierung der Wörterbuchoperationen (Suchen, Einfügen, Entfernen) in Binärbäumen.