ein Kapitel zurück                                           ein Kapitel weiter

Die Binären Suchbäume dürften wohl als die Methode der Informatik angesehen werden. Sie haben binäre Bäume auch schon in einigen Kapiteln zuvor kennen gelernt. Sollten sie diese Lektionen bereits wieder vergessen haben, empfehle ich Ihnen diese Lektüre erneut zu lesen, da dies zum Verständnis dieser Kapitel dringend nötig ist, da wir auf die Einzelheiten wie eine Binärer Baum aufgebaut wird nicht mehr genauer eingehen werden.

Zuerst wollen wir unsere Grundlegende Knoten-Struktur für unseren Binären Baum festlegen.... 

struct binaer_knoten{
                      char ort[255];
                      unsigned int plz;
                      struct binaer_knoten *links;
                      struct binaer_knoten *rechts;
                    };

Jetzt noch die Struktur für unseren Baum..... 

struct binaer_baum{
                   struct binear_knoten *root;
                   unsigned int counter;
                  };

Nun eine Funktion mit der wir unseren Binären Baum initialisieren.... 

struct binaer_baum *init()
{
 /*dynamisch Speicher allokieren*/
 struct binaer_baum *baum = malloc(sizeof(*baum));
 if(baum == NULL) /*Speicher allokieren fehlgeschlagen ? */
   return NULL;
 else
  { /*Initialisieren*/
   baum->root = NULL;
   baum->counter=0;
   return baum;
  }
}

Als nächstes benötigen wir eine Funktion zum Einfügen einzelner Knoten im Binären Baum.... 

int einfuegen(struct binaer_baum *baum, int p, char o[])
{
 struct binaer_knoten *knoten, **neu;
 neu = &baum->root;
 knoten=  baum->root;

 for(;;)
  {
    if(knoten == NULL) /*Haben wir einen freien Platz gefunden?*/
     {
       knoten = *neu = malloc(sizeof(*knoten));
       if(knoten==NULL)
        return 0;
       else
        {
         /*Daten rein damit*/
         knoten->plz = p;
         strcpy(knoten->ort, o);
         knoten->links=knoten->rechts=NULL;
         baum->counter++;
        }
      }
    else if(p > knoten->plz) /*Ist die aktuelle Postleitzahl größer*/
      {
       /*Dann gehts recht weiter im Baum*/
       neu = &knoten->rechts;
       knoten = knoten->rechts;
      }
    else /*Der letzte Fall die aktuelle PLZ ist kleiner*/
      {
       /*dann eben nach links weiter im Baum*/
       neu = &knoten->links;
       knoten = knoten->links;
      }
   }
}

Unser Einfügen eines neues Elementes berücksichtigt übrigens keine doppelten Einträge. Dies können sie ja selbst nachtragen.

Jetzt wollen wir unser Suchfunktion verwenden. Wir fangen an der Wurzel (root) des Baumes an. Ist das gesuchte Element größer geht die Suche auf der rechten Seite des Baumes weiter. Ist das gesuchte Element kleiner suchen wir auf der linken Seite weiter. Bei einem optimal ausgeglichenem Baum führt dies zu optimalen Ergebnissen. Wir kommen noch zu diesem Thema. Hier nun die Suchfunktion, welche sich relativ einfach erstellen lässt..... 

void binaere_suche_plz(const struct binaer_baum *baum, unsigned int p)
{
 const struct binaer_knoten *knoten;
 /*Zuerst an die Wurzel*/
 knoten = baum->root;

 for(;;)
  {
    if(knoten == NULL)
     {
      printf("Keine erfolgreiche Suche!\n");
      return;
     }
    if(p == knoten->plz) /*Gefunden*/
     {
      printf("Ort zu Postleitzahl %d : %s\n",p,knoten->ort);
      return;
     }
    else if(p > knoten->plz) /*Gesuchtes Element größer*/
      knoten=knoten->rechts; /*Rechts am Baum weiter*/
    else /*Gesuchtes Element kleiner*/
      knoten=knoten->links;  /*Links am Baum weiter*/
   }
}

Mit dieser Funktion haben wir auch schon die Grundlage für das Löschen eines Elementes im Baum geschaffen nur das wir anstatt..... 

    if(p == knoten->plz) /*Gefunden*/
     {
      printf("Ort zu Postleitzahl %d : %s\n",p,knoten->ort);
      return;
     }

...ein break verwenden um nach der for-Schleife weiter Operationen durchzuführen.... 

    if(p == knoten->plz) /*Gefunden*/
       break;

Das Löschen eines Elements haben wir im Kapitel der Binären Bäume schon einmal angewendet. Da es aber zu diesem Kaptitel ebenfalls passt wollen wir uns die Funktion (etwas anders geschrieben) dazu auch ansehen.

