Elektroda.pl
Elektroda.pl
X

Search our partners

Find the latest content on electronic components. Datasheets.com
Elektroda.pl
Please add exception to AdBlock for elektroda.pl.
If you watch the ads, you support portal and users.

[C] Jak zaimplementować drzewo binarne?

caps20 31 Aug 2009 16:44 9869 12
  • #1
    caps20
    Level 10  
    Witam mam taki problem nie znalazlem zadnych pomocnych i zrozumialych informacji na temat drzew binarnych w c, a musze zrobic taki program "Napisać prosty słownik oparty o drzewo binarne, który pamięta wszystkie wyrazy w tekście i liczbę ich wystąpień, żeby uniknąć problemu z polskimi znakami przyjmiemy ze tekst jest w j. angielskim.
    Program w wczytuje z pliku tekstowego (książka czy dokumentacja z internetu)
    i niepowtarzające sie wyrazy zapisuje do drzewa, a dla powtarzających inkrementuje licznik wystąpień"

    typedef struct slownik_
    {
    char * slowo;
    int liczbawystapien;
    struct slownik_ *lewy;
    struct slownik_ *prawy;
    } Slownik;



    Wszystkie operacje na słowniku ma wykonywać osobna funkcja np.

    Slownik * tworz_slownik( FILE *plikztekstem)
    {
    //wczytuje z pliku i zapisuje do drzewa
    //MOZE a wrecz MUSI zawierac funkcje pomocnicze
    }

    Nie mialem nigdy stycznosci z drzewami dlatego nie wiem jak to zrobic - nie oczekuje rozwiazania ( choc nie pogardze) - moga byc zrodla na temat drzew binarnych lub cos innego co pomoze, czesc ze szczytywaniem wyrazow mam.
    Z gory dziekuje za pomoc.
  • #2
    marseel
    Level 10  
    Więc tak:
    1. Trzeba napisać procedurę, która wyszukuje węzeł w drzewie.
    2. procedurę, która dodaje węzeł.

    I jeżeli wyszukiwanie zakończy się powodzeniem, to zwiększamy licznik,a jeżeli nie to dodajemy.
    Struktura węzła powinna mieć jeszcze wskaźnik na ojca(tylko korzeń ma pusty wskaźnik na ojca).
    wyszukiwanie:
    x- wskaźnik do korzenia , k- klucz

    Code:

    Tree-Search(x,k)
    if x=NIL lub k=key[x]
    return x
    if(k<key[x])
        then return Tree-Search(left[x],k)
        else return  Tree-Search(right[x],k)


    dodawanie:
    x-korzeń
    z-węzeł do dodania
    lewy i prawy wskaźnik z puste(NIL)
    Code:

    Tree-Insert(x,z)
    y=NIL
    while x!=NIL
     do y=x
           if key[z]< key[x]
                 then x=left[x]
                 else x=right[x]
    parent[z]=y
    if y=NIL
         then   (drzewo jest puste i z staje sie korzeniem)
         else if key[z] < key[y]
                  then left[y]=z
                  else right[y]=z
  • #3
    jestam
    Automation specialist
    Trochę informacji o drzewach binarnych jest w polskiej Wikipedii, w sumie powinno wystarczyć.

    marseel wrote:

    1. Trzeba napisać procedurę, która wyszukuje węzeł w drzewie.
    2. procedurę, która dodaje węzeł.

    I jeżeli wyszukiwanie zakończy się powodzeniem, to zwiększamy licznik,a jeżeli nie to dodajemy.

    ...jeżeli nie to dodajemy węzeł.

    @caps20: zaimplementuj to co kol. marseel opisał, pytaj w razie problemów

    @marseel: węzły drzewa nie muszą mieć wskazania na rodziców; w tym konkretnym przypadku jest to zupełnie zbędne
  • #4
    caps20
    Level 10  
    Moze tak od poczatku - jak pisalem nie mialem z drzewami stycznosci i zaczynam programowac dopiero. Niech mi ktos rozjasni czy dobrze mysle:
    mam strukture Slownik ( jest to jakby typ danych) definiuje zmienna np wezel czyli Slownik wezel1; teraz pobieram wyraz i ustawiam wskaznik na ten wyraz do wezel. slowo i inkrementuje licznik , potem pobieram drugi wyraz sprawdzam czy go juz nie ma jezeli nie to ustawiam wskaznik na ten wyraz do np wezel2 i w wezel1.lewy ustawaim wskanik na wezel2 .
    Pewnie to glupio brzmi ale nie umie zalapac tej zasady jak sie to odbywa - osoba w temacie na pewno bedzie wiedziec o co mi chodzi i wyjasni co i jak.
  • #5
    jestam
    Automation specialist
    1. czytasz słowo z wejścia
    2. szukasz słowa w drzewie
    2a. znalazłeś -> zwiększasz pole liczbawystapien
    2b. nie znalazłeś ->
    - tworzysz nowy węzeł (malloc)
    - tworzysz nową kopię słowa: alokujesz pamięć (malloc) i kopiujesz (strncpy)
    - przypisujesz liczbawystapien = 1
    - wstawiasz właśnie utworzony węzeł do drzewa, przypisując go odpowiednio do wskaźnika lewy lub prawy u węzła-rodzica; wyjątek - wstawienie pierwszego słowa do drzewa - wtedy nie ma rodzica i przypisuje się do zmiennej, która wskazuje na korzeń drzewa (czyli pierwszy węzeł)

    Pułapek w tym jest kilka, najważniejsze to że operujesz na dynamicznie tworzonych zmiennych, a więc:
    - nie deklarujesz zmiennej Slownik wezel1 tylko Slownik * korzen;
    - poszczególne węzły alokujesz funkcją malloc
    - dla każdego słowa koniecznie alokujesz tablicę bajtów o odpowiedniej długości i kopiujesz odczytane słowo do tej tablicy, po czym przypisujesz wskaźnik do niej do pola slowo w węźle.
  • #6
    caps20
    Level 10  
    Dobra juz zalapalem jak to dziala - zostal tylko jeden problem, w wiekszosci drzew wpisujemy liczby wiec porownujemy i wiemy czy na lewo czy na prawo, a w tym przypadku nie porownujemy , mamy poprostu wpisywac w pierwsze wolne. Dla przykladu gdy mamy juz sytuacje gdzie korzen ma wpisanych potomkow , jego potomkowie tez maja wpisanych i teraz chce dalej powpisywac ?? Jak to zrobic zeby program wiedzial ze ma isc np prawo->lewo i tu do lewego ma wpisac obecny adres pamieci. W tresci zadania a dokladnie w strukturze podanej nie ma wskaznika na rodzica co by chyba ulatwilo ?? jakies pomysly??

    Dodano po 9 [minuty]:

    Gdzies widzialem cos ze zmienna kolejka i wydaje mi sie ze w zaleznosci od niej powinno sie co innego robic
  • #7
    marseel
    Level 10  
    Możesz napisać funkcje, która będzie miała dwa argumenty(wskaźniki do napisów).
    I będzie zwracała true, gdy pierwszy argument jest mniejszy od drugiego. Wtedy porównujesz po kolei każdy znak i gdy napotkasz różne znaki to ten napis jest mniejszy, którego kod ASCII jest mniejszy.

    A czy to koniecznie musi być w C ? Nie może być w C++ ? To by znacznie ułatwiło, bo w STLu jest gotowa struktura set, czyli drzewo czerwono-czarne, które jest odmianą drzewa binarnego.

    Dodano po 1 [godziny] 12 [minuty]:

    Code:
    #include<stdlib.h>
    
    #include<stdio.h>

    struct tree_el {
       int val;
    int licznik;
       struct tree_el * right, * left;
    };

    typedef struct tree_el node;

    node *search(node ** tree,int value)
    {
    if(!(*tree) || (*tree)->val==value)
    return (*tree);
    if(value<(*tree)->val)
       return search(&(*tree)->left,value);
       else return search(&(*tree)->right,value);
    }

    void insert(node ** tree, node * item) {
       if(!(*tree)) {
          *tree = item;
          return;
       }
       if(item->val<(*tree)->val)
          insert(&(*tree)->left, item);
       else if(item->val>(*tree)->val)
          insert(&(*tree)->right, item);
    }

    void printout(node * tree) {
       if(tree->left) printout(tree->left);
       printf("%d\n",tree->val);
       if(tree->right) printout(tree->right);
    }

    int main() {
       node * curr, * root;
       int i;
       int ile;
       root = NULL;


    printf("ile chcesz podac liczb?");
    scanf("%d",&ile);
    while(ile--)
    {
    scanf("%d",&i);
    if(search(&root,i))
    {

    (*search(&root,i)).licznik++;
    printf(" jest juz:%d takich liczb wraz z nia\n", (*search(&root,i)).licznik);
    }
    else{

    curr = (node *)malloc(sizeof(node));
     curr->left = curr->right = NULL;
    curr->val=i;
    curr->licznik=1;
     insert(&root, curr);
    printf("utworzony zostal dodatkowy wezel\n");
    }
    }

    return 0;
    }

    Jest do implementacja drzewa binarnego. Znalazłem go na jednej stronie i dopisałem funkcje search. Tu jest zaimplementowane na integerach. Najpierw podajesz liczbę slow(tu liczb) i potem odpowiednio albo tworzy węzeł, albo dodaje licznik.
  • #8
    jestam
    Automation specialist
    caps20 wrote:
    w wiekszosci drzew wpisujemy liczby wiec porownujemy i wiemy czy na lewo czy na prawo, a w tym przypadku nie porownujemy , mamy poprostu wpisywac w pierwsze wolne [...]


    Porównanie napisów załatwiasz funkcją strcmp. Drzewo to drzewo, w tym przypadku także porównujesz.

    @marseel: Kolega caps20 chyba się tego dopiero uczy. Wklejając taki kod raczej mu utrudniasz zamiast ułatwiać.
  • #9
    caps20
    Level 10  
    No troszke namieszane - mam takie pytanie : jestesmy na takim etapie w programie mamy wyraz ( dokladnie to obszar pamieci ktory na niego wskazuje), sprawdzilismy czy juz nie wystepuje i teraz chcemy ustawic wskazanie na niego w odpowiednim węźle i tu pytanie czy musze cos porownywac i jak tak to co - zeby dojsc do odpowiedniego wezla. Zrobilem algorytm ktory to robi bez porownywania ze soba wezlow, poniewaz nie wiem po co jezeli tam mamy wyrazy (wskazania na wyrazy) , chyba ze to chodzi o porownanie adresow w pamieci , nie wiem.
    Ja to zrobilem w ten sposob ze kazdy kolejny wezel ma numer , teraz dostajemy kolejny np 13 z koleji wyraz (zakladamy ze sie nie powtarzaly) i teraz dzielac przez 2 dostajemy 6 reszte 1 czyli prawo, pozniej 6 dzielimy na 2 mamy 3 reszte 0 czyli lewo i w koncu 3 dzielimy na 2 mamy 1 i reszte 1 czyli prawo( reszta 1 prawo 0 lewo ). Teraz od konca patrzac idziemy od korzenia w prawo w lewo i tu trzeba dowiazac na prawo ( przypominam ze jest to drzewo binarne czyli 2 potomkow moze byc), i mamy dokladne wskazanie .
    Jako dane wejsciowe mamy numer wyrazu i wskazanie na korzen , na wyjsciu otrzymamy wskazanie. Jak ktos chce moge zamiescic ten kawalek kodu, wiem ze jest dobrze - probowalem roznych wariantow, ale moze nie tedy droga.
  • #10
    Dr.Vee
    VIP Meritorious for electroda.pl
    Kolego caps20, chyba niezbyt dokładnie czytałeś artykuł o drzewach binarnych w Wikipedii... Jak odnajdziesz w drzewie węzeł, który przechowuje ilość wystąpień danego wyrazu? Jeśli przez przeglądanie wszystkich węzłów, to nie jest to drzewo, tylko lista. Zaletą (zbilansowanego) drzewa binarnego jest takie uporządkowanie węzłów, przy którym dokonując wyboru pomiędzy prawym a lewym potomkiem automatycznie eliminujesz połowę węzłów, które musiałbyś jeszcze przeszukać.

    Masz dowolny węzeł i funkcję porównującą napisy (strcmp). Jeśli zapewnisz, że napis przechowywany w prawym potomku zawsze jest "mniejszy" (w sensie strcmp) od rodzica, a w lewym potomku zawsze "większy", to wykonując jedno porównanie napisów eliminujesz jednego z potomków (a więc i całe poddrzewo pod nim). Czyli:
    Code:
    void wstaw_wyraz(drzewo* korzeń, const char* wyraz)
    
    {
        // Korzeń nie może być NULL
        assert( korzeń != NULL );

        int porównanie = strcmp(wyraz, korzeń->wyraz);
        if ( porównanie == 0 )
        {
            // znalazłeś ten sam wyraz, zwiększ licznik
        }
        else if ( porównanie < 0 )
        {
            // wstaw wyraz do lewego poddrzewa
            // jeśli poddrzewo == NULL, utwórz nowy węzeł z licznikiem 1
        }
        else
        {
            // wstaw wyraz do prawego poddrzewa
            // jeśli poddrzewo == NULL, utwórz nowy węzeł z licznikiem 1
        }
    }


    Pozdrawiam,
    Dr.Vee
  • #11
    caps20
    Level 10  
    Tego ktory to wyraz z kolei nie przechowywalbym w drzewie, a co z sytuacja gdzie jako pierwszy wyraz dostane "adam" i korzen wskazuje na "adam" i prawie wszystkie napisy beda wieksze od rodzica w tym wypadku korzen, wiec wszystkie beda szly na lewo od korzenia?
  • #12
    Dr.Vee
    VIP Meritorious for electroda.pl
    Nawet jeśli wszystkie wyrazy będą większe od "adam", to będą się różnić między sobą - a więc mamy nadzieję, że lewe poddrzewo korzenia będzie dość rozgałęzione i nie będzie tragedii. W skrajnym przypadku (wyrazy na wejściu posortowane alfabetycznie) drzewo zdegeneruje się do nieefektywnej listy.

    Żeby temu zapobiec stosuje się bardziej zaawansowane metody konstrukcji drzewa, albo jego "wyrównywanie" przez reorganizację. Poczytaj np. o samowyrównujących się drzewach czarno-czerwonych albo o drzewach AVL. Poprawna implementacja tych drzew jest trudnym testem dla nawet bardziej doświadczonych programistów - więc na razie zaimplementuj proste, standardowe drzewo binarne :)

    Pozdrawiam,
    Dr.Vee
  • #13
    caps20
    Level 10  
    Ahhhhh no wkoncu - ja caly czas myslalem ze musze miec 'symetryczne' te drzewo czyli ze jezeli po lewej sronie korzenia mam np 3 wezly to nastepne 3 wyrazy wpisuje po prawej stronie korzenia.
    Wiec ten algortm co zrobilem wpisuje wlasnie tak , ze drzewo jest 'wyrownane' metadą ktora opisalem wyzej , a tak na marginesie to drzewa avl i b-drzewa mam na prace inzynierska - czeka mnie duzo pracy:)