Bäume: Einführung

Bäume dienen als hierarchisches Strukturierungsmittel oder als Organsisationsprinzip - ein Beispiel ist der nebenstehende Stammbaum, in dem Johannes Gans versucht, fast alle europäischen Herrscherdynastien auf die Nachkommenschaft Rudolfs von Habsburg zurückzuverfolgen.1) Bildquelle: Johannes Gans: Arboretvm genealogicvm annotationibvs in arbores singvlas illvstratvm exhibens omnes fere imperii principes Evropae hodie reges linea recta descendentes a Rvdolpho I. Imperatore Köln, apvd Ioannem Kinchivm, 1638 (2. Auflage, 1. Auflage: Prag 1635). Public Domain https://commons.wikimedia.org/wiki/File:Gans_Stammbaum_Habsburg_Baden.jpg

Du kennst sicher weitere Beispiele, bei denen Daten und ihre Beziehungen zueinander als Baum strukturiert werden können.

(A1)

Finde 3 weitere Beispiele für baumartig strukturierte Daten und Zusammenhänge. Skizziere die jeweiligen Bäume in deinem Heft.

Allgemeine Begriffe

Allgemein besteht ein Baum (in der Informatik) aus Knoten und Kanten. Die Koinoten sind teilweies durch Kanten verbunden. Damit wir von einem Baum sprechen, dürfen die Knoten allerdings nicht in beliebiger Weise untereinander verbunden sein, sondern es müssen bestimmte Regeln eingehalten werden:

Jeder Knoten - außer dem Wurzelknoten - ist durch genau eine Kante mit seinem Elternknoten (Vaterknoten, Vorgänger)verbunden. Dieser Knoten wird häufig Kind oder Nachfolger des Elternknotens genannt.

Der Knoten ohne Elternknoten ist der Wurzelknoten. Jeder (nicht leere) Baum hat genau einen Wurzelknoten.

Ein Knoten der keine Kinderknoten hat heißt Blatt.

Knoten mit Eltern- und Kinderknoten heißen innere Knoten des Baums

Ein Pfad ist eine Abfolge von Knoten, die durch Kanten miteinander verbunden sind. Bei einem Baum gibt es zwischen dem Wurzelknoten und jedem anderen Knoten genau einen Pfad. (Bäume sind "zyklenfrei" und "zusammenhängend").

Das Niveau eines Knotens ist die Länge des Pfads vom Wurzelknoten zum betrachteten Knoten.

Die Höhe des Baums ist die Anzahl der Knoten im längsten Pfad des Baums (oder gleichbedeutend: Das größte Niveau eines Knotens im Baum +1)

In der Informatik zeichnet man Bäume aus praktischen Erwägungen von oben nach unten.

Wenn vorgegeben ist, welche (Maximal-)Zahl von Kinderknoten eine Knoten eines Baums haben darf, spricht man von einem n-ären Baum. Wenn die Kinder eines Knotens in einer bestimmten Reihenfolge geordnet sein müssen ("zuerst das linke Kind, dann das rechte"), spricht man von einem geordneten Baum.

Binärbaum

Ein sehr wichtiges Sonderfall, wen wir im weiteren betrachten werden ist der "2-äre" Baum, besser bezeichnet als binärer Baum oder Binärbaum.

Bei einem Binärbaum hat jeder Knoten höchstens 2 Kindsknoten

Es ist unterscheidbar, welches der linke und welches der rechte Kindsknoten ist.

(A2)

Bäume können dazu genutzt werden, Rechenausdrücke darzustellen, so dass sich Rechenregeln wie "Punkt vor Strich" in der Struktur wiederfinden.

Welcher Term ist durch den Baum rechts dargestellt?

Welche Höhe hat der Baum?

Was ist das größte Niveau eines Knotens in diesem Baum?

Handelt es sich um einen Binärbaum? Muss es sich um einen Binärbaum handeln, damit man Terme darstellen kann?

Muss der Baum geordnet sein? Begründe?

Skizziere den Baum für den Term (9+2-3)*3+7/(6-2)