Hierzu nochmals zur Erinnerung die 3 Möglichkeiten, die wir beim Löschen eines Elements aus einem Baum, überprüfen müssen.....

  • Die einfachste Form ist die Entfernung eines Blattes da dieses keinen Nachfolger mehr hat.
  • Die zweite Möglichkeit ist die Entfernung eines Knotens mit nur einem Nachfolger.
  • Die letzte Möglichkeit ist gleich die Schwierigste. Wir müssen einen Knoten löschen der 2 Nachfolger hat.

Und hierzu nun die Funktion zum löschen eines Elementes im binären Baum...... 

int bin_delete(struct binaer_baum *baum, unsigned int p)
{ /*pointer_z ist das zu löschende Element*/
 struct binaer_knoten **pointer_q, *pointer_z, *pointer_y,*pointer_x;

 pointer_q = &baum->root;
 pointer_z =  baum->root;

 for(;;)
  {
    if(pointer_z == NULL)
      return 0;
    else if(p == pointer_z->plz) /*zu löschendes Element gefunden*/
      break;
    else if(p > pointer_z->plz) /*löschende Element ist größer*/
     {
       pointer_q = &pointer_z->rechts; /*rechts weitersuchen*/
       pointer_z = pointer_z->rechts;
     }
    else /*Löschende Element ist kleiner*/
     {
       pointer_q = &pointer_z->links; /*links weitersuchen*/
       pointer_z = pointer_z->links;
     }
   }/*Hierher kommen wir nur durch break*/

 /*Jetzt müssen wir das zu löschende Element untersuchen*/

 /*pointer_z hat rechts keinen Nachfolger, somit können wir
          es austauschen mit dem linken Nachfolger.......*/
  if(pointer_z->rechts == NULL)
    *pointer_q = pointer_z->links;
  else
    {
 /*pointer_z hat einen rechten Nachfolger aber keinen Linken.*/
      pointer_y = pointer_z->rechts;
      if(pointer_y->links == NULL)
      /*pointer_z->rechts hat keinen linken Nachfolger....*/
       {
         pointer_y->links = pointer_z->links;
         *pointer_q = pointer_y;
       }
      else
       { /* es gibt einen linken Nachfolger*/
         pointer_x = pointer_y->links;
         /*Jetzt suchen wir solange bis es keinen linken Nachfolger mehr gibt*/
         while(pointer_x->links != NULL)
          {
            pointer_y = pointer_x;
            pointer_x = pointer_y->links;
          }
         /*Jetzt haben wir alle Punkte zusammen und könne diese Verknüpfen*/
        pointer_y->links = pointer_x->rechts;
        pointer_x->links = pointer_z->links;
        pointer_x->rechts = pointer_z->rechts;
        *pointer_q = pointer_x;
       }
      }
    /*Zu guter letzt könne wir pointer_z freigeben*/
   baum->counter--;
   free(pointer_z);
   return 1;
}

Zugegeben auf dem ersten Blick mag diese Funktionen etwas abschreckend wirken. Aber ein Tipp: Zeichnen sie sich einen binären Baum auf ein Blatt Papier und gehen sie diese Funktion mit dem Stift Schritt für Schritt durch. Sie werden sich Wundern wie einfach diese Funktion ist.

Zum guten Abschluss wollen wir uns noch einen kompletten Quellcode zu diesem Kapitel ansehen, bei dem sie alle Funktionen noch mal live sehen können...... 

/*Download:btree.c*/

#include <stdio.h>
#include <string.h>
#include <stdlib.h>


struct binaer_knoten{
                      char ort[255];
                      unsigned int plz;
                      struct binaer_knoten *links;
                      struct binaer_knoten *rechts;
                    };


struct binaer_baum{
                   struct binear_knoten *root;
                   unsigned int counter;
                  };


struct binaer_baum *init()
{
 /*dynamisch Speicher allokieren*/
 struct binaer_baum *baum = malloc(sizeof *baum);
 if(baum == NULL) /*Speicher allokieren fehlgeschlagen ? */
   return NULL;
 else
  { /*Initialisieren*/
   baum->root = NULL;
   baum->counter=0;
   return baum;
  }
}


int einfuegen(struct binaer_baum *baum, unsigned int p, char o[])
{
 struct binaer_knoten *knoten, **neu;
 neu = &baum->root;
 knoten=  baum->root;

 for(;;)
  {
    if(knoten == NULL) /*Haben wir einen freien Platz gefunden?*/
     {
       knoten = *neu = malloc(sizeof *knoten);
       if(knoten!=NULL)
        {
         /*Daten rein damit*/
         knoten->plz = p;
         strcpy(knoten->ort, o);
         knoten->links=knoten->rechts=NULL;
         baum->counter++;
         return 1;
        }
       else
        return 0;
      }
    else if(p > knoten->plz) /*Ist die aktuelle Postleitzahl größer*/
      {
       /*Dann gehts recht weiter im Baum*/
       neu = &knoten->rechts;
       knoten = knoten->rechts;
      }
    else /*Der letzte Fall die aktuelle PLZ ist kleiner*/
      {
       /*dann eben nach links weiter im Baum*/
       neu = &knoten->links;
       knoten = knoten->links;
      }
   }
}


