Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

Preorder, inorder sekvenca, crtanje binarnog drveta

[es] :: Art of Programming :: Preorder, inorder sekvenca, crtanje binarnog drveta

[ Pregleda: 6289 | Odgovora: 1 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

anon315

Član broj: 315
Poruke: 1657
*.beoland.sezampro.yu.



+13 Profil

icon Preorder, inorder sekvenca, crtanje binarnog drveta20.05.2005. u 19:42 - pre 229 meseci
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

 
Odgovor na temu

Srđan Krstić
Srđan Krstić
Princeton, NJ

Član broj: 7526
Poruke: 416
*.rcub.bg.ac.yu.

Jabber: srkiboy@elitesecurity.org
ICQ: 193836365
Sajt: www.princeton.edu/~skrsti..


Profil

icon Re: Preorder, inorder sekvenca, crtanje binarnog drveta20.05.2005. u 23:08 - pre 229 meseci
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
 
Odgovor na temu

[es] :: Art of Programming :: Preorder, inorder sekvenca, crtanje binarnog drveta

[ Pregleda: 6289 | Odgovora: 1 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.