Binäre Bäume

Binäre Bäume
Ein voller, aber nicht vollständiger Binärbaum

Als Binärbaum bezeichnet man in der Graphentheorie eine spezielle Form eines Graphen. Genauer gesagt handelt es sich um einen gewurzelten Baum, bei dem jeder Knoten höchstens zwei Kindknoten besitzt. Oft wird verlangt, dass sich die Kindknoten eindeutig in linkes und rechtes Kind einteilen lassen. Ein anschauliches Beispiel für einen solchen Binärbaum ist die Ahnentafel. Hierbei sind allerdings die Elternteile die Kindknoten.

Ein Binärbaum ist entweder leer, oder er besteht aus einer Wurzel mit einem linken und rechten Teilbaum, die wiederum Binärbäume sind.

Inhaltsverzeichnis

Weitere Begriffe

Ein Binärbaum heißt geordnet, wenn jeder innere Knoten ein linkes und eventuell zusätzlich ein rechtes Kind besitzt (und nicht etwa nur ein rechtes Kind). Man bezeichnet ihn als voll, wenn jeder Knoten entweder Blatt ist (also kein Kind besitzt), oder aber zwei (also sowohl ein linkes wie ein rechtes) Kinder besitzt. Für die Eigenschaft voll werden gelegentlich auch die Begriffe saturiert oder strikt synonym verwendet. Man bezeichnet volle Binärbäume als vollständig, wenn alle Blätter die gleiche Tiefe (Anzahl übergeordneter Knoten) besitzen.

Induktiv lässt sich zeigen, dass ein vollständiger Binärbaum der Höhe h, den man häufig auch als Bh bezeichnet, genau

  • 2h+1-1 Knoten,
  • 2h-1 innere Knoten (Knoten, die keine Blätter sind),
  • 2i Knoten in Tiefe i, insbesondere also
  • 2h Blätter

besitzt, wobei mit Höhe h die Länge des Pfades zu einem tiefsten Knoten bezeichnet wird. Eine Darstellung eines Binärbaumes, in dem die Knoten mit rechtwinkligen Dreiecken und die Kanten mit Rechtecken dargestellt werden, nennt man pythagoreischen Binärbaum.

Der Binärbaum ist entartet, wenn jeder Knoten entweder Blatt ist (Anzahl Kinder ist 0) oder nur ein Kind besitzt. In diesem Fall stellt der Baum eine Liste dar. Besondere Formen sind die geordneten Listen, bei denen ein Baum jeweils nur aus linken oder nur aus rechten Kindern besteht.

Anwendungen

Viele Datenstrukturen wie beispielsweise binäre Suchbäume, AVL-Bäume, Fibonacci-Bäume und binäre Heaps basieren auf Binärbäumen.

Einige spezielle Binärbäume

Partiell geordneter Baum

Ein partiell geordneter Baum T ist ein spezieller Baum,

  • dessen Knoten markiert sind
  • dessen Markierungen aus einem geordneten Wertebereich stammen
  • in dem für jeden Teilbaum T' mit der Wurzel x gilt: Alle Knoten aus T' sind größer markiert als x oder gleich x.

Intuitiv bedeutet dies: Die Wurzel jedes Teilbaumes stellt ein Minimum für diesen Teilbaum dar. Die Werte des Teilbaumes nehmen in Richtung der Blätter zu oder bleiben gleich.

Derartige Bäume werden häufig in Heaps verwendet.

Vollständig balancierter Binärbaum

Ein vollständig balancierter Binärbaum ist ein voller Binärbaum, bei dem die Abstände zweier beliebiger Blätter von der Wurzel um höchstens 1 voneinander abweichen. (siehe auch Balancierter Baum oder AVL-Baum)

Traversierung

Traversierung bezeichnet das Untersuchen der Knoten des Baumes in einer bestimmten Reihenfolge. Ein Spezialfall ist die Linearisierung, bei der die Elemente in der Reihenfolge der Traversierung in eine Liste eingefügt werden.

Es gibt verschiedene Möglichkeiten, die Knoten von Binärbäumen zu durchlaufen. Man unterscheidet hier in

  • pre-order oder Hauptreihenfolge (W–L–R): wobei zuerst die Wurzel (W) betrachtet wird und anschließend zuerst der linke (L), dann der rechte (R) Teilbaum durchlaufen wird,
  • in-order oder symmetrische Reihenfolge (L–W–R): wobei zuerst der linke (L) Teilbaum durchlaufen wird, dann die Wurzel (W) betrachtet wird und anschließend der rechte (R) Teilbaum durchlaufen wird und
  • post-order oder Nebenreihenfolge (L–R–W): wobei zuerst der linke (L), dann der rechte (R) Teilbaum durchlaufen wird und anschließend die Wurzel (W) betrachtet wird.
  • level-order Beginnend bei der Wurzel, werden die Ebenen von links nach rechts durchlaufen.

Rekursive Implementierungen

