Forum » Programiranje » Ne-rekurzivno iskanje po rekurzivni podatkovni strukturi
Ne-rekurzivno iskanje po rekurzivni podatkovni strukturi
marjan_h ::
Že kar nekaj časa, se sprašujem kako bi iskal iterativno po recimo kopici ali drevesu.
V drevesu ima vsako vozlišče le 2 naslednika.
Tole je samo moja psevdokoda, vendar ne predstavljam si kako bi iskal z while ali for zanko.
Bi lahko kdo napisal psevdokodo za takšen primer?
Hvala za vaš trud.
V drevesu ima vsako vozlišče le 2 naslednika.
class Drevo:
Drevo otroka[]
int vrednost
function boolean isci(int v):
if v == vrednost:
return true
else:
if v < otroka[0].vrednost:
return otroka[0].isci(v)
else:
return otroka[1].isci(v)
return false
Tole je samo moja psevdokoda, vendar ne predstavljam si kako bi iskal z while ali for zanko.
Bi lahko kdo napisal psevdokodo za takšen primer?
Hvala za vaš trud.
xordie ::
na hitro:
struct Drevo {
Drevo *levo;
Drevo *desno;
int vrednost;
};
// koren drevesa s podatki
Drevo *d = koren;
while( d )
{
if( v == d->vrednost )
break;
if( v < d->vrednost )
{
d = d->levo;
}
else
{
d = d->desno;
}
}
x
Spura ::
xordie tvoja koda razisce samo najbolj levo pot v drevesu.
Iterativno lahko simuliras rekurzijo tako, da imas lasten stack.
Recimo da imas tako kodo kot xordie, naredis List<Drevo> path, malo dopolnis njegovo kodo in gre.
Iterativno lahko simuliras rekurzijo tako, da imas lasten stack.
Recimo da imas tako kodo kot xordie, naredis List<Drevo> path, malo dopolnis njegovo kodo in gre.
darkkk ::
Prevajanje rekurzije na iteracijo je bila tko ene 15-10 let nazaj najljubša naloga na faksih. Nek čudn fetiš so mel na to.
Običajno maš v drevesih 2 vrsti iskanja, "BFS" pa "DFS".
Za DFS uporabiš stack(LIFO), za BFS pa vrsto (FIFO).
Običajno maš v drevesih 2 vrsti iskanja, "BFS" pa "DFS".
Za DFS uporabiš stack(LIFO), za BFS pa vrsto (FIFO).
Spura ::
xordie tvoja koda razisce samo najbolj levo pot v drevesu.
Iterativno lahko simuliras rekurzijo tako, da imas lasten stack.
Recimo da imas tako kodo kot xordie, naredis List<Drevo> path, malo dopolnis njegovo kodo in gre.
Edit: sori xordie, narobe sm vidu kaj je problem, za iskanje bo ze deloval, ni pa to full tree traversal.
blaz_ ::
kopica je en lep primer, ko se jo zelo lepo lahko stlač v 1d array - torej pomnilnik
recimo v pomnilniku bi potem izgledala takole kot je na tem linku na sliki Kopica @ Wikipedia
in če je potreba bi se kopico lahko tut tko sprogramiral(skratka samo telovadba z indeksi) in potem greš enostavno s for-zanko čez celoten array
binarno drevo pa je prav tako lahko potem podobno kot pri tej kopici in greš enostavno s for-zanko čez array (razlika v primerjavi s kopico bi bila v bistvu le v tem, da bi imel pri binarnem drevesu v zaporedju lahko tudi luknje, medtem ko pri kopici tega nimaš, ker je uteženo drevo)
recimo v pomnilniku bi potem izgledala takole kot je na tem linku na sliki Kopica @ Wikipedia
in če je potreba bi se kopico lahko tut tko sprogramiral(skratka samo telovadba z indeksi) in potem greš enostavno s for-zanko čez celoten array
binarno drevo pa je prav tako lahko potem podobno kot pri tej kopici in greš enostavno s for-zanko čez array (razlika v primerjavi s kopico bi bila v bistvu le v tem, da bi imel pri binarnem drevesu v zaporedju lahko tudi luknje, medtem ko pri kopici tega nimaš, ker je uteženo drevo)
Ko tehnologija odpove, uporabi macolo.
Vredno ogleda ...
| Tema | Ogledi | Zadnje sporočilo | |
|---|---|---|---|
| Tema | Ogledi | Zadnje sporočilo | |
| » | java pomočOddelek: Programiranje | 2040 (1432) | kr?en |
| » | Java metode;Oddelek: Programiranje | 5166 (4358) | ragezor |
| » | algoritm za pot med dvema točkamaOddelek: Programiranje | 1787 (1480) | detroit |
| » | Za programerske teoretikeOddelek: Programiranje | 8985 (5787) | Jerry000 |
| » | Kaj naj si zmislim za O(n^m)?Oddelek: Programiranje | 1114 (999) | Arthur |