[ anon315 @ 20.05.2005. 19:42 ] @
U pitanju je binarno stablo i preorder, inorder i postorder obilazak. Ovo nije problem.

Medjutim, javio mi se zadacic gde imam inorder i preorder poredak, a na osnovu toga treba nacrtati izgled drveta.

Kako se resava ovaj (inverzni) problem? Kako da krenem, sta da gledam itd.?

Evo primera:

preorder: ATNEIFCSBDGPMLK
inorder: EINSCFBTGPDLMKA

[ Srđan Krstić @ 20.05.2005. 23:08 ] @
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...