{{ :faecher:informatik:oberstufe:adt:baeume:einfuehung:stammbaum_habsburg_baden.jpg?300|}}

====== 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.((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. 

----
{{:aufgabe.png?nolink  |}}
=== (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 Knoten sind teilweise 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.

{{ :faecher:informatik:oberstufe:adt:baeume:einfuehung:baumbegriffe.drawio.png |}}

Wenn vorgegeben ist, welche (Maximal-)Zahl von Kinderknoten ein 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 wichtiger Sonderfall, den 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.

----
{{:aufgabe.png?nolink  |}}
=== (A2) ===

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

{{ :faecher:informatik:oberstufe:adt:baeume:einfuehung:term.drawio.png|}}

  * 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)''

==== Material ====

{{simplefilelist>:faecher:informatik:oberstufe:adt:baeume:einfuehung:*}}