home *** CD-ROM | disk | FTP | other *** search
/ No Fragments Archive 12: Textmags & Docs / nf_archive_12.iso / MAGS / TEXTMAGS / ATOS / archive / ATOS971M.ZIP / ATOS971M / SOURCEN / BINBAUM.C < prev    next >
Encoding:
C/C++ Source or Header  |  1997-02-01  |  4.4 KB  |  129 lines
  1. /*
  2.  * Quelltext zum ATOS-Artikel "Dynamische Datenstrukturen"
  3.  * ATOS 3/96, 5/96, 1/97
  4.  *
  5.  * Quelltext für einen binären Baum am Beispiel einer CD-Verwaltung.
  6.  *
  7.  * Autor: Hauke Wessels
  8.  */
  9.  
  10. #include <stdio.h>
  11. #include <string.h>
  12. #include <stdlib.h>
  13.  
  14. #include "binbaum.h"                                    /* struct's etc. */
  15.  
  16. void main(void)
  17. {
  18.     exit(EXIT_SUCCESS);                                    /* und tschüß */
  19. }
  20.  
  21. int einfuegen(Knoten *wurzel, Knoten *eintrag)            /* Datensatz einfügen in bin. Baum */
  22. {
  23.     long erg;
  24.  
  25.     erg = strcmp(wurzel->gruppe, eintrag->gruppe);        /* Strings vergl. */
  26.     if (erg == 0)                                        /* exakt gefunden? */
  27.         return(FALSE);                                    /* dann nicht einfügen */
  28.     if (erg < 0)                                        /* Eintrag ist kleiner */
  29.     {
  30.         if (wurzel->links == NULL)                        /* noch weitere Einträge*/
  31.         {
  32.             wurzel->links = eintrag;                    /* einfügen */
  33.             eintrag->links = NULL;                        /* zur Sicherheit ... */
  34.             eintrag->rechts = NULL;                        /* ... markieren      */
  35.             return(TRUE);                                /* wurde eingefügt */
  36.         }
  37.         else
  38.             return(einfuegen(wurzel->links, eintrag));    /* links einfügen */
  39.     }
  40.     else
  41.     {
  42.         if (wurzel->rechts == NULL)                        /* noch weitere ...     */
  43.         {                                                /* Einträge einthalten? */
  44.             wurzel->rechts = eintrag;                    /* einfügen */
  45.             eintrag->links = NULL;                        /* zur Sicherheit ... */
  46.             eintrag->rechts = NULL;                        /* ... markieren      */
  47.             return(TRUE);                                /* wurde eingefügt */
  48.         }
  49.         else
  50.             return(einfuegen(wurzel->rechts, eintrag));    /* rechts  einfügen */
  51.     }
  52. } /* einfuegen */
  53.  
  54. int loeschen(Knoten **wurzel, char *gruppe)                /* löscht ein Element aus dem Baum */
  55. {
  56.     long erg;                                            /* Hilfsvariable; Ergebnis des Stringvergleichs */
  57.     Knoten *hilf;                                        /* Hilfszeiger */
  58.     
  59.     if (*wurzel == NULL)                                /* Gruppe nicht gefunden? */
  60.         return(FALSE);
  61.     
  62.     erg = strcmp((*wurzel)->gruppe, gruppe);            /* Gruppe vergleichen */
  63.     if (erg < 0)                                        /* Gruppe ist im linken Teilbaum */
  64.         return(loeschen(&(*wurzel)->links, gruppe));    /* Rekursion, die gruppe im linken Teilbaum löschen */
  65.     if (erg > 0)                                        /* Gruppe ist im rechten Teilbaum */
  66.         return(loeschen(&(*wurzel)->rechts, gruppe));    /* Gruppe im rechten Teilbaum löschen */
  67.     if (erg == 0)                                        /* Treffer? */
  68.     {
  69.         hilf = *wurzel;
  70.         if (hilf->rechts == NULL)                        /* kein rechtes Kind? */
  71.         {
  72.             *wurzel = hilf->links;                        /* dann einfach linken Teilbaum nehmen */
  73.             free(hilf);                                    /* gelöschten Knoten wieder frei geben */
  74.         }
  75.         else
  76.         {
  77.             if (hilf->links == NULL)                    /* kein linkes Kind? */
  78.             {
  79.                 *wurzel = hilf->rechts;                    /* dann einfach rechten Teilbaum nehmen */
  80.                 free(hilf);                                /* Knoten-Speicher frei geben */
  81.             }
  82.             else                                        /* sowohl linkes als auch rechtes Kind! */
  83.             {
  84.                 ersatz_finden(&hilf->links, wurzel);    /* nun müssen einige Äste umgehängt werden */
  85.                 free(hilf);                                /* Knoten-Speicher frei geben */
  86.             }
  87.         }
  88.     }
  89.     return(TRUE);
  90. }
  91.  
  92. void ersatz_finden(Knoten **knoten, Knoten **zu_loeschen)    /* sucht den In-Order-Vorgänger und setzt ihn an die Stelle von *zu_loeschen */
  93. {
  94.     Knoten *hilf;
  95.     
  96.     hilf = *knoten;
  97.     
  98.     if (hilf->rechts != NULL)                            /* rechter Sohn ist vorhanden? */
  99.         ersatz_finden(&hilf->rechts, zu_loeschen);        /* vom linken Sohn das rechteste Blatt suchen (rek.) */
  100.     else
  101.     {
  102.         knoten = &hilf->links;                            /* linken Teilbaum des alten Kindes ersetzen */
  103.         hilf->links = (*zu_loeschen)->links;            /* linken Teilbaum an Ersatz hängen */
  104.         hilf->rechts = (*zu_loeschen)->rechts;            /* rechten Teilbaum an Ersatz hängen */
  105.         zu_loeschen = &hilf;                            /* Generationswechsel. das alte Kind wird nun Vater */
  106.     }
  107. }
  108.  
  109. void traversieren(Knoten *wurzel)                        /* In-Order-Durchlauf durch den Teilbaum */
  110. {
  111.     if (wurzel->links != NULL)                            /* gibt es einen linken Teilbaum */
  112.         traversieren(wurzel->links);                    /* dann erst mal in den linken Teilbaum gehen */
  113.     if (wurzel->rechts != NULL)                            /* gibt es einen rechten Teilbaum? */
  114.         traversieren(wurzel->rechts);                    /* dann den auch noch durchlaufen */
  115.     puts(wurzel->gruppe);                                /* und ausgeben */
  116. }
  117.  
  118. Knoten *suche(Knoten *wurzel, char *key)                /* sucht ein Element in dem bin. Suchbaum */
  119. {
  120.     long erg;
  121.     
  122.     erg = strcmp(wurzel->gruppe, key);                    /* Strings vergleichen */
  123.     if (erg < 0)                                        /* kleiner? */
  124.         return(suche(wurzel->links, key));                /* im linken Teilbaum suchen */
  125.     if (erg > 0)                                        /* größer? */
  126.         return(suche(wurzel->rechts, key));                /* im rechten Teilbaum suchen */
  127.     return(wurzel);
  128. }
  129.