#####____________________Binäre Bäume - Teil 2___________________

Zum Anfang des 2. Teiles über Binäre Bäume wollen wir die einzelnen Knoten die wir in dem Programm zuvor "erzeugt" haben besuchen bzw. in unserm Fall ausgeben. Man spricht dabei vom traversieren von Bäumen. Es gibt 2 Möglichkeiten die Bäume zu traversieren (besuchen)....

Die Preorder-Travesierung. Nehmen wir unseren Beispielbaum vom Kapitel zuvor....

Nach der Preorder-Travesierung würden wir zuerst den Knoten mit dem Wert 10 besuchen bzw. ausgeben. Anschließend den Knoten mit dem Wert 8. Als nächstes folgt der Knoten mit dem Wert 9. Als letztes wird der Knoten mit dem Wert 20 besucht bzw. ausgegeben. Diese Preorder - Taktik läuft wie folgt ab : Besuche den Knoten, dann besuche den linken Unterbaum, als nächstes besuche den rechten Unterbaum. Nun wollen wir noch die Funktion dazu schreiben....
```
void zeige_baum(KNOTEN *zeiger)
{
 if(zeiger != NULL)
  {
    printf("\n%d->",zeiger->wert);
    zeige_baum(zeiger->links);
    zeige_baum(zeiger->rechts);
   }
}  
```
Die zweite Möglichkeit ist die sogenannte Inorder - Travesierung. Bei dieser Möglichkeit würde um wieder auf unser Beispiel zurückzugreifen die Knoten in folgender Reihenfolge besucht.....

8->9->10->20
im Gegensatz zum Preorder.....
```
10->8->9->20  
```
Daraus läßt sich folgende Inorder - Taktik feststellen : Besuche den linken Unterbaum, dann besuche den Knoten, besuche den rechten Unterbaum. Somit würde unser Funktion wie folgt aussehen....
```
void zeige_baum(KNOTEN *zeiger)
{
 if(zeiger != NULL)
  {
    zeige_baum(zeiger->links);
    printf("\n%d->",zeiger->wert);
    zeige_baum(zeiger->rechts);
   }
}  
```
Also kaum eine Änderung als bei der Preorder - Travesierung nur das beim Inorder - Travesieren zuerst der am weitesten links unten liegende Knoten oder Blatt angefangen wird und beim Preorder zuerst bei der Wurzel.

Natürlich gibt es noch ein dritte Möglichkeit : Besuche den linken Unterbaum, besuche den rechten Unterbaum dann besuch die Wurzel. Auf Grund das sich dies als etwas Umständlicher bewerkstelligen lässt lassen wir diese Beispiel. Diese Methode benötigen wir eigentlich nur wenn wir Postfix - Notationen programmieren wollen. Da dies kein Mathmatik-Kurs sondern ein C-Kurs ist überlasse ich es denen die so etwas benötigen. Nur eines noch dazu wenn sie im Postorder - Verfahren den linken Unterbaum besuchen müssen den rechten Unterbaum und die Wurzel speichern. Wenn sie den rechten Unterbaum besuchen müssen sie die Wurzel speichern. Ein 4. Möglichkeit, die wir aber hier auch nicht erwähnen ist die Level-Order-Travesierung die aber nicht mehr rekursiv ist.

Nun kommen wir noch einem etwas komplizierteren Problem. Das löschen eines Elementes im Baum. Hier haben wir 3 Möglichkeiten....

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 (zeiger = zeiger->links && zeiger->rechts == NULL) oder (zeiger = zeiger->rechts && zeiger->links==NULL).
Die letzte Möglichkeit ist gleich die Schwierigste. Wir müssen einen Knoten löschen der 2 Nachfolger hat.

Zuerst benötigen wir eine Funktion die den zu löschenden Knoten sucht. Hier zuerst die Funktion.....

