Zadatak sa pismenog 19.rujna 2005.

[LSSD]

Molila bih pomoc oko slijedeca dva zadatka:

1.Kazemo da je cvor v binarnog stabla T k-potomak cvora u ako se v nalazi u podstablu od T kojem je u korijen i pri tome je nivo cvora v za k veci od nivoa cvora u. Tako su npr. djeca nekog cvora njegovi 1-potomci, djeca od djece 2-potomci,itd. Napisite funkciju sa prototipom
labeltype potomak(BTREE T,int k) koja vraca label onog cvora bin. stabla T koji ima najvise k-potomaka. Ako ima vise takvih cvorova,vratite label bilo kojeg. Funkcija treba biti neovisna o implementaciji atp-a BTREE,ne smijete koristiti pomocne atp-ove. Mozete definirati pomocne funkcije i globalne varijable.

2.Napisite funkciju sa prototipom labeltype najvisi_list(BTREE T) koja vraca label onog lista bin.stabla koji ima najmanji nivo. Ako ima vise listova na najmanjem nivou, treba vratiti onaj sa najmanjim label.Funkcija treba biti neovisna o implementaciji atp-a BTREE, smijemo koristiti i druge pomocne atp-ove, te definirati pomocne funkcije.

_________________
' Zasto jednostavno kad moze i komplicirano?'

[vsego]

1. Trcis (npr. rekurzivno) po stablu i trazis koliko djece ima svaki cvor. Kad god nadjes nekoga tko ima vise djece nego je dotadasnji maximum, pamtis novi maximum i label (globalne varijable; inicijalizacija: max=0, max_label = root).

2. Isto kao ovo gore, samo je kriterij usporedbe drugaciji ("ako je nivo manji od dosadasnjeg minimuma ili ako mu je jednak, uz manji label onda..."). Ako ne smijes imati globalne varijable, poigras se s argumentima funkcije.

_________________
U pravilu ignoriram pitanja u krivim topicima i kodove koji nisu u [code]...[/code] blokovima.
Takodjer, OBJASNITE sto vas muci! "Sto mi je krivo?", bez opisa u cemu je problem, rijetko ce zadobiti moju paznju.

[LSSD]

Ali, zar se u prvom zadatku ne trazi onaj cvor koji ima najvise k-potomaka, a ne potomaka opcenito?

_________________
' Zasto jednostavno kad moze i komplicirano?'

[vsego]

Tako je to kad izbacis dva zadatka odjednom. Da, u pravu si; ja sam brojao djecu (dakle 1-potomke).

Dakle, treba ti pomocna rekurzija koja ce za svaki cvor brojati koliko ima k-djece (to sredis s dodatnim parametrom u deklaraciji same rekurzije).

Ako nije jasno, zapomazi!

_________________
U pravilu ignoriram pitanja u krivim topicima i kodove koji nisu u [code]...[/code] blokovima.
Takodjer, OBJASNITE sto vas muci! "Sto mi je krivo?", bez opisa u cemu je problem, rijetko ce zadobiti moju paznju.