Löschen eines Elements im binären Baum

Schnelle objektorientierte, kompilierende Programmiersprache.
Antworten
Xeon
Beiträge: 169
Registriert: So Dez 17, 2017 4:10 pm

Löschen eines Elements im binären Baum

Beitrag von Xeon » Mi Mär 13, 2019 4:02 pm

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:
Du hast keine ausreichende Berechtigung, um die Dateianhänge dieses Beitrags anzusehen.

Benutzeravatar
cloidnerux
Moderator
Beiträge: 3123
Registriert: Fr Sep 26, 2008 4:37 pm
Wohnort: Ram (Gibts wirklich)

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

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

Redundanz macht wiederholen unnötig.
quod erat expectandum

Xeon
Beiträge: 169
Registriert: So Dez 17, 2017 4:10 pm

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

Beitrag von Xeon » Do Mär 14, 2019 3:11 pm

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:
Du hast keine ausreichende Berechtigung, um die Dateianhänge dieses Beitrags anzusehen.

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8858
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

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

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

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.
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

Xeon
Beiträge: 169
Registriert: So Dez 17, 2017 4:10 pm

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

Beitrag von Xeon » Do Mär 14, 2019 5:01 pm

Der Fehler hätte auffallen sollen, aber irgendwie habe ich ihn doch nicht gefunden. Vielen Dank Xin, du hast mir wieder sehr geholfen.

Antworten