Drzewo poszukiwań binarnych (BST) - implementacja w języku C¶

/*
 * author: Tomasz Gawęda
 * url: http://blog.0x1fff.com/
 * date: Tue Jul  4 23:25:59 CEST 2006
 * license: BSD
 * version: 0.0.1
 *
 * Binnary tree - demonstration in C.
 *
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

/* Stany wyjscia */
#define BAD_ALLOC 10

/* stale zdefiniowane */
#define DATA_BUFFER 1024
#define TRUE 1
#define FALSE 0

struct Dane {
    char *tekst;
    int id;
};

struct Wezel {
    struct Dane *zawartosc;
    int poziom;
    struct Wezel *lewy;
    struct Wezel *prawy;
};

/* Naglowki funkcji - tzw deklaracje */
struct Dane *WczytajDane();
void WypiszDane(struct Dane *wypisz_mnie);
void BadAlloc(void);
void ClearStream(FILE *fp);
struct Wezel *StworzWezel(void);
int WstawDoDrzewa(struct Wezel **root, struct Wezel *doWsawienia);
void UsunDrzewo(struct Wezel *root);
void WypiszDrzewo(struct Wezel *root);
int IleElementowWDrzewie(struct Wezel *root);
struct Wezel *SprawdzCzyElementJest_id(struct Wezel *root, int id);
void WypiszMenu(void);
void ObslugaMenu(char wybor);
void UsunCalaZaalokowanaPamiec(void);

/* Zmienne globalne */
struct Wezel *korzen;

/**
 * Funckja główna
 */
int main(int argc, char **argv) {
    char wybor = '\0';

    atexit(UsunCalaZaalokowanaPamiec);
    fprintf(stdout, "%s Compiled: "__DATE__ __TIME__ "\n", argv[0]);
    do {
        WypiszMenu();
        wybor = fgetc(stdin);
        ClearStream(stdin);
        wybor = (char) toupper(wybor);
        ObslugaMenu(wybor);
    } while (wybor != 'X');

    return (EXIT_SUCCESS);
}

/**
 * Funkcja do obslugi danych
 */
struct Dane *WczytajDane() {
    struct Dane *temp = (struct Dane *) malloc(sizeof (struct Dane));
    char tymczasowe_dane[DATA_BUFFER];
    int dlugosc = 0;

    if (temp == NULL) BadAlloc();
    /* Czyscimy bufor jakby cos w nim zostalo niekoniecznie to trzeba robic bo dane zostana nadpisane
     * ale warto ;)
     */
    for (dlugosc = 0; dlugosc < DATA_BUFFER; dlugosc++) *(tymczasowe_dane + dlugosc) = '\0';
    /* Pobieramy dane i do zmiennej tymczasowej, nastepnie dynamicznie przydzielamy pamiec dla nich i kopiujemy
     * a i jeszcze czyscimy stdin ;)
     */
    fprintf(stdout, "Podaj ciag znakow do przechowywania: ");
    fflush(stdout);
    fgets(tymczasowe_dane, DATA_BUFFER, stdin);
    ClearStream(stdin);
    dlugosc = strlen(tymczasowe_dane);
    temp->tekst = (char *) malloc((dlugosc + 1) * sizeof (char));
    strcpy(temp->tekst, tymczasowe_dane);
    /* pobieramy id ;) ewentualnie wyliczamy wlasne */
    fprintf(stdout, "Podaj id: ");
    fflush(stdout);
    fgets(tymczasowe_dane, DATA_BUFFER, stdin);
    ClearStream(stdin);
    /* nim przepiszemy wypadalo by sprawdzic czy id sie nie powtarza ... no ale ;)*/
    temp->id = atoi(tymczasowe_dane);
    /* slow pare:
     *  - po co oprozniac bufor (fflush) po fprintf - niektore implementacje jezyka C tak naprawde drukuja
     *    dane dopiero po wystapieniu znaku nowej linii -> nam o to nie chodzi
     *  - po co oprozniac bufor po wczytaniu (ClearStream) po fgets()?
     *    Otoz jesli ktorys z uzytkownikow poda wiecej danych niz wejdzie w bufor, to funkcja fgets nie odczyta ich
     *    a zostana one w strumieniu, prawdopodobnie trafia do kolejnej funkcji (kolejnego fgetsa) ktora bedziemy czytac.
     */
    return temp;
}

