Algorithmen und Datenstrukturen in C/ Binäre Bäume

Während bei Listen, Stapeln und Arrays im ungünstigsten Fall das gesamte Array / die gesamte Liste durchsucht werden muss, um einen bestimmten Eintrag zu finden, liegen die Elemente eines binären Baumes immer sortiert vor. Die Einfügeoperation in eine solche dynamische Datenstruktur ist etwas aufwendiger, das Suchen geht aber im Allgemeinen etwas schneller von statten.

Die Datenstruktur

typedef struct _knoten
{
   struct _knoten *links, *rechts;
   int wert;
} knoten;

Ein binärer Baum hat zwei Nachfahren, einen linken und einen rechten Teilbaum. Ausserdem speichert er einen Wert, den wir hier mit einer ganzen Zahl beispielhaft andeuten.

Erzeugen eines Baumes

Ein einzelner Knotenpunkt wird wie folgt erzeugt:

knoten *baum;
baum = malloc(sizeof(knoten));
baum->links = NULL;
baum->rechts = NULL;
baum->wert = 10;

Wenn wir als Konvention vereinbaren, dass jeder linke Knoten kleiner ist als die Wurzel, und jeder rechte Knoten größer ist als die Wurzel, könnten wir einen Baum aufbauen, indem wir mit einem temporären Zeiger bis an die Stelle vorrücken, wo der Knoten eingefügt werden muss:

 void einfuegen (knoten **ganzer_baum, int neu_wert)
 {
   knoten *tmp, *neu_knoten;
   bool gefunden = false;
 
   tmp = (*ganzer_baum);
   while (!gefunden)
    {
       if (neu_wert < tmp->wert)
         {
           if (tmp->links != NULL) 
             tmp = tmp->links;
           else
             gefunden = true;
         }
       else if (neu_wert == tmp->wert)
         gefunden = true;
       else
         {
           if (tmp->rechts != NULL)
             tmp = tmp->rechts;
           else
             gefunden = true;
         }
     }
   if (neu_wert != tmp->wert)
     {
       neu_knoten = malloc (sizeof (knoten));
       neu_knoten->links = NULL;
       neu_knoten->rechts = NULL;
       neu_knoten->wert = neu_wert;
       if (neu_wert < tmp->wert)
         tmp->links = neu_knoten;
       else
         tmp->rechts = neu_knoten;
     }
 }

Solange gefunden nicht true ist, rücken wir vor bis zu der Stelle, wo wir unseren Knoten einfügen können. Selbstverständlich müssen wir dabei ständig auf der Hut sein, ob nicht

unser neu_wert gleich dem gespeicherten Wert ist oder
der linke oder rechte Nachfolger NULL ist.

Haben wir die richtige Stelle gefunden, können wir bequem einen neuen Zeiger neu_knoten erzeugen und ihn in den Baum einfügen.

Einen Baum der Gestalt

können wir mit folgendem Programm erzeugen:

 int main (void)
 {
   knoten *baum;
 
   baum = malloc (sizeof (knoten));
   baum->links = NULL;
   baum->rechts = NULL;
   baum->wert = 10;
 
   einfuegen (&baum, 2);
   einfuegen (&baum, 5);
   einfuegen (&baum, 17);
   einfuegen (&baum, 1);
  
   return 0;
 }

Durchlaufen eines Baumes

Einen binären Baum kann man auf mindestens drei Weisen durchlaufen (traversieren): preorder, inorder und postorder. Allen drei gemeinsam ist, dass die Vorschrift, wie der Baum zu durchlaufen ist, rekursiv beschrieben wird. Aus diesem Grund schieben wir ein Kapitel über Rekursionen ein:

Rekursion

Rekursion bedeutet im Zusammenhang mit Programmen und Funktionen sich selbst aufrufen. Eine rekursive Funktion ruft sich also selbst auf, um eine Berechnung durchzuführen. Ein Beispiel:

 /* Berechnet die Summe der Zahlen von...bis */
 #include <stdio.h>
 int Summe (int von, int bis)
 {
   if (von < bis)
     return von + Summe (von + 1, bis);
   else
     return von;
 }
 
 int main (void)
 {
   printf ("Summe = %d\n", Summe (0, 100));
   return 0;
 }

In diesem Beispiel bewirkt der Aufruf Summe(0, 100), dass die Summe der Zahlen von 0 bis 100 berechnet wird. Innerhalb der Funktion Summe (0, 100) passiert folgendes:

1. Schritt:

return von + Summe (von + 1, bis)

wird ersetzt durch

return 0 + Summe (1, 100)

2. Schritt

return 1 + Summe (2, 100)

...
98. Schritt:

return 99 + Summe (99 + 1, 100)

und im 100. Schritt:

return 100

Nun wird jeder Schritt wieder zurück verfolgt:

 return 1 + 2 + 3 + ... + Summe (98 + 1, 100) + Summe (99 + 1, 100)

ist

 return 1 + 2 + 3 + ... 98 + 99 + 100

ist

 return 5050

preorder

Einen Baum in Preorder-Reihenfolge zu durchlaufen bedeutet, zuerst das aktuelle Element auszugeben und dann nacheinander den linken und anschließend den rechten Teilbaum preorder zu durchlaufen.

 void preorder (knoten *k)
 {
   if (k == NULL)
     return;
   printf ("%d\n", k->wert);
   if (k->links != NULL)
     preorder (k->links);
   if (k->rechts != NULL)
     preorder (k->rechts);
 }

Obiger Baum würde folgendes Ergebnis ('\n' entfernt) liefern: 10 2 1 5 17

inorder

Dieses ist wohl die natürlichste Ausgabe, der Baum wird symmetrisch durchlaufen. Es wird zuerst der linke Teilbaum inorder durchlaufen, dann wird das aktuelle Element ausgegeben, anschließend wird der rechte Teilbaum inorder durchlaufen.

 void inorder (knoten *k)
 {
   if (k == NULL)
     return;
   if (k->links != NULL)
     inorder (k->links);
   printf ("%d\n", k->wert);
   if (k->rechts != NULL)
     inorder (k->rechts);
 }

Die Ausgabe mit obigem Baumbeispiel würde 1 2 5 10 17 lauten.

postorder

Die dritte Art, einen Baum zu durchlaufen heißt postorder und stellt die Ausgabe des aktuellen Elementes an das Ende der Baumdurchläufe für linken und rechten Teilbaum:

 void postorder (knoten *k)
 {
   if (k == NULL)
     return;
   if (k->links != NULL)
     postorder (k->links);
   if (k->rechts != NULL)
     postorder (k->rechts);
   printf ("%d\n", k->wert);
 }

Die Ausgabe würde 1 5 2 17 10 lauten.

Höhe eines Baumes

Die Höhe eines Baumes ist das Maximum der Höhe des linken und des rechten Teilbaumes plus 1. Somit ergibt sich folgender Code:

 int max (int a, int b)
 {
   return a > b ? a : b;
 }
 
 int hoehe (knoten *k)
 {
   if (k != NULL)
     return 1 + max (hoehe (k->links), hoehe (k->rechts));
   else
     return 0;
 }

Die Gesamthöhe unseres Beispielbaumes ist 3.

<< Stacks und Queues | Inhaltsverzeichnis