» »

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.

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.

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

Spura ::

Spura je izjavil:

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)
Ko tehnologija odpove, uporabi macolo.


Vredno ogleda ...

TemaSporočilaOglediZadnje sporočilo
TemaSporočilaOglediZadnje sporočilo
»

java pomoč

Oddelek: Programiranje
211947 (1339) kr?en
»

Java metode;

Oddelek: Programiranje
354910 (4102) ragezor
»

algoritm za pot med dvema točkama

Oddelek: Programiranje
161681 (1374) detroit
»

Za programerske teoretike

Oddelek: Programiranje
478779 (5581) Jerry000
»

Kaj naj si zmislim za O(n^m)?

Oddelek: Programiranje
81040 (925) Arthur

Več podobnih tem