Mit Google fortfahren
Binärbaum: Aufbau, Traversierung und Suchbaum
Ein Binärbaum ordnet Daten hierarchisch: Jeder Knoten hat höchstens ein linkes und ein rechtes Kind. Diese Struktur allein sagt noch nichts über die Reihenfolge der gespeicherten Werte aus. Erst ein binärer Suchbaum ergänzt eine Ordnungsregel.
Auf dieser Seite lernst du, einen Binärbaum zu beschreiben, seine Höhe eindeutig anzugeben, Knoten in verschiedenen Reihenfolgen zu durchlaufen und ihn von einem binären Suchbaum zu unterscheiden.
Hake ab, was du schon kannst — und komm am Ende hierher zurück!
Woran erkennst du einen Binärbaum?
Stell dir eine Ordnerstruktur vor, in der jeder Eintrag höchstens zwei direkte Untereinträge haben darf. Genau diese Begrenzung ist die Kernidee eines Binärbaums. „Binär“ bedeutet hier also höchstens zwei Kinder pro Knoten — nicht „genau zwei“.
Binärbaum
Ein Binärbaum ist entweder leer oder besteht aus einer Wurzel, einem linken Teilbaum und einem rechten Teilbaum. Beide Teilbäume sind wiederum Binärbäume. Linkes und rechtes Kind werden unterschieden.
Die wichtigsten Bauteile sind:
- Die Wurzel ist der oberste Einstiegspunkt. Sie hat keinen Elternknoten.
- Ein Knoten speichert einen Wert oder andere Informationen.
- Eine Kante verbindet einen Elternknoten mit einem Kind.
- Ein Blatt ist ein Knoten ohne Kinder.
- Ein innerer Knoten besitzt mindestens ein Kind.
- Ein Teilbaum besteht aus einem Knoten und allen darunterliegenden Knoten.
Ein einzelner Wurzelknoten ist bereits ein Binärbaum. Er ist zugleich Wurzel und Blatt. Auch ein Knoten mit nur einem Kind ist erlaubt.
Betrachte diesen Baum: Die Wurzel ist 20. Ihre Kinder sind links 10 und rechts 30. 10 hat die Kinder 5 und 15; 30 hat die Kinder 25 und 35.
Der Baum besitzt 7 Knoten und 6 Kanten. Die Blätter sind 5, 15, 25 und 35. Der Teilbaum mit der Wurzel 10 enthält die Knoten 10, 5 und 15.
Wie misst du Tiefe, Höhe und Größe?
Die Größe ist einfach die Anzahl aller Knoten. Bei Tiefe und Höhe musst du genauer hinsehen, weil Lehrwerke die Höhe unterschiedlich zählen.
Tiefe
Die Tiefe eines Knotens ist die Anzahl der Kanten auf dem Weg von der Wurzel zu diesem Knoten. Die Wurzel hat daher Tiefe 0.
Wenn du die Höhe als Kantenanzahl misst, ist die Höhe eines Knotens die Länge seines längsten Weges hinunter zu einem Blatt. Die Baumhöhe ist dann die Höhe der Wurzel und zugleich die größte Knotentiefe.
Beim Beispielbaum liegt die Wurzel in Tiefe 0, 10 und 30 liegen in Tiefe 1, die vier Blätter in Tiefe 2. Die Baumhöhe beträgt bei der Kantenzählung also 2.
Manche Darstellungen zählen stattdessen die Ebenen. Dann hat derselbe Baum 3 Ebenen und damit Ebenenhöhe 3. Schreibe deshalb immer dazu, welche Konvention du verwendest.
Kantenzählung: Ein Einzelknotenbaum hat Höhe 0. Ebenenzählung: Derselbe Baum hat Höhe 1. Beide Angaben können korrekt sein, wenn die Konvention genannt ist.
Für einen im engen Sinn vollständigen Binärbaum sind alle Ebenen voll besetzt und alle Blätter gleich tief. Hat er bei Ebenenzählung die Höhe $h$, dann gilt:
$$n=2^h-1$$
Bei 3 Ebenen enthält der Baum $2^3-1=7$ Knoten. Das passt zum Beispielbaum: 1 Knoten auf der ersten, 2 auf der zweiten und 4 auf der dritten Ebene.
Wähle in jeder Lücke die passende Form und prüfe anschließend deine Antworten.
Im Beispielbaum hat die Wurzel die Tiefe . Das Blatt 25 hat die Tiefe . Bei Kantenzählung beträgt die Baumhöhe ; bei Ebenenzählung beträgt sie .
Wie besuchst du alle Knoten?
Eine Traversierung besucht jeden Knoten systematisch genau einmal. Bei den drei Tiefensuchen bleibt die Reihenfolge der Teilbäume gleich: links vor rechts. Nur der Zeitpunkt, an dem der aktuelle Knoten verarbeitet wird, ändert sich.
| Verfahren | Kurzregel | Reihenfolge im Beispiel |
|---|---|---|
| Preorder | Knoten – links – rechts | 20, 10, 5, 15, 30, 25, 35 |
| Inorder | links – Knoten – rechts | 5, 10, 15, 20, 25, 30, 35 |
| Postorder | links – rechts – Knoten | 5, 15, 10, 25, 35, 30, 20 |
| Level-order | Ebene für Ebene, links nach rechts | 20, 10, 30, 5, 15, 25, 35 |
So entsteht die Inorder-Folge des Beispielbaums:
- Durchlaufe zuerst den linken Teilbaum von
20:5, 10, 15. - Verarbeite die Wurzel
20. - Durchlaufe danach den rechten Teilbaum:
25, 30, 35.
Zusammen ergibt das 5, 10, 15, 20, 25, 30, 35.
N steht für den aktuellen Knoten, L für den linken und R für den rechten Teilbaum: Preorder ist N–L–R, Inorder L–N–R und Postorder L–R–N.
Wann wird daraus ein binärer Suchbaum?
Ein allgemeiner Binärbaum begrenzt nur die Kinderzahl. Ein binärer Suchbaum ordnet zusätzlich seine Schlüssel.
Binärer Suchbaum
Für jeden Knoten gilt: Alle Schlüssel im linken Teilbaum sind kleiner als der Schlüssel des Knotens, alle Schlüssel im rechten Teilbaum sind größer. Diese Regel gilt rekursiv in jedem Teilbaum.
Wie gleiche Schlüssel behandelt werden, muss eine Implementierung eigens festlegen: Sie kann Duplikate ablehnen oder sie nach einer konsistenten Regel einer Seite zuordnen. Für die folgenden Beispiele kommen keine Duplikate vor.
Suchen
Suche im Beispielbaum nach 25:
- Vergleiche mit
20. Weil25 > 20, gehe nach rechts. - Vergleiche mit
30. Weil25 < 30, gehe nach links. - Dort findest du
25.
Du musst nicht beide Teilbäume durchsuchen. Die Ordnungsregel entscheidet bei jedem Vergleich, auf welcher Seite die Suche weitergeht.
Einfügen
Füge 27 ein:
27 > 20: gehe rechts zu30.27 < 30: gehe links zu25.27 > 25: Der rechte Kindverweis von25ist frei.- Erzeuge dort den neuen Knoten
27.
Der neue Knoten ist zunächst ein Blatt. Die Suchbaumordnung bleibt erhalten.
Warum die Höhe wichtig ist
Suchen und Einfügen folgen jeweils einem Weg von der Wurzel nach unten. Ihr Aufwand hängt deshalb von der Höhe $h$ ab und beträgt $O(h)$.
Ein ausgeglichener Baum kann bei vielen Knoten eine logarithmische Höhe haben. Werden Schlüssel dagegen einseitig eingefügt, kann der Baum zu einer listenartigen Kette entarten. Dann wächst die Höhe mit der Knotenzahl, und der Suchvorteil geht im schlechtesten Fall verloren.
Eine verkettete lineare Liste besitzt pro Element typischerweise einen Verweis zum nächsten Element. Ein Binärbaumknoten benötigt Verweise auf linkes und rechtes Kind. Dafür kann die Suchbaumordnung bei günstiger Höhe viele Elemente überspringen, während eine unsortierte Liste im schlechtesten Fall Element für Element geprüft wird.
Karteikasten
Überlege zuerst selbst und drehe die Karte anschließend zum Prüfen um.
Alles auf einen Blick
- Binärbaum
- Struktur: Wurzel, Knoten, Kanten, Teilbäume und Blätter
- Begrenzung: höchstens zwei unterscheidbare Kinder
- Maße: Größe, Tiefe und Höhe
- Traversierung: Preorder, Inorder, Postorder und Level-order
- Suchbaum: zusätzliche Schlüsselordnung
- Laufzeit: Suchweg hängt von der Höhe ab