Binärbaum
aus www.iwiki.de, der freien Wissensdatenbank
Eine besondere Ausprägung eines Baumes ist der sogenannte Binärbaum. Hierbei hat jedes Element genau zwei Nachfolger, die man als "linken Nachfolger" und "rechten Nachfolger" bezeichnet.
Eigenschaften von Binärbäumen
Ein Binärbaum
- ist entweder leer oder besteht aus einem Wurzelknoten, einem linken und einem rechten Teilbaum.
- heißt ausgeglichen, wenn für jeden Knoten gilt, dass sich die Anzahl der Knoten im linken Teilbaum maximal um eins von der Anzahl der Knoten im rechten Teilbaum unterscheidet.
Die Hauptanwendungen von Binärbäumen sind Suchbäume und die Darstellung arithmetischer Ausdrücke. Desweiteren wird ein Binärbaum auch als eine rekursive Datenstruktur (siehe Rekursion) bezeichnet.
Traversierung
Unter Traversierung bezeichnet man die Aufzählung aller Knoten eines (Binär-) Baumes in einer bestimmten Reihenfolge.
Es gibt drei Standardreihenfolgen beim Traversieren, deren Motivation und Bezeichnung sich am besten am Beispiel eines binären Operatorbaums klarmacht.
- Preorder: Man bearbeitet Wurzel bzw. Knoten vor linkem und rechtem Teilbaum
- Inorder: Man bearbeitet zuerst der linken Teilbaum, dann die Wurzel bzw. den Knoten, dann den rechten Teilbaum
- Postorder: Man bearbeitet zuerst den linken Teilbaum, dann den rechten Teilbaum, dann die Wurzel bzw. den Knoten
Bei einem binären Operatorbaum führen die Ausgabe der Knotenwerte beim Traversieren nach obigen Standardreihenfolgen zu folgenden Ergebnissen:
Beispiel:
- Preorder: Prefix-Notation des arithmetischen Ausdrucks: + 2 3
- Inorder: Infix-Notation: 2 + 3
- Postorder: Postfix-Notation: 2 3 +
Operationen auf Binärbäumen
Aufbau eines ausgeglichenen Baumes aus einer geordneten linearen Struktur (Umkehrung der Traversierung)
- Einen Binärbaum kann man leicht mithilfe einer rekursiven Methode (siehe Rekursion) erzeugen. Dabei wird beim Aufruf der rekursiven Methode die zu berechnete Tiefe übergeben. Sie gibt den Zeiger auf den Baum zurück.
- Wenn n Elemente zu speichern sind, ist die Tiefe m so zu wählen, dass n+1
2m + 1 gilt
Suchen eines Knoten mit einem bestimmten Wert (in Suchbäumen)
Suchen eines Knoten anhand seines Platzes in der "Hierarchie" (z.B. Pfad im Dateisystem)
Traversieren
- Durchlauf durch alle Knoten eines Baumes, z.B. um alle Knotenwerte auszugeben, oder um eine Operation auf allen Knotenwerten durchzuführen. Häufig ist eine bestimmte Durchlaufreihenfolge einzuhalten.
Einfügen eines Blattes
- Das Einfügen kann sehr leicht mit einer rekursiven Methode (siehe Rekursion) beschrieben werden. Dieser wird beim Aufruf der zu speichernden Inhalt und ein Zeiger auf den Knoten übergeben. Nur beim letzten rekursiven Aufruf wird dieser Zeiger verändert.
Das Erzeugen eines Blattes umfasst drei Aktionen:
- dem Anlegen des Speicherbereiches für die Struktur 'Knoten' (der übergebene Zeiger erhält die Anfangsadresse),
- dem Kopieren des Inhalts,
- dem Setzen beide Zeigerkomponenten des neuen Kindknotens auf 'NULL'.
Entfernen eines Knotens
Man muss folgende Situationen unterscheiden:
Grundsätzlich wird der Methode bei Aufruf der Ordnungsbegriff für den zu entfernenden Knoten übergeben. Sie liefert einen logischen Wert zurück, nämlich FALSE, wenn kein Knoten gefunden wurd, sonst TRUE.
- Entfernen eines Blattes
Der dafür belegte Speicherplatz wird zurückgegeben und der Verweis im Elternknoten auf NULL esetzt. Bei der Suche benötigt man also einen Zeiger auf das vorherige Element, den Elternknoten.
- Entfernen eines Knotens mit genau einem nicht leeren Teilbaum
Hat der zu entfernende Knoten gena einen gültigen Verweis auf einen Teilbaum, ist genau dieser Zeigerinhalt in den Verweis im Elternknoten an die Stelle zu übernehmen, an der bisher auf den zu löschenden Knoten verwiesen wurde
- Entfernen eines Knotens mit zwei nicht leeren Teilbäumen
Existieren unter dem zu entfernenden Knoten zwei (echte) Teilbäume, muss sicher gestellt werden, dass in diesem Knoten ein Element steht, das größer als alle anderen im linken Teilbaum und kleiner as alle anderen im rechten Teilbaum ist. Daher kann man entweder das größte Element des linken Teilbaumes oder das kleinste Element des rechten Teilbaumes in diesen Knoten übertragen. Anschließend ist dieser Knoten zu entfernen. Es kann nur ein Blatt oder ein Knoten mit genau einem nicht leeren Verweis sein.
Links
Literatur
- Bernd Breutmann: data and algorithms. Carl-Hanser-Verl., Leipzig 2001, ISBN 3-446-21591-3
- Michael Goodrich, Roberto Tamassia: Data Structures and Algorithms in Java 2nd Edition. John Wiley and Sons, New York 2001, ISBN 0-471-38367-8
Weblinks
- http://de.wikipedia.org/wiki/Binärbaum Wikipedia
