Ein Binärbaum ist in der Graphentheorie ein gewurzelter Baum, genauer ein Out-Tree, bei dem jeder Knoten höchstens zwei Kinder besitzt. Oft wird verlangt, dass sich die Kinder eindeutig in linkes und rechtes Kind einteilen lassen.

Weitere Begriffe

Ein Binärbaum heißt geordnet, wenn jeder innere Knoten ein linkes und eventuell zusätzlich ein rechtes Kind besitzt (und nicht etwas nur ein rechtes Kind). Man bezeichnet ihn als voll, wenn jeder Knoten entweder Blatt ist (also kein Kind besitzt) oder aber 2 (also sowohl ein linkes wie ein rechtes) Kinder besitzt. Man bezeichnet ihn als vollständig, wenn alle Blätter die gleiche Tiefe besitzen. Induktiv lässt sich zeigen, dass ein vollständiger Binärbaum der Höhe n, den man häufig auch als B_n bezeichnet, genau

• 2ⁿ-1 Knoten,
• 2ⁱ Knoten in Tiefe i, insbesondere also
• 2ⁿ Blätter und
• 2²ⁿ-1 innere Knoten

besitzt.

Eine Darstellung eines Binärbaumes, in dem die Knoten mit rechtwinkligen Dreiecken und die Kanten mit Rechtecken dargestellt werden, nennt man pythagoräischen Binärbaum.

Anwendungen

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

Linearisierung von Binärbäumen

Es gibt verschiedene Möglichketen die Knoten von Binärbäumen zu Durchlaufen. Diesen Prozess nennt man auch Linarisieren. Man unterscheidet hier in

• pre-order (W - L - R): wobei zuerst die Wurzel (W) betrachtet wird und anschließend zuererst der linke (L), dann der rechte (R) Teilbaum durchlaufen wird,
• in-order (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 (L - R - W): wobei zuererst der linke (L), dann der rechte (R) Teilbaum durchlaufen wird und anschließend die Wurzel (W) betrachtet wird.

siehe auch: Linearisierung von Binärbäumen