void WypiszDane(struct Dane *wypisz_mnie) {
    fprintf(stdout, "id: %d, %s\n", wypisz_mnie->id, wypisz_mnie->tekst);
    return;
}

/* ---- Nieprzewidziane sytuacje ---- */

/**
 * Funkcja wywolywana gdy nastepuje blad przydzielenia pamieci ...
 * alternatywnie moglibysmy uzyc wlasnej funkcji do allokowania pamieci
 * patrz biblioteka glibc
 */
void BadAlloc(void) {
    fprintf(stderr, "Blad przydzielenia pamieci.\n");
    UsunCalaZaalokowanaPamiec();
    exit(BAD_ALLOC);
}

/**
 * Funckja usuwająca wejscie do napotkanai EOF lub znaku nowej
 * linii (nie zawsze fscnaf / fgets to robi)
 */
void ClearStream(FILE * fp) {
    int ch = 0;
    while ((ch = fgetc(fp)) != EOF && ch != '\n');
    return;
}

/**
 * Funkcja bindujaca się do zdarzenia exit()
 * Wychodzac z programu funkcja exit nie mozemy "zapomniec"
 * o usunieciu danych zaalokowanych (wyciek pamieci).
 *
 * TODO: Obsluga sygnalow.
 */
void UsunCalaZaalokowanaPamiec(void) {
    UsunDrzewo(korzen);
    korzen = NULL;
    return;
}

/* Funkcje do obslugi drzewa */

/**
 * Funckja do tworzenia elementu wraz z danymi, w swoim ciele wywoluje
 * funkcje WczytajDane() zwracajac wskaznik na strukture z danymi,
 * polem obowiazkowym w strukturze Dane jest id
 */
struct Wezel *StworzWezel(void) {
    struct Wezel *temp = (struct Wezel *) malloc(sizeof (struct Wezel));
    if (temp == NULL) BadAlloc();
    temp -> poziom = 0;
    temp -> lewy = NULL;
    temp -> prawy = NULL;
    temp -> zawartosc = NULL;
    temp -> zawartosc = WczytajDane();
    return temp;
}

/**
 * Funkcja zajmujaca sie wstawianiem do drzewa danych, zwraca
 * 1 jesli operacja wstawienia sie powiodla
 * operacja powinna sie zawsze powiesc
 *
 * Jest to funkcja nie rekurencyjna!
 */
int WstawDoDrzewa(struct Wezel **root, struct Wezel *doWstawienia) {
    struct Wezel *temp = *root;
    struct Wezel *temp2 = NULL;
    int i = 0;

    if (*root == NULL) {
        /* Sytuacja gdy nie mamy korzenia - podanie wskaznika na wskaznik pozwala nam zrobci takie cos */
        *root = doWstawienia;
        return TRUE;
    }
    while (temp != NULL) {
        temp2 = temp;
        i++;
        if (temp->zawartosc->id < doWstawienia->zawartosc->id) temp = temp->lewy;
        else temp = temp->prawy;
    }
    /*
     * Znalezlismy miejsce gdzie musimy wstawic obiekt, wskazuje nam na to struktura temp2
     * teraz musimy ustalic czy po jej lewej czy prawej stronie to zrobimy
     */
    doWstawienia->poziom = i;
    if (temp2->zawartosc->id < doWstawienia->zawartosc->id) temp2->lewy = doWstawienia;
    else temp2->prawy = doWstawienia;
    return TRUE;
}

/**
 * Funkcja usuwa cale drzewo rekurencyjnie
 * bo tak prosciej ;) niekoniecznie wydajniej
 */
