#1: Zadatak iz SPA Autor/ica: Gost, Postano: 22:28 pon, 7. 2. 2005 Kako da kreiram binarno stablo ako imam zadani prefiks oblik aritmetičkog izraza? Može i samo male upute,ne trebam baš algoritam,samo dobru ideju. Hvala!
#2: Autor/ica: Zvone, Postano: 0:15 sri, 9. 2. 2005 Hm...nije bas uputno na forumu traziti rjesenje zadatka koje treba predati asistentu ako taj asistent cita forum
Pogotovo jer postoji injekcija sa skupa studenata u skup zadataka
No dobro...
Evo male upute: algoritam je jako slican onom za rekonstrukciju binarnog stabla ako su zadani inorder i preorder obilasci (prefix izraz je preorder obilazak stabla kojeg treba stvoriti).
Npr. neka je zadan prefix izraz "*+abc".
* je korijen, slijede opisi lijevog (L) i desnog (D) podstabla.
U korijenu od L je +, slijede opisi njegovog lijevog (LL) i desnog (LD) podstabla.
U korijenu od LL je a, i on nema djece (jer je operand), dakle opis od LL je gotov.
U korijenu od LD je b, i on nema djece (jer je operand), dakle opis od LD je gotov.
Ovim je gotov opis od L; slijedi opis od D.
U korijenu od D je c, i on nema djece (jer je operand), dakle opis od D je gotov.