Seite 1 von 1

Löschen eines Elements im binären Baum

Verfasst: Mi Mär 13, 2019 4:02 pm
von Xeon
Hallo zusammen,

ich möchte ein Element im binären Baum löschen das zwei Nachfolger hat. Leider funktioniert es nicht ganz. Hier ist der link:

http://openbook.rheinwerk-verlag.de/c_v ... 102c324f2f

Ich glaube der Fehler ist in dieser Funktion

void suche_ersatz(int *neuwert, KNOTEN **zeiger)

Ich möchte z.B. die Zahl 40 löschen aber irgendwie funktioniert es nicht. Hier ist mein Baum:

Re: Löschen eines Elements im binären Baum

Verfasst: Mi Mär 13, 2019 7:26 pm
von cloidnerux

Re: Löschen eines Elements im binären Baum

Verfasst: Do Mär 14, 2019 3:11 pm
von Xeon
Entschuldigung, hier der Code:

Code: Alles auswählen

void loesche(KNOTEN **zeiger, int such) //Mit dieser Funktion wird der Wert gesucht zum löschen
{
   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);
}

Code: Alles auswählen


void loesche_knoten(KNOTEN **zeiger) //Hier wird ermittelt wie viel Nachfolger der Knoten hat
{								    
   KNOTEN *temp;
   int tempwert;

   if(globale_wurzel == *zeiger) {
      printf("Kann die Wurzel nicht loeschen!!\n");
      return;
   }
   if((*zeiger)!=NULL) { /* Blatt! */
      if((*zeiger)->links==NULL && (*zeiger)->rechts==NULL) {
         free(*zeiger);
         *zeiger=NULL;
      }
      else if((*zeiger)->links==NULL) {
         /* Nur rechter Nachfolger */
         temp = *zeiger;
         *zeiger=(*zeiger)->rechts;
         free(temp);
      }
      else if((*zeiger)->rechts==NULL) {
         /* Nur linker Nachfolger */
         temp = *zeiger;
         *zeiger=(*zeiger)->links;
         free(temp);
      }
      else { /* 2 Nachfolger, wir suchen Ersatzelement */
        suche_ersatz(&tempwert, &((*zeiger)->rechts));
        (*zeiger)->wert=tempwert;
      }
   }
}

Code: Alles auswählen

//Hier sollte der Knoten gelöscht werden der zwei Nachfolger hat z.B. 40
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);
      }
      else
         suche_ersatz(neuwert, &((*zeiger)->links));
   }
}
In dieser Funktion: void suche_ersatz(int *neuwert, KNOTEN **zeiger) möchte ich das der Wert 42, den Platz von 40 einnimmt und anschließend soll der Wert 42 gelöscht werden, aber auf dem Platz den die Zahl 42 einnehmen sollte kommt eine ganz andere Zahl heraus z.B.2000144914. Ich glaube der Fehler ist in dieser Funktion ist.

So sollte es grafisch aussehen:

Re: Löschen eines Elements im binären Baum

Verfasst: Do Mär 14, 2019 4:19 pm
von Xin

Code: Alles auswählen

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

   if(*zeiger != NULL) {
      if((*zeiger)->links==NULL) {
         neuwert=(*zeiger)->wert;
Wenn wert ein integer ist und neuwert ein int *, dann sollte hier mindestens eine Warnung rauskommen. Das sollte wohl *neuwert=(*zeiger)->wert; heißen.
Wenn das so kompiliert (und eine Warnung ignoriert wird), dann wird neuwert überschrieben, also die Adresse, wo der neue Wert hingeschrieben werden soll. Es wird an die Adresse, wo der neue Wert hingeschrieben werden soll, aber nix geschrieben.

Ich habe das Buch von Jürgen Wolf nicht und was ich von Jürgen Wolf habe, ist okay. Aber das C von A bis Z wird regelmäßig verrissen. Und ich könnte mir vorstellen, dass das eine der Gründe ist, denn eine Funktion "suche_ersatz", die gleichzeitig Knoten löscht, erscheint mir auch nicht ganz koscher.

Re: Löschen eines Elements im binären Baum

Verfasst: Do Mär 14, 2019 5:01 pm
von Xeon
Der Fehler hätte auffallen sollen, aber irgendwie habe ich ihn doch nicht gefunden. Vielen Dank Xin, du hast mir wieder sehr geholfen.