[ ivan_nedeljkovic @ 21.05.2012. 15:27 ] @
Iz vise razloga u koje ne bih ulazio imam niz u kom su smesteni koreni elementi, deca, unuci, praunuci.....A povezani su atributima id i parent_id, znaci koreni element ima npr id = 1, a njegova deca imaju svoje id-eve (2,3..) ali ima je parent_id = 1. Potrebno mi je da pronadjem krajnje elemente u nizu koji nemaju svoju decu.
Npr elementi u nizu su:

rb parent_id id
1 -1 1
2 1 2
3 1 3
4 2 4
5 2 5
6 4 6

element sa rednim brojem 1 ima parent parent_id=-1 sto znaci da je to koreni element a njegov id=1. Dva elementa imaju id=1 sto znaci da su to deca korenog elementa itd. Element sa rednim brojem 3 nema vise dece (tj nema elementata ciji je parent_id jednak njegovom id-u).
Problem je sto efikasnije pronaci sve krajnje elemente (u konkretnom primeru to su elementi sa rednim brojevima 3, 5, 6)

Hvala unapred na pomoci :)
[ Mihajlo Cvetanović @ 21.05.2012. 15:55 ] @
Rezerviši jedan bool niz (recimo da se zove is_parent) koji je veličine ulaznog niza (recimo da se ulazni niz zove parent_child). Indeks ovog bool niza je zapravo id. Pretpostavljam da su ovi id brojevi "pitomi", to jest da nema rupa, i najveći id je jednak veličini ulaznog niza. Iteriraj kroz ulazni niz po recimo indeksu ix, i postavi is_parent[parent_child[ix].parent_id] = true. Na kraju rada petlje svi koji su true su nekome roditelji, a svi ostali nisu nikome roditelji, i to su ti koje tražiš.
[ djoka_l @ 21.05.2012. 15:59 ] @
Napravi niz HasChild čija je dužina ista kao dužina niza sa podacima i incijalizuj ga svim nulama.
Prođi kroz niz sa podacima i za svaki parent_id različit od minus jedan postavi HasChild[parent_id] na 1.
Na kraju će niz HasChild imati 0 na onim mestima koji predstavljaju id elemnta bez dece.