Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen angezeigt.
| Beide Seiten der vorigen Revision Vorhergehende Überarbeitung Nächste Überarbeitung | Vorhergehende Überarbeitung | ||
| faecher:informatik:oberstufe:adt:baeume:einfuehung:start [07.02.2022 15:52] – sbel | faecher:informatik:oberstufe:adt:baeume:einfuehung:start [Unbekanntes Datum] (aktuell) – gelöscht - Externe Bearbeitung (Unbekanntes Datum) 127.0.0.1 | ||
|---|---|---|---|
| Zeile 1: | Zeile 1: | ||
| - | {{ : | ||
| - | |||
| - | ====== 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: | ||
| - | |||
| - | 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, | ||
| - | * 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 " | ||
| - | * 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: | ||
| - | |||
| - | {{ : | ||