Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:adt:baeume:einfuehung:start [07.02.2022 14:51] – [Allgemeine Begriffe] sbel
+++ faecher:informatik:oberstufe:adt:baeume:einfuehung:start [26.11.2022 16:48] (aktuell) – Marco Kuemmel
@@ Zeile 1: / Zeile 1: @@
-{{ :faecher:informatik:oberstufe:adt:baeume:einfuehung:stammbaum_habsburg_baden.jpg?400|}}
+{{ :faecher:informatik:oberstufe:adt:baeume:einfuehung:stammbaum_habsburg_baden.jpg?300|}}
 ====== Bäume: Einführung ======
@@ Zeile 14: / Zeile 14: @@
 ----
-==== Allgemeine Begriffe ===
+===== 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:
+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.
+  * 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.
+  * 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)
+  * 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:*}}