Pretraga binarnog stabla C

Pretraga binarnog stabla C 27.01.2014. u 18:03 · pre 155 meseci #1

Pozdrav.
Potrebna mi je pomoc oko algoritma za 'pametnu' pretragu binarnog stabla. Treba da vratim broj cvorova kod kojih je podatak po kome se formira stablo veci od nekog zadatog broja ali tako da ne prolazim kroz sve cvorove. Moze i samo ideja pa cu napisati sam, ne mora ceo kod.

Re: Pretraga binarnog stabla C 27.01.2014. u 19:01 · pre 155 meseci #2

Za zadatak i resenje je vazno kako se formira stablo. Ako je stablo slucajnog rasporeda sa slucajnim vrednostima cvorova i listova onda ne mozes da prebrojis bez da posetis sve cvorove.

Potpis

Sloba je za 12 godina promenio antropološki kod srpskog naroda. On je od jednog
naroda koji je bio veseo, pomalo površan, od jednog naroda koji je bio znatiželjan, koji
je voleo da vidi, da putuje, da upozna,
od naroda koji je bio kosmopolitski napravio narod koji je namršten, mrzovoljan,
sumnjicav, zaplašen, narod koji se stalno nešto žali, kome je stalno neko kriv - Z.Đinđić

Re: Pretraga binarnog stabla C 27.01.2014. u 23:10 · pre 155 meseci #3

Formira se tako sto levo od svakog cvora idu elementi manji od njega a desno veci, balans vec nije bitan, tako da moze i za ne balansirano stablo.

Re: Pretraga binarnog stabla C 28.01.2014. u 00:11 · pre 155 meseci #4

Mozes da upises u svaki cvor tezinu levog i tezinu desnog cvora tako sto ces kad prolazis kroz stablo prilikom dodavanja noda
dodati +1 svakom listu kroz koji prolazis. To mi je prvo palo napamet. Kada pretrazujes stablo dodjes do cvora
gde su svi levi manji a svi desni veci od zadatog broja i onda procitas tezinu datog cvora.

Re: Pretraga binarnog stabla C 28.01.2014. u 00:36 · pre 155 meseci #5

To je odlicno resenje i tada imam minimalni broj provera cvorova pri pretrazi ali mi nije dozvoljeno da menjam strukturu. Cvor mora da sadrzi tacno ono sto mi je zadato. Posto je obicno binarno stablo(nije balansirano) sme da sadrzi samo podatak i pokazivac na levo i desno dete.

Re: Pretraga binarnog stabla C 28.01.2014. u 01:10 · pre 155 meseci #6

Ako nemas podatak o tezini leve i desne grane u cvoru, onda moras proci celu granu da bi izracunao tezinu.

Re: Pretraga binarnog stabla C 28.01.2014. u 10:25 · pre 155 meseci #7

Ako stablo izgleda ovako i ja hocu da nadjem broj cvorova vecih od 14, zasto onda moram da prodjem i kroz 5,1,8? Zasto ne mogu da kad dodjem do prvog manjeg proverim samo desno od njega i onda se vracam gore, ka roditelju?

Code:

                        20
                       /   \
                      15   21
                     /  \    \
                    5  17    28
                   / \      / \
                  1   8   24  30
                         / \
                        23  26

Re: Pretraga binarnog stabla C 28.01.2014. u 11:23 · pre 155 meseci #8

Možeš i to je jedina optimizacija koju mogu da vidim.

Re: Pretraga binarnog stabla C 28.01.2014. u 11:43 · pre 155 meseci #9

Pa da, ali kako?

Re: Pretraga binarnog stabla C 28.01.2014. u 17:36 · pre 155 meseci #10

resio sam, evo kako ako nekog interesuje.

Code:

void trazi(drvo* p, int k, int* broj)
{
    if(p)
    {
        if(p->broj > k)
        {
            (*broj)++;
            trazi(p->levi,k,broj);
        }
        trazi(p->desni,k,broj);
    }
}

Re: Pretraga binarnog stabla C 28.01.2014. u 20:26 · pre 155 meseci #11

Citat:

tripleqqqqq:
Ako stablo izgleda ovako i ja hocu da nadjem broj cvorova vecih od 14, zasto onda moram da prodjem i kroz 5,1,8? Zasto ne mogu da kad dodjem do prvog manjeg proverim samo desno od njega i onda se vracam gore, ka roditelju?

A sta ako je stablo ovakvo?

Code:

                        20
                       /   \
                      16   21
                     /  \    \
                   5   17     28
                   / \           / \
                 1   8        24  30
                       \       / \
                       15   23  26

Re: Pretraga binarnog stabla C 28.01.2014. u 23:36 · pre 155 meseci #12

Radi i u tom slucaju, on stigne do petice, i ona nije manja od 14 i tada rekurzivno poziva istu funkciju za desnu granu, desna grana je 8, posto 8 takodje nije manje od 14 opet poziva istu funkciju za desnu granu, tu uveca brojac za 1 jer je 15 vece od 14 i poziva za levu granu, ali sada je p = NULL jer leva grana ne postoji i onda se vraca na gore.

Forum kao aplikacija na telefonu

Srodne teme