prreorder, postorder, inorder

[ivanzub]

Ukratko, zadatak ide ovako:

zadan je postorder i inorder obilazak nekog stabla kojeg treba rekonstruirati. to nije problem.

no trazi se da se nacrta jos jedno stablo koje ce imati isti postorder i inorder obilazak za kao i zadano stablo.
Kako se to radi?

[arya]

nikako. stablo je jedinstveno određeno postorder i inorder obilaskom.

_________________
kalendar

[ivanzub]

to sam si i ja mislila, ali mi nije jasno zasto bi nas onda trazili da tako nesto napravimo. cemu takva pitanja??? (inace, to je 12. zadatak iz zadataka za vježbu)

[Luuka]

Traži se još jedno stablo koje ima isti PREorder i POSTorder ko ovo traženo...a stablo nije jednoznačno određeno sa pre- i postorderom...

_________________
"Bolje bi prolazio na faxu da sam na drogama nego na netu" - by a friend of mine
"Poslije spavanja doma spavanje bilo di mi je najdraža stvar" - by the same guy

[napraviculom]

bilo je napomenuto na vjezbama da stablo nije jednoznacno odredjeno pomocu pre- i postordera i da se to pokaze (kontra)primjerom. mozda bi tak nesto moglo bit u kolokviju.
EDIT: tako je

_________________
"I'm the operator with my pocket calculator"

[ma]

znači kad imamo inorder i još jedan od preostala dva obilaska - stablo je jedinstveno određeno, a kad imamo preorder i postorder, tada nije

_________________
ima let u finish

[Luuka]

Tak je ma...

A kad bi se tražio kontraprimjer, koja bi konstrukcja upalila? Možda da se neko dijete okrene?

_________________
"Bolje bi prolazio na faxu da sam na drogama nego na netu" - by a friend of mine
"Poslije spavanja doma spavanje bilo di mi je najdraža stvar" - by the same guy

[skywalker]

da, baš preko tog okretanja, evo jedan prilično jednostavan primjer..
u prvom slucaju, neka je korijen 1 a desno dijete 2
a u drugom neka je korije 1 a lijevo dijete 2
tada je postorder za oba dva
21
a preorder za oba dva je
12
no
inorder za prvo je
21
a za drugo
12
znaci
imamo dva stabla
sa istim
pre i post

[mala]

ajde probajte ovo nacrtat (pazite, binarno je!)
PRE: 01342
POST: 43120

[woodstock]

0 je korijen, lijevo dijete mu je 1, a desno mu je 2, a 3 i 4 su djeca od 1...ja mislim da je to točno...ako nije sorry

[Luuka]

Ja bi reko da je 0 korijen, lijevo 1, desno 2, 3 lijevo dijete od 1 a 4 lijevo dijete od 3...

@woodstock ovom tvom je ili preorder ili postorder krivi (ovisi kak staviš djecu od 1)...

_________________
"Bolje bi prolazio na faxu da sam na drogama nego na netu" - by a friend of mine
"Poslije spavanja doma spavanje bilo di mi je najdraža stvar" - by the same guy

[mala]

Iskreno, bacila sam papir u smeće , to je bio samo primjer da stablo nije jedinstveno određeno. 4 može bit i lijevo i desn, a kod binarnih to nije isto

[ma]

[woodstock]