| Prethodna tema :: Sljedeća tema |
| Autor/ica |
Poruka |
zzsan
Forumaš(ica)
Pridružen/a: 25. 11. 2005. (20:53:14)
Postovi: (89)16
|
|
| [Vrh] |
|
vsego
Site Admin
Pridružen/a: 06. 10. 2002. (22:07:09)
Postovi: (3560)16
Spol: 
Lokacija: /sbin/init
|
 Postano: 22:39 ned, 19. 11. 2006 Naslov: Re: BTREE |
    |
|
|
[quote="zzsan"]imam PREORDER obilazak stabla: HIDJKEBLMFNOGCA
I INORDER obilazak: HDIBJEKALFMCNGO
Dakle, korijen je A, desno dijete je C. Sad me zanima, kad dobim takve zapise obilazaka kak da odredim koje mi je lijevo dijete?[/quote]
Ne bash... :?
[list=1][*] Preorder prvo posjeti korijen :arrow: korijen je 'H' :)
[*] Inorder prvo posjeti lijevo podstablo, zatim korijen i zatim desno podstablo :arrow:
sve lijevo od 'H' (u inorderu) je lijevo podstablo, a sve desno od 'H' je desno podstablo :arrow:
lijevo podstablo je prazno, a inorder desnog je "DIBJEKALFMCNGO"; ista slova poredana u preorderu su "IDJKEBLMFNOGCA"
[*] Sad, za desno podstablo, imas:
Preorder: IDJKEBLMFNOGCA :arrow: korijen je 'I'
Inorder: DIBJEKALFMCNGO :arrow: inorderi podstabala su "D" i "BJEKALFMCNGO"
Dakle, lijevo podstablo je 'D', a desno sve bez 'I' i 'D'
[*] Desno podstablo:
Preorder: JKEBLMFNOGCA :arrow: korijen je 'J'
Inorder: BJEKALFMCNGO :arrow: inorderi podstabala su "B" i "EKALFMCNGO"
No, sada preorder ne stima (jer prva dva znaka nisu "JB", a trebali bi biti (lijevo podstablo u svim obilascima ide prije desnog)[/list:o]
:?
Provjeri jesi li dobro prepisao zadatak (mozda je ono postorder?), pa primijeni opisani postupak... 8)
[size=7]A mozda sam i ja fulao...[/size] :oops:
| zzsan (napisa): | imam PREORDER obilazak stabla: HIDJKEBLMFNOGCA
I INORDER obilazak: HDIBJEKALFMCNGO
Dakle, korijen je A, desno dijete je C. Sad me zanima, kad dobim takve zapise obilazaka kak da odredim koje mi je lijevo dijete? |
Ne bash... 
- Preorder prvo posjeti korijen
 korijen je 'H' 
- Inorder prvo posjeti lijevo podstablo, zatim korijen i zatim desno podstablo
sve lijevo od 'H' (u inorderu) je lijevo podstablo, a sve desno od 'H' je desno podstablo
lijevo podstablo je prazno, a inorder desnog je "DIBJEKALFMCNGO"; ista slova poredana u preorderu su "IDJKEBLMFNOGCA"
- Sad, za desno podstablo, imas:
Preorder: IDJKEBLMFNOGCA korijen je 'I'
Inorder: DIBJEKALFMCNGO inorderi podstabala su "D" i "BJEKALFMCNGO"
Dakle, lijevo podstablo je 'D', a desno sve bez 'I' i 'D'
- Desno podstablo:
Preorder: JKEBLMFNOGCA korijen je 'J'
Inorder: BJEKALFMCNGO inorderi podstabala su "B" i "EKALFMCNGO"
No, sada preorder ne stima (jer prva dva znaka nisu "JB", a trebali bi biti (lijevo podstablo u svim obilascima ide prije desnog)
Provjeri jesi li dobro prepisao zadatak (mozda je ono postorder?), pa primijeni opisani postupak... 
A mozda sam i ja fulao... 
_________________ 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.  |
|
| [Vrh] |
|
GauSs_
Moderator
Pridružen/a: 28. 01. 2004. (21:01:17)
Postovi: (53C)16
Spol: 
Lokacija: 231
|
|
| [Vrh] |
|
zzsan
Forumaš(ica)
Pridružen/a: 25. 11. 2005. (20:53:14)
Postovi: (89)16
|
|
| [Vrh] |
|
zzsan
Forumaš(ica)
Pridružen/a: 25. 11. 2005. (20:53:14)
Postovi: (89)16
|
|
| [Vrh] |
|
vsego
Site Admin
Pridružen/a: 06. 10. 2002. (22:07:09)
Postovi: (3560)16
Spol:
Lokacija: /sbin/init
|
| Postano: 15:37 uto, 21. 11. 2006 Naslov: |
|
|
|
[quote="zzsan"]Jel ima drugog načina osim rekurzije za rekonstrukciju binarnog stabla? I kak bi on glasio? Ova moja rekurzija je previse spetljana...[/quote]
AFAIK nema; radije napisi manje spetljanu rekurziju. :D
0. Ako je inorder string duljine 0, vrati prazno stablo
1. Neka je [tt]r[/tt] zadnji znak postordera; nadji [tt]r[/tt] u inorderu (to je pozicija [tt]p[/tt])
2. Pozovi rekurziju za prvih [tt]p[/tt] znakova postordera i inordera (dakle, za podstringove koji se sastoje od znakova s indeksima od 0 do [tt]p-1[/tt]) :arrow: dobijes stablo [tt]TL[/tt]
3. Pozovi rekurziju za zadnjih [tt]strlen(inorder)-p-1[/tt] znakova postordera i inordera (dakle, za podstringove koji pocinju na lokaciji [tt]p+1[/tt] i idu do kraja) :arrow: dobijes stablo [tt]TR[/tt]
4. Kreiraj stablo s korijenom [tt]r[/tt], lijevim podstablom [tt]TL[/tt] i desnim podstablom [tt]TR[/tt], te ga vrati kao rezultat funkcije
Simple! :D
(samo oprezno, pisah ovo iz glave :oops:)
| zzsan (napisa): | | Jel ima drugog načina osim rekurzije za rekonstrukciju binarnog stabla? I kak bi on glasio? Ova moja rekurzija je previse spetljana... |
AFAIK nema; radije napisi manje spetljanu rekurziju. 
0. Ako je inorder string duljine 0, vrati prazno stablo
1. Neka je r zadnji znak postordera; nadji r u inorderu (to je pozicija p)
2. Pozovi rekurziju za prvih p znakova postordera i inordera (dakle, za podstringove koji se sastoje od znakova s indeksima od 0 do p-1) dobijes stablo TL
3. Pozovi rekurziju za zadnjih strlen(inorder)-p-1 znakova postordera i inordera (dakle, za podstringove koji pocinju na lokaciji p+1 i idu do kraja) dobijes stablo TR
4. Kreiraj stablo s korijenom r, lijevim podstablom TL i desnim podstablom TR, te ga vrati kao rezultat funkcije
Simple!
(samo oprezno, pisah ovo iz glave )
_________________ 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. |
|
| [Vrh] |
|
|
