Daten im Binärbaum ändern

[sesame]

Hallo,

hat jemand eine Idee, wie ich einen Datensatz in einem binären Suchbaum ändern kann?

Der Suchbaum funktioniert schon gut, nur bekomme ich die einmal eingelesenen Einträge nicht geändert (nicht löschen).

Die Struktur dazu:


struct binaer_knoten{
char name[MAX];
int nummer;
int bestand;
struct binaer_knoten *links;
struct binaer_knoten *rechts;
}var1;

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

struct binaer_baum *init(void) {
struct binaer_baum *baum =(struct binaer_baum *)
malloc(sizeof *baum);
if(baum == NULL) {
fprintf(stderr, "Speicherplatzmangel!\n");
return NULL;
}
else { /*Initialisieren*/
baum->root = NULL;
baum->counter=0;
return baum;
}
}

[anda_skoa]

Und wenn du uns jetzt noch den Code zum Löschen zeigst, können wir dir eventuell sogar sagen, warum es nicht geht und eine Fehlerbehebung vorschlagen :D

[sesame]

Eine Löschfunktion ist nicht notwendig. Es soll hier nur der Bestand geändert werden können. Dadurch bleibt der Datensatz an seiner Stelle stehen.

Wie kann ich also den Bestand eines Artikels ändern?
(Datei mit Daten vorausgesetzt: z.B. '100 Artikel1 233'.)

Hier das komplette Programm:

// Artikelverwaltung
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX 20


struct binaer_knoten{
int nummer;
char name[MAX];
int bestand;
struct binaer_knoten *links;
struct binaer_knoten *rechts;
}var1;

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

struct binaer_baum *init(void) {
struct binaer_baum *baum =(struct binaer_baum *) malloc(sizeof *baum);
if(baum == NULL) {
fprintf(stderr, "Speicherplatzmangel!\n");
return NULL;
}
else { /*Initialisieren*/
baum->root = NULL;
baum->counter=0;
return baum;
}
}

int einfuegen(struct binaer_baum *baum, int nummer, char *name, int bestand){
struct binaer_knoten *knoten, **neu;

neu =(struct binaer_knoten **) &baum->root;
knoten= (struct binaer_knoten *) baum->root;
for(;;) {
if(knoten == NULL) {
/* Haben wir einen freien Platz gefunden? */
knoten = *neu =
(struct binaer_knoten *)malloc(sizeof *knoten);
if(knoten != NULL) {
/* Daten rein damit */
knoten->nummer = nummer;
strcpy(knoten->name, name);
knoten->bestand = bestand;
knoten->links=knoten->rechts=NULL;
baum->counter++;
/* Beendet die Funktion erfolgreich */
return 1;
}
else {
fprintf(stderr, "Speicherplatzmangel\n");
return 0;
}
}
/* Ist die aktuelle Nummer größer */
else if(nummer > knoten->nummer) {
/* Dann gehts rechts weiter im Baum */
neu = &knoten->rechts;
knoten = knoten->rechts;
}
else { /* Der letzte Fall, die aktuelle Nummer ist kleiner */
/* dann eben nach links weiter im Baum */
neu = &knoten->links;
knoten = knoten->links;
}
}
}

void binaere_suche(const struct binaer_baum *baum, int nummer) {
const struct binaer_knoten *knoten;

/* Zuerst an die Wurzel */
knoten = (struct binaer_knoten *) baum->root;
for(;;) {
if(knoten == NULL) {
printf("Keine erfolgreiche Suche!\n");
return;
}
if(nummer == knoten->nummer) { /* Gefunden */
printf("Artikelnr.: %d \nName: %s\n", nummer, knoten->name);
printf("Bestand: %i\n\n", knoten->bestand);
return;
}
else if(nummer > knoten->nummer) /* Gesuchtes Element größer */
knoten=knoten->rechts; /* Rechts am Baum weiter */
else /* Gesuchtes Element kleiner */
knoten=knoten->links; /* Links am Baum weiter */
}
}

int main(void) {
struct binaer_baum *re;
char name[20];
int wahl, nummer, bearb, bestand;
FILE *file;
struct binaer_knoten *knoten;

printf("\nArtikelverwaltung\n");

re = init();
if(re == NULL) {
printf("Konnte keinen neuen binären Baum erzeugen!\n");
return 0;
}
else
printf("Binärbaum wurde erfolgreich Initialisiert\n");

if((file = fopen("artikel", "r")) != NULL) {
while(!feof(file)) {
fscanf(file, "%i", &nummer);
fscanf(file, "%s", &name[0]);
fscanf(file, "%i", &bestand);
einfuegen(re, nummer , name, bestand);
}
printf("o.k.\n");
}
else {
printf("Datei nicht gefunden.");}
fclose(file);

do {
printf("------------------------------\n");
printf("-1- Artikel suchen\n");
printf("-2- Artikel aendern\n");
printf("-3- Ende\n\n");
printf("Ihre Wahl : ");
printf("\n------------------------------\n");
scanf("%d", &wahl);

if(wahl == 1) {
printf("zu suchende Artikelnummer: ");
scanf("%i", &nummer);
binaere_suche(re, nummer);
}
else if(wahl == 2) {
printf("\nArtikelnummer eingeben: ");
scanf("%i", &nummer);

printf("\nBitte neuen Bestand des Artikels eingeben : ");
scanf("%i", &bestand);
binaere_suche(re, nummer);
knoten->bestand=bestand;
printf("Neuer Bestand: %i\n", knoten->bestand);
}

} while(wahl != 3);
return 0;
}

[panzi]

Mir war mal fad, deswegen hab ich einen AVL-Baum (http://de.wikipedia.org/wiki/AVL-Baum) (balancierter Binärbaum (http://de.wikipedia.org/wiki/Bin%C3%A4rbaum#Vollst.C3.A4ndig_balancierter_Bin.C 3.A4rbaum)) in C implementiert. Siehe dieses Blog-Posting (http://twoday.tuwien.ac.at/pub/stories/7589/).

Aber ist C++s std::map (http://www.sgi.com/tech/stl/Map.html) nicht eigentlich auch ein AVL-Baum?

[sesame]

geht leider nicht, ist ein studienprojekt und muss so umgesetzt werden.

[sesame]

so geht's:


int aendern( struct binaer_baum *baum, int nummer) {
struct binaer_knoten *knoten;

/* Zuerst an die Wurzel */
knoten = (struct binaer_knoten *) baum->root;
for(;;) {
if(knoten == NULL) {
printf("Keine erfolgreiche Suche!\n");
return;
}
if(nummer == knoten->nummer) { /* Gefunden */
printf("Artikelnr.: %d \nName: %s\n", nummer, knoten->name);
printf("\nneuen Bestand eingeben: ");
scanf("%i", &knoten->bestand);
printf("\nneuer Bestand: %i\n\n", knoten->bestand);
return;
}
else if(nummer > knoten->nummer) /* Gesuchtes Element größer */
knoten=knoten->rechts; /* Rechts am Baum weiter */
else /* Gesuchtes Element kleiner */
knoten=knoten->links; /* Links am Baum weiter */
}
return nummer;
}