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 | 1947 (1339) | kr?en |
» | Java metode;Oddelek: Programiranje | 4910 (4102) | ragezor |
» | algoritm za pot med dvema točkamaOddelek: Programiranje | 1681 (1374) | detroit |
» | Za programerske teoretikeOddelek: Programiranje | 8779 (5581) | Jerry000 |
» | Kaj naj si zmislim za O(n^m)?Oddelek: Programiranje | 1040 (925) | Arthur |