void UsunDrzewo(struct Wezel *root) {
    if (root != NULL) {
        UsunDrzewo(root->lewy);
        UsunDrzewo(root->prawy);
        free(root->zawartosc->tekst);
        free(root->zawartosc);
        free(root);
    }
    return;
}

/**
 * Wypisuje drzewo rekurencyjnie bo tak ciekawiej
 */
void WypiszDrzewo(struct Wezel *root) {
    if (root != NULL) {
        WypiszDrzewo(root->lewy);
        printf("Poziom: %d\t", root->poziom);
        WypiszDane(root->zawartosc);
        WypiszDrzewo(root->prawy);
    }
    return;
}

/**
 * Funkcja oblicza ile elementow znajduje sie w drzewie oraz zwraca ta wartosc
 * zrezygnowalem tu z globalnej wartosci ilosci elementow na rzecz przekazywania
 * i wywolywania rekurencyjnego, innym pomyslem na rozwiazanie tego problemu
 * moglo by byc kazdorazowe aktualizowanie zmiennej globalnej okresnajacej ile
 * mamy elelemntow (inkrementowanie jej jesli elelment zostanie dodany, lub dekrementowanie
 * jesli elelemnt zostanie usuniety)
 */
int IleElementowWDrzewie(struct Wezel *root) {
    int i = 0;
    if (root != NULL) {
        i++;
        i = i + IleElementowWDrzewie(root->lewy) + IleElementowWDrzewie(root->prawy);
    }
    return i;
}

/**
 * Funkcja poszukuje czy element o id znajduje sie w drzewie binarnym
 * oraz zwraca do niego wskaznik, badz NULL
 */
struct Wezel *SprawdzCzyElementJest_id(struct Wezel *root, int id) {
    struct Wezel *temp = root;

    while (temp != NULL && temp->zawartosc->id != id) {
        if (temp->zawartosc->id < id) temp = temp->lewy;
        else temp = temp->prawy;
    }
    /*
    if ( temp == NULL )
    {
             nic nie znaleziono
            return NULL;
    }
     */
    return temp;
}

/**
 * Funkcja liczy ile elementow znajduje sie na okreslonym poziomie
 * niestety przechodzi przez cale drzewo
 */

int IleElementowNaPoziomie(struct Wezel *root, int poziom) {
    int ilosc = 0;
    if (root != NULL) {
        ilosc += IleElementowNaPoziomie(root->lewy, poziom);
        if (root->poziom == poziom) ilosc++;
        ilosc += IleElementowNaPoziomie(root->prawy, poziom);
    }
    return ilosc;
}
/* Stara niedzialajaca wersja! :)
 * int IleElementowNaPoziomie( struct Wezel *root, int poziom )
{
                int i=0;

                if ( root != NULL )
                {
                        if ( root->poziom ==  poziom )
                        {
                                i++;
                                i= i + IleElementowNaPoziomie( root->lewy, poziom ) + IleElementowNaPoziomie( root->prawy, poziom );
                        }
                }
                return i;
}
 */

/**
 * Funkcja liczy sume elementow w calym drzewie i ja zwraca
 */
int SumaElementow(struct Wezel *root) {
    int i = 0;
    if (root != NULL) {
        i = root->zawartosc->id;
        i = i + SumaElementow(root->lewy) + SumaElementow(root->prawy);
    }
    return i;
}

/**
 * Funkcja oblicza ilosc elementow na okreslonym poziomie drzewa -
 * podanym jako argument poziom
 */
int SumaElementowNaPoziomie(struct Wezel *root, int poziom) {
    int suma = 0;
    if (root != NULL) {
        suma += SumaElementowNaPoziomie(root->lewy, poziom);
        if (root->poziom == poziom) suma += root->zawartosc->id;
        suma += SumaElementowNaPoziomie(root->prawy, poziom);
    }
    return suma;
    /*
     * Niedzialajaca wersja
            int i=0;
            if ( root != NULL )
            {
                    if ( root->poziom ==  poziom)
                    {
                            i = root->zawartosc->id ;
                            i= i + SumaElementowNaPoziomie( root->lewy, poziom ) + SumaElementowNaPoziomie( root->prawy, poziom );
                    }
            }
            return i;
     */
}