void loesche(KNOTEN **zeiger, int such) { if((*zeiger) == NULL) printf("Baum ist leer\n"); else if((*zeiger)->wert == such) //Gefunden! loesche_knoten(zeiger); else if((*zeiger)->wert >= such) loesche(&((*zeiger)->links),such); else loesche(&((*zeiger)->rechts),such); }

Der Funktion lösche werden dabei als Parameter die Wurzel (zeiger) und der zu suchende Wert (such) übergeben. Als erstes überprüfen wir ob überhaupt eine Wurzel vorhanden ist (if((*zeiger) == NULL)). Danach überprüfen wir ob wir unseren Wert schon gefunden haben (else if((*zeiger)->wert == such))

Wenn wir unseren Wert gefunden haben rufen wir die Funktion loesche_knoten() mit dem zeiger auf den gefundenen Wert. Diese Funktion werden in Kürze besprechen. Als nächstes (da wir den Knoten noch nicht gefunden haben) überprüfen wir ob der Wert auf den unser Zeiger zeiger zeigt grösser oder gleich unserem gesuchten Wert such ist (else if((*zeiger)->wert >= such)).

Ist dies der Fall ist der gesuchte Wert kleiner als der auf den unser Zeiger zeiger zeigt und muss sich somit auf der linken Seite des aktuellen Zeiger zeiger befinden (loesche(&((*zeiger)->links),such);). Hier erfolgt unser erster rekursiver Aufruf mit dem Adressoperator '&'

Die letzte else-Anweisung ergibt sich dadurch das unser gesuchter Wert größer als der ist, worauf unser Zeiger zeiger gerade zeigt. In diesem Fall suchen wir auf der rechten Seite weiter, somit unser zweiter rekursiver Aufruf (loesche(&((*zeiger)->rechts),such);)

Wir gehen jetzt mal davon aus das wir unseren Knoten gefunden haben womit die Funtkion loesche_knoten(zeiger) aufgerufen wird. Hier die Funktion......

void loesche_knoten(KNOTEN **zeiger)
{
  KNOTEN *temp;
  int tempwert;

  if(globale_wurzel==*zeiger)
   {
     printf("Kann die Wurzel nicht loeschen!!\n");
     return;
   }

  if((*zeiger)!=NULL)
   {
     if((*zeiger)->links==NULL && (*zeiger)->rechts==NULL) //Blatt!
       {
         free((*zeiger)->wert);
         free(*zeiger);
         *zeiger=NULL;
       }
     else if((*zeiger)->links==NULL) //Nur rechten Nachfolger
       {
         temp = *zeiger;
         *zeiger=(*zeiger)->rechts;
         free(temp->wert);
         free(temp);
       }
     else if((*zeiger)->rechts==NULL) //Nur linker Nachfolger
       {
          temp = *zeiger;
          *zeiger=(*zeiger)->links;
          free(temp->wert);
          free(temp);
       }
     else //2 Nachfolger, wir suchen Ersatzelement
       {
          suche_ersatz(&tempwert, &((*zeiger)->rechts));
          (*zeiger)->wert=tempwert;
       }
   }
}

Zuerst überprüfen wir ob unser gefundener Wert die Wurzel ist. In diesem Fall löschen wir kein Element und beenden die Funktion mit return (Dazu unten dann mehr). Nun überprüfen wir als erstes ob unser zu löschendes Element ein Blatt ist (ein Element ohne Nachfolger) mittels....

if((*zeiger)->links==NULL && (*zeiger)->rechts==NULL)

Falls es ein Blatt ist wird es entfernt ansonsten überprüfen wir in den nächsten beiden else-if-Anweisungen ob unser zu löschendes Element einen rechten oder linken Nachfolger hat. Die letzte und die schwierigste Möglichkeit ist das unser zu löschender Knoten zwei Nachfolger hat. Dafür benötigen wir wieder eine extra Funktion die für unseren zu löschenden Knoten ein Ersatzelement sucht......

else //2 Nachfolger, wir suchen Ersatzelement
  {
    suche_ersatz(&tempwert, &((*zeiger)->rechts));
    (*zeiger)->wert=tempwert;
..............

Wir suchen unser Ersatzelement auf der rechten Seite. Hier nun die Funktion suche_ersatz.......

void suche_ersatz(int *neuwert, KNOTEN **zeiger)
{
  KNOTEN *temp;

  if(*zeiger != NULL)
    {
      if((*zeiger)->links==NULL)
       {
         neuwert=(*zeiger)->wert;
         temp=*zeiger;
         *zeiger=(*zeiger)->rechts;
         free(temp->wert);
         free(temp);
       }
      else
        suche_ersatz(neuwert, &((*zeiger)->links));
    }
}

Die Funktion suche_ersatz läuft jetzt durch rekursiven Aufruf (suche_ersatz(neuwert, &((*zeiger)->links));) solange der linken Seite des Baumes hinab bis die Bedienung (if((*zeiger)->links==NULL)) wahr ist. Dann haben wir unser Ersatzelement gefunden und lassen den Zeiger *neuwert auf die Adresse des Ersatzelementes zeigen. Wenn sie nicht nachvollziehen können wieso die Funktion suche_ersatz zuerst mit der Adresse auf die rechte Seite aufgerufen und anschließend die komplette linke Seite hinabläuft, empfehle ich Ihnen das auf eine Blatt Papier zu zeichnen um es besser zu verstehen.

Hier nun das komplette Programm mit einigen zusätzlichen Funktionen......

baum1.c

Ich nehme mal an das es nicht einfach zu verstehen war. Und ich muss zugeben das ich das Thema binäre Bäume nur gestriffen habe. Denn was ist z.B. wenn wir als Wurzel den Wert 100 eingeben und es werden anschließend Werte kleiner wie 100 eingegeben. Somit befinden sich alle anderen Werte auf der linken Seite des Baumes. Wie sie einen ausgeglichenen binären Baum erstellen und noch vieles mehr zu diesem Thema können sie in dem Buch : Algorithmen in C von Robert Sedegewick nachlesen.

In späteren Kapiteln wenn es um Algorithmen geht werden wir die binären Bäume nochmals verwenden.