void binaere_suche_plz(const struct binaer_baum *baum, unsigned int p)
{
 const struct binaer_knoten *knoten;
 /*Zuerst an die Wurzel*/
 knoten = baum->root;

 for(;;)
  {
    if(knoten == NULL)
     {
      printf("Keine erfolgreiche Suche!\n");
      return;
     }
    if(p == knoten->plz) /*Gefunden*/
     {
      printf("Ort zu Postleitzahl %d : %s\n",p,knoten->ort);
      return;
     }
    else if(p > knoten->plz) /*Gesuchtes Element größer*/
      knoten=knoten->rechts; /*Rechts am Baum weiter*/
    else /*Gesuchtes Element kleiner*/
      knoten=knoten->links;  /*Links am Baum weiter*/
   }
}

int bin_delete(struct binaer_baum *baum, unsigned int p)
{ /*pointer_z ist das zu löschende Element*/
 struct binaer_knoten **pointer_q, *pointer_z, *pointer_y,*pointer_x;

 pointer_q = &baum->root;
 pointer_z =  baum->root;

 for(;;)
  {
    if(pointer_z == NULL)
      return 0;
    else if(p == pointer_z->plz) /*zu löschendes Element gefunden*/
      break;
    else if(p > pointer_z->plz) /*löschende Element ist größer*/
     {
       pointer_q = &pointer_z->rechts; /*rechts weitersuchen*/
       pointer_z = pointer_z->rechts;
     }
    else /*Löschende Element ist kleiner*/
     {
       pointer_q = &pointer_z->links; /*links weitersuchen*/
       pointer_z = pointer_z->links;
     }
   }/*Hierher kommen wir nur durch break*/

 /*Jetzt müssen wir das zu löschende Element untersuchen*/

 /*pointer_z hat rechts keinen Nachfolger, somit können wir
           es austauschen mit dem linken Nachfolger.......*/
  if(pointer_z->rechts == NULL)
    *pointer_q = pointer_z->links;
  else
    {
 /*pointer_z hat einen rechten Nachfolger aber keinen Linken.*/
      pointer_y = pointer_z->rechts;
      if(pointer_y->links == NULL)
      /*pointer_z->rechts hat keinen linken Nachfolger....*/
       {
         pointer_y->links = pointer_z->links;
         *pointer_q = pointer_y;
       }
      else
       { /* es gibt einen linken Nachfolger*/
         pointer_x = pointer_y->links;
         /*Jetzt suchen wir solange bis es keinen linken Nachfolger mehr gibt*/
         while(pointer_x->links != NULL)
          {
            pointer_y = pointer_x;
            pointer_x = pointer_y->links;
          }
         /*Jetzt haben wir alle Punkte zusammen und könne diese Verknüpfen*/
        pointer_y->links = pointer_x->rechts;
        pointer_x->links = pointer_z->links;
        pointer_x->rechts = pointer_z->rechts;
        *pointer_q = pointer_x;
       }
      }
    /*Zu guter letzt könne wir pointer_z freigeben*/
   baum->counter--;
   free(pointer_z);
   return 1;
}


int main()
{
 struct binaer_baum *re;
 char o[255];
 unsigned int p;
 int wahl,r;
 re = init();
 if(re == NULL)
  {
    fprintf(stderr, "Konnte keinen neuen binären Baum erzeugen!\n");
    exit(0);
  }
 else
   fprintf(stdout, "Binärbaum konnte erfolgreich initialisiert werden!\n");

 do{
     printf("-1- Neue PLZ hinzufügen\n");
     printf("-2- PLZ suchen\n");
     printf("-3- PLZ löschen\n");
     printf("-4- Ende\n\n");
     printf("Ihre Wahl : ");
     scanf("%d",&wahl);

     if(wahl==1)
      {
       printf("Bitte geben sie eine neue PLZ ein : ");
       scanf("%d",&p);
       printf("Der Ort dazu : ");
       scanf("%s",&o);
       r=einfuegen(re,p,o);
       if(r==0)
        {
         fprintf(stderr, "Fehler beim Speicherallokieren!\n");
         exit(0);
        }
       }
      else if(wahl==2)
        {
          printf("Für welche PLZ suchen sie einen Ort : ");
          scanf("%d",&p);
          binaere_suche_plz(re,p);
         }
      else if(wahl==3)
        {
          printf("Welche PLZ wollen sie löschen : ");
          scanf("%d",&p);
          bin_delete(re,p);
         }
    }while(wahl != 4);

 return 0;
}

ein Kapitel zurück          nach oben           ein Kapitel weiter


© 2001,2002 Jürgen Wolf