home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
TCE Demo 2
/
TCE_DEMO_CD2.iso
/
demo_cd_.2
/
mags
/
atos
/
atos971f.arj
/
atos971f
/
SOURCEN
/
BINBAUM.C
< prev
next >
Wrap
C/C++ Source or Header
|
1997-02-01
|
4KB
|
129 lines
/*
* Quelltext zum ATOS-Artikel "Dynamische Datenstrukturen"
* ATOS 3/96, 5/96, 1/97
*
* Quelltext für einen binären Baum am Beispiel einer CD-Verwaltung.
*
* Autor: Hauke Wessels
*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "binbaum.h" /* struct's etc. */
void main(void)
{
exit(EXIT_SUCCESS); /* und tschüß */
}
int einfuegen(Knoten *wurzel, Knoten *eintrag) /* Datensatz einfügen in bin. Baum */
{
long erg;
erg = strcmp(wurzel->gruppe, eintrag->gruppe); /* Strings vergl. */
if (erg == 0) /* exakt gefunden? */
return(FALSE); /* dann nicht einfügen */
if (erg < 0) /* Eintrag ist kleiner */
{
if (wurzel->links == NULL) /* noch weitere Einträge*/
{
wurzel->links = eintrag; /* einfügen */
eintrag->links = NULL; /* zur Sicherheit ... */
eintrag->rechts = NULL; /* ... markieren */
return(TRUE); /* wurde eingefügt */
}
else
return(einfuegen(wurzel->links, eintrag)); /* links einfügen */
}
else
{
if (wurzel->rechts == NULL) /* noch weitere ... */
{ /* Einträge einthalten? */
wurzel->rechts = eintrag; /* einfügen */
eintrag->links = NULL; /* zur Sicherheit ... */
eintrag->rechts = NULL; /* ... markieren */
return(TRUE); /* wurde eingefügt */
}
else
return(einfuegen(wurzel->rechts, eintrag)); /* rechts einfügen */
}
} /* einfuegen */
int loeschen(Knoten **wurzel, char *gruppe) /* löscht ein Element aus dem Baum */
{
long erg; /* Hilfsvariable; Ergebnis des Stringvergleichs */
Knoten *hilf; /* Hilfszeiger */
if (*wurzel == NULL) /* Gruppe nicht gefunden? */
return(FALSE);
erg = strcmp((*wurzel)->gruppe, gruppe); /* Gruppe vergleichen */
if (erg < 0) /* Gruppe ist im linken Teilbaum */
return(loeschen(&(*wurzel)->links, gruppe)); /* Rekursion, die gruppe im linken Teilbaum löschen */
if (erg > 0) /* Gruppe ist im rechten Teilbaum */
return(loeschen(&(*wurzel)->rechts, gruppe)); /* Gruppe im rechten Teilbaum löschen */
if (erg == 0) /* Treffer? */
{
hilf = *wurzel;
if (hilf->rechts == NULL) /* kein rechtes Kind? */
{
*wurzel = hilf->links; /* dann einfach linken Teilbaum nehmen */
free(hilf); /* gelöschten Knoten wieder frei geben */
}
else
{
if (hilf->links == NULL) /* kein linkes Kind? */
{
*wurzel = hilf->rechts; /* dann einfach rechten Teilbaum nehmen */
free(hilf); /* Knoten-Speicher frei geben */
}
else /* sowohl linkes als auch rechtes Kind! */
{
ersatz_finden(&hilf->links, wurzel); /* nun müssen einige Äste umgehängt werden */
free(hilf); /* Knoten-Speicher frei geben */
}
}
}
return(TRUE);
}
void ersatz_finden(Knoten **knoten, Knoten **zu_loeschen) /* sucht den In-Order-Vorgänger und setzt ihn an die Stelle von *zu_loeschen */
{
Knoten *hilf;
hilf = *knoten;
if (hilf->rechts != NULL) /* rechter Sohn ist vorhanden? */
ersatz_finden(&hilf->rechts, zu_loeschen); /* vom linken Sohn das rechteste Blatt suchen (rek.) */
else
{
knoten = &hilf->links; /* linken Teilbaum des alten Kindes ersetzen */
hilf->links = (*zu_loeschen)->links; /* linken Teilbaum an Ersatz hängen */
hilf->rechts = (*zu_loeschen)->rechts; /* rechten Teilbaum an Ersatz hängen */
zu_loeschen = &hilf; /* Generationswechsel. das alte Kind wird nun Vater */
}
}
void traversieren(Knoten *wurzel) /* In-Order-Durchlauf durch den Teilbaum */
{
if (wurzel->links != NULL) /* gibt es einen linken Teilbaum */
traversieren(wurzel->links); /* dann erst mal in den linken Teilbaum gehen */
if (wurzel->rechts != NULL) /* gibt es einen rechten Teilbaum? */
traversieren(wurzel->rechts); /* dann den auch noch durchlaufen */
puts(wurzel->gruppe); /* und ausgeben */
}
Knoten *suche(Knoten *wurzel, char *key) /* sucht ein Element in dem bin. Suchbaum */
{
long erg;
erg = strcmp(wurzel->gruppe, key); /* Strings vergleichen */
if (erg < 0) /* kleiner? */
return(suche(wurzel->links, key)); /* im linken Teilbaum suchen */
if (erg > 0) /* größer? */
return(suche(wurzel->rechts, key)); /* im rechten Teilbaum suchen */
return(wurzel);
}