Ajde da resimo taj praktican problemcic :)
Problemcic je inace dosta poznat, secam se da sam ga radio nekad davno...
Elem. Za one koji ne znaju (a napisacu nesto i o tome uskoro), preorder obilazak stabla je obliazak redosledom: root, levo poddrvo, desno poddrvo (naravno to rekurzivno), inorder redom: levo poddrvo, root, desno poddrvo, a postorder redom: levo poddrvo, desno poddrvo, root.
Za ovaj konkretan problem: Uzmemo preorder. Prvo slovo u njemu je definitivno root celog drveta. U tvom slucaju, to je A. Sad podelimo inorder na dva dela, levo i desno od A:
levo: EINSCFBTGPDLMK
desno: nista (boze, gde nadje bas ovakav primer :D:D)
Jasno je da je ovo levo celo levo poddrvo, a desno celo desno poddrvo.
Isto tako, mozemo podeliti i preorder na dva dela, sto ce da budu levo i desno poddrvo, respektivno, jer znamo da ce se u njemu prvo naci svi cvorovi levog poddrva, pa onda svi desnog, a posto znamo koji su cvorovi u levom koji u desnom poddrvetu znamo i gde je granica izmedju njih. U ovom slucaju:
levo: TNEIFCSBDGPMLK
desno: prazno, naravno
Znaci za sad sve sto znamo je:
Code:
A
/
Sad smo problem sveli na 2 identicna problema, jer su dobijeni nizovi bas inorder i preorder obilasci levog i desnog poddrveta. Sada mozemo rekurzivno pozvati proceduru za levo i desno posebno. Ovde desnog drveta nece biti, ali idemo dalje sa levim:
root: T
levo (inorder): EINSCFB
desno (inorder): GPDLMK
levo (preorder): NEIFCSB
desno (preorder): DGPMLK
Sada imamo:
Code:
A
/
T
/ \
Sad za novi levi i desni nastavljamo...
levo:
root: N
levo (in): EI
desno (in): SCFB
levo (pre): EI
desno (pre): FCSB
desno:
root: D
levo (in): GP
desno (in): LMK
levo (pre): GP
desno (pre): MLK
Znaci imamo:
Code:
A
/
T
/ \
N D
/ \ / \
Da ne smaram, nadam se da je jasno :)
Nastavljamo u istom stilu, i dobijemo celo drvo:
Code:
A
/
T
/ \
/ \
/ \
/ \
/ \
/ \
N D
/ \ / \
/ \ / \
/ \ / \
E F G M
\ / \ \ / \
I C B P L K
/
S
Nadam se da nikom nije problem da ovo i iskodira...
I HAD A NIGHTMARE
IT ALL STARTED NORMAL
10101010
10110011
THEN ALL OF A SUDDEN
1100102
GAAAAH
_____________________________
www.princeton.edu/~skrstic
www.niwifi.co.sr