Binärbaum

Binärbaume

Begriffserklärung

Binärbaume sind in der Informatik eine Unterart von Bäumen. Diese Art von Bäumen können jeweils nur zwei nachfolgende Knoten haben. Ein Binärbaum ist entweder leer, oder besteht aus zwei Teilbäumen (einem linken und einen rechten).

mini|Beispiel eines typischen Binärbaums

Beschreibung des Beispiels

   Blätter und innere Knoten
   Als Blatt bezeichnet man denjenigen Knoten, der keine Nachfolger besitzt.
   Alle anderen Knoten heißen innere Knoten vom Baum B.

   Vorgänger und Nachfolger
   Ein Knoten y, der direkt unter einem Knoten x liegt, heißt Nachfolger von x.
   Umgekehrt heißt der Knoten x direkter Vorgänger von y.

   Grad und Kanten
   Die Zahl der direkten Nachfolger eines inneren Knotens ist sein (Verzweigungs-)Grad.
   Der höchste Grad unter allen Knoten ist der Grad des Baumes.
   Bäume vom Grad 2 heißen binär.
   Als Kanten bezeichnet man die Äste des Baumes.

Anwendung

Sie finden Anwendung in unterschiedlichen Bereichen:

       -als Suchbäume zum Finden von Elementen in geordneten Mengen
       -als Entscheidungsbäume zur Organisation sukzessiver Entscheidungen
       -als Datenstruktur zur Organisation eines Sortierprozesses

Quellen http://www.hs-augsburg.de/mebib/emiel/entw_inf/lernprogramme/baeume/gdi_kap_1bis3.html