13 Sep 2009

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

Uwaga: Artykuł ten pochodzi ze starej wersji mojego bloga - w chwili obecnej liczy on sobie już co najmniej 3 lata ;).

Czym są drzewa binarne

Drzewo binarne to jeden z rodzajów drzewa (struktury danych), w którym liczba synów każdego wierzchołka wynosi nie więcej niż dwa. Wyróżnia się wtedy lewego syna i prawego syna danego wierzchołka.

Do czego drzewa binarne są stosowane?

Drzewa ułatwiają i przyspieszają wyszukiwanie, a także pozwalają w łatwy sposób operować na posortowanych danych. Znaczenie tych struktur jest bardzo duże i ze względu na swoje własności drzewa są stosowane praktycznie w każdej dziedzinie informatyki (np. bazy danych, grafika komputerowa, przetwarzanie tekstu, telekomunikacja).

Drzewa składają się z wierzchołków (węzłów) oraz łączących je krawędzi. Jeśli drzewo nie jest puste, tzn. liczba wierzchołków jest większa od zera, jeden z nich jest wyróżniony i nazywany korzeniem drzewa.

Więcej o drzewach można przeczytać na stronach Polskiej Wikipedii, skąd w znacznej mierze pochodzi ten cytat.

Przykładowa reprezentacja drzewa poszukiwań binarnych

Tworzenie drzewa BST przebiega w następujący sposób:
  1. Jeśli drzewo BST jest puste to wstawiamy element jako korzeń (i omijamy następne punkty). Gdy drzewo nie jest puste to porównujemy wstawiany element z korzeniem.
  2. Jeżeli wartość elementu jest mniejsza od wartości porównywanego wierzchołka to przechodzimy do lewego syna, jeżeli zaś większa to do prawego syna (gdy równa to zależnie od tego jak sobie wybierzemy, byle konsekwentnie).
  3. Gdy tam gdzie "doszliśmy" nie ma żadnego wierzchołka to przechodzimy do następnego punktu. Jeżeli jednak znajduje się tam inny wierzchołek drzewa to musimy porównać go z wstawianym elementem i wrócić do punktu 2.
  4. Skoro doszliśmy do "wolnego miejsca" to właśnie tam wstawiamy nasz element. Oczywiście będzie om synem wierzchołka, z którego przyszliśmy (a czy lewym czy prawym to zależy od tego, w którą stronę poszliśmy z tamtego wierzchołka).
Drzewo dla liczb: [7, 11, 3, 10, 15, 1, 5, 4] wygląda w sposób następujący:
ps: Dziękuje Tomkowi Karbownickiemu za artykuł o Języku Dot, bo właśnie tym narzędziem wygenerowałem powyższy schemat (w poprzedniej wersji bloga był on zrobiony w Inkscape). Dla zainteresowanych kod w Graphviz - dot, wygląda tak:
digraph 7 {
    7 -> 3;
    7 -> 11;
    3 -> 1;
    3 -> 5;
    5 -> 4;
    11 -> 10;
    11 -> 15;
}

Przykładowa implementacja drzewa poszukiwań binarnych w C

Proszę pamiętać, że kod ten pisałem z początkiem drugiego semestru studiów ;) i na pewno nie jest on idealny, niemniej jednak zostanie tutaj zamieszczony.
/*
 * 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;
}

4 comments:

  1. Jeżeli ktoś jest zainteresowany większą ilością informacji o drzewach binarnych to polecam zerknąć na stronę sdj - artykuł "Wyświetlanie drzewa na konsoli"

    ReplyDelete
  2. http://programmuj.blogspot.com/2009/09/implementacja-drzewa-binarnego-bst-c.html tu jest prosta implementacja drzewa binarnego w C dla kompletnych laików. Kodu jest mniej, nie jest napisany profesjonalnie ale tylko aby zademonstrować jak można zaimplementować wstawianie elementów do drzewa.

    ReplyDelete
  3. JEzuuuuuuu w koncu cos co dziala i sie kompiluje elegancko ! wielkie dzieki za ten kod bo ułatwia ogarniecie drzew w ogole. Mam na szybko do napisania projekt a w necie zaden kod dotychczas znaleziony w ogole sie nie chcial kompilowac pod GCC ( tak do Ciebie Kadoel tez to mowie, pomijam warningi z opcji -Wall ale error uniemożliwił mi jaka kolwiek kompilacje twojego kodu) WIELKIE DZIEKI JESZCZE RAZ !!!!

    ReplyDelete
    Replies
    1. n/p mam nadzieję, że oprócz kompilacji kodu spróbujesz podjąć wyzwanie napisania swojej implementacji - ew. zainteresowania się innymi strukturami danych - bo jest ich naprawdę sporo ;).

      Delete