[C] Jak zaimplementować drzewo binarne?

Question

Witam mam taki problem nie znalazlem zadnych pomocnych i zrozumialych informacji na temat drzew binarnych w c, a musze zrobic taki program "Napisać pr...

marseel · Answer

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

jestam · Answer

Trochę informacji o drzewach binarnych jest w polskiej Wikipedii, w sumie powinno wystarczyć....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

caps20 · Answer

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.

jestam · Answer

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.

caps20 · Answer

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

marseel · Answer

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.

jestam · Answer

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ć.

caps20 · Answer

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.

Dr.Vee · Answer

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&#40;drzewo* korzeń, const char* wyraz&#41;&#123;    // Korzeń nie może być NULL    assert&#40; korzeń != NULL &#41;;    int porównanie = strcmp&#40;wyraz, korzeń->wyraz&#41;;    if &#40; porównanie == 0 &#41;    &#123;        // znalazłeś ten sam wyraz, zwiększ licznik    &#125;    else if &#40; porównanie < 0 &#41;    &#123;        // wstaw wyraz do lewego poddrzewa        // jeśli poddrzewo == NULL, utwórz nowy węzeł z licznikiem 1    &#125;    else    &#123;        // wstaw wyraz do prawego poddrzewa        // jeśli poddrzewo == NULL, utwórz nowy węzeł z licznikiem 1    &#125;&#125;Pozdrawiam,Dr.Vee

caps20 · Answer

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?

Dr.Vee · Answer

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

caps20 · Answer

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:)