Funktion Preorder(Baum)
	W <- Baum.Wurzel                    //W:= Wurzel des übergebenen Baumes
	If Baum.Links <> NULL               //Existiert ein linker Unterbaum?
		L <- Preorder(Baum.Links)   //  dann: L:= Preorder von linkem Unterbaum
	If Baum.Rechts <> NULL              //Existiert ein rechter Unterbaum?
		R <- Preorder(Baum.Rechts)  //  dann: R:= Preorder von rechtem Unterbaum
	Return W°L°R                        //Rückgabe: Verkettung aus W, L und R
Funktion Inorder(Baum)
	W <- Baum.Wurzel                    //W:= Wurzel des übergebenen Baumes
	If Baum.Links <> NULL               //Existiert ein linker Unterbaum?
		L <- Inorder(Baum.Links)    //  dann: L:= Inorder von linkem Unterbaum
	If Baum.Rechts <> NULL              //Existiert ein rechter Unterbaum?
		R <- Inorder(Baum.Rechts)   //  dann: R:= Inorder von rechtem Unterbaum
	Return L°W°R                        //Rückgabe: Verkettung aus L, W und R
Funktion Postorder(Baum)
	W <- Baum.Wurzel                    //W:= Wurzel des übergebenen Baumes
	If Baum.Links <> NULL               //Existiert ein linker Unterbaum?
		L <- Postorder(Baum.Links)  //  dann: L:= Postorder von linkem Unterbaum
	If Baum.Rechts <> NULL              //Existiert ein rechter Unterbaum?
		R <- Postorder(Baum.Rechts) //  dann: R:= Postorder von rechtem Unterbaum
	Return L°R°W                        //Rückgabe: Verkettung aus L, R und W

Siehe auch


Wikimedia Foundation.

Игры ⚽ Нужно решить контрольную?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Binäre Suche — Die binäre Suche ist ein Algorithmus, der auf einem Feld sehr effizient ein gesuchtes Element findet bzw. eine zuverlässige Aussage über das Fehlen dieses Elementes liefert. Voraussetzung ist, dass die Elemente in dem Feld entsprechend einer… …   Deutsch Wikipedia

  • Baum — azyklischer, zusammenhängender Graph * * * Baum [bau̮m], der; [e]s, Bäume [ bɔy̮mə]: großes Gewächs mit einem Stamm aus Holz, aus dem Äste wachsen, die sich in Zweige (mit Laub oder Nadeln) teilen: die Bäume schlagen aus, blühen, lassen ihre… …   Universal-Lexikon

  • Liste (Datenstruktur) — Die Verkettete Liste ist eine dynamische Datenstruktur, die eine Speicherung von einer im Vorhinein nicht bestimmten Anzahl von miteinander in Beziehung stehenden Objekten erlaubt. Sie wird durch Zeiger auf die jeweils folgende(n) Knoten oder… …   Deutsch Wikipedia

  • GLib — Entwickler Das GTK+ Team Aktuelle Version 2.30.2 (11. November 2011) Betriebssystem Unix, Windows, OS/2, BeOS …   Deutsch Wikipedia

  • Glib — Entwickler: Das GTK+ Team Aktuelle Version: 2.20.1 (12. April 2008) Aktuelle Vorabversion: 2.19.6 (2. Februar 2009) …   Deutsch Wikipedia

  • NTFS —   [Abk. für New Technology File System, dt. »Dateisystem für (Windows) NT«], das 1993 mit Windows NT von Microsoft eingeführte Dateisystem für Festplatten. Es geht auf das von Microsoft und IBM für das Betriebssystem OS/2 gemeinsam konzipi …   Universal-Lexikon

  • Doppelt verkettete Liste — Verkettete Listen gehören zu den dynamischen Datenstrukturen, die eine Speicherung von einer im Vorhinein nicht bestimmten Anzahl von miteinander in Beziehung stehenden Werten einfacher oder zusammengesetzter Datentypen erlauben. Sie werden durch …   Deutsch Wikipedia

  • Einfach verkettete Liste — Verkettete Listen gehören zu den dynamischen Datenstrukturen, die eine Speicherung von einer im Vorhinein nicht bestimmten Anzahl von miteinander in Beziehung stehenden Werten einfacher oder zusammengesetzter Datentypen erlauben. Sie werden durch …   Deutsch Wikipedia

  • Evl — Verkettete Listen gehören zu den dynamischen Datenstrukturen, die eine Speicherung von einer im Vorhinein nicht bestimmten Anzahl von miteinander in Beziehung stehenden Werten einfacher oder zusammengesetzter Datentypen erlauben. Sie werden durch …   Deutsch Wikipedia

  • Lineare Liste — Verkettete Listen gehören zu den dynamischen Datenstrukturen, die eine Speicherung von einer im Vorhinein nicht bestimmten Anzahl von miteinander in Beziehung stehenden Werten einfacher oder zusammengesetzter Datentypen erlauben. Sie werden durch …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”