/**
 * Funkcja wypisuje menu widoczne w glownej czesci programu
 */
void WypiszMenu(void) {
    fprintf(stdout,
            "\n"
            "[N] Utworz nowy element\n"
            "[D] Usun cale drzewo\n"
            "[W] Wyswietl cala zawartosc drzewa\n"
            "[Z] Znajdz element po id\n"
            "[P] Policz ilosc elementow w drzewie\n"
            "[O] Policz ilosc elementow na danym poziomie drzewa\n"
            "[S] Oblicz sume wszystkich elementow znajdujacych sie w drzewie\n"
            "[T] Oblicz sume wartosci elementow na danym poziomie drzewa\n"
            "[X] Opusc program demonstrujacy dzialanie drzew binarnych\n"
            "\n\t:> ");
    fflush(stdout);

    return;
}

/**
 * Funkcja sluzaca do obslugi menu, powinno dostawac znak ktory jest
 * duza litera, chyba ze cos innego zaimplementujemy ;)
 */
void ObslugaMenu(char wybor) {
    struct Wezel *temp = NULL;
    int num = 0;
    int poziom = 0;

    switch (wybor) {
        case 'N': /* Utworz nowy element */
            temp = StworzWezel();
            WstawDoDrzewa(&korzen, temp);
            break;
        case 'D': /* Usun cale drzewo */
            UsunCalaZaalokowanaPamiec();
            break;
        case 'W': /* Wyswietl zawartosc drzewa */
            WypiszDrzewo(korzen);
            break;
        case 'Z': /* Znajdz element po id */
            fprintf(stdout, "Podaj numer id do odnalezienia:\n");
            scanf("%d", &num);
            ClearStream(stdin);
            temp = SprawdzCzyElementJest_id(korzen, num);
            if (temp != NULL) {
                fprintf(stdout, "Znaleziono! Jego zawartosc to:");
                WypiszDane(temp->zawartosc);
                fprintf(stdout, "\n");
            } else {
                fprintf(stdout, "Niestety elementu o podanym kluczu nie ma.\n");
            }
            break;
        case 'P': /* Policz ilosc elementow w drzewie */
            num = IleElementowWDrzewie(korzen);
            fprintf(stdout, "W drzewie znajduje sie %d elementow.\n", num);
            break;
        case 'O': /* Oblicz ilosc elementow na danym poziomie */
            fprintf(stdout, "Podaj numer poziomu:\n");
            scanf("%d", &poziom);
            ClearStream(stdin);
            num = IleElementowNaPoziomie(korzen, poziom);
            if (num == 0) fprintf(stdout, "Brak elementow spelniajacych wymagania\n");
            else fprintf(stdout, "Znaleziono %d elementow spelniajacych wymagania.\n", num);
            break;
        case 'S': /* Oblicz sume wszystkich elementow znajdujacych sie w drzewie */
            num = SumaElementow(korzen);
            fprintf(stdout, "Suma wszystkich elementow w drzewie wynosi %d\n", num);
            break;
        case 'T': /* Oblicz sume wartosci elementow na danym poziomie drzewa */
            fprintf(stdout, "Podaj numer poziomu dla ktorego nalezy wyliczyc sume!\n");
            scanf("%d", &poziom);
            ClearStream(stdin);
            num = SumaElementowNaPoziomie(korzen, poziom);
            if (num == 0) fprintf(stdout, "Brak elementow spelniajacych wymagania\n");
            else fprintf(stdout, "Suma elementow spelniajacych wymagania wynosi: %d.\n", num);
            break;

        case 'X': fprintf(stdout, "Dziekuje za korzystanie z programu.\n");
            UsunCalaZaalokowanaPamiec();
            break;
        default: fprintf(stdout, "Niestety wybrales niepoprawna opcje.\n");
            break;
    }
    return;
}