8. vje~zbe iz C-a -- 2. zadatak

✓XHTML1

U datoteci stablo.in nalaze se dvije rije~ci, svaka u svom redu, duljine <=70, sastavljene od istih slov~a (svako slovo se pojavljuje to~cno dvaput, jednom u prvom a jednom u drugom redu). One predstavljaju inorder i preorder obilazak nekog stabla ~ciji ~cvorovi su slova. Va~s program treba:

1. pro~citati stablo.in, i provjeriti jesu li unutra stvarno obilasci istog stabla
2. rekonstruirati to stablo (vidjeti dolje za algoritam)
3. ispisati postorder obilazak stabla
4. ispisati visinu stabla (najdulji put od vrha do lista)
5. ispisati sve listove u stablu

Algoritam rekonstrukcije

Imamo dva stringa, pre i in, koji predstavljaju preorder i inorder obilazak. To su argumenti rekurzivne funkcije, koja vra~ta stablo (pointer na ~cvor) s tim obilascima.
Ako su prazni (ako je jedan prazan, oba su, jer su jednake duljine), vratimo prazno stablo.

Ina~ce, pogledajmo prvo slovo pre stringa, ono mora biti korijen. Stavimo ga u korijen. Zatim na~demo to slovo u inorder obilasku (mora se pojaviti to~cno jednom -- ako ne, javimo gre~sku). Ono nam prirodno rastavlja in string na dva stringa, in1 i in2. Pogledajmo njihove duljine, neka su to l1 i l2.

Mora biti l1+l2+1=n, gdje je n duljina od in, kao i duljina od pre. Pa rastavimo string pre bez prvog slova, koji je duljine n-1, na dva dijela duljine l1 i l2, i ozna~cimo ih s pre1 i pre2.

Sada rekurzivno pozovemo funkciju s in1 i pre1 kao inorder i preorder obilaskom, i ono ~sto nam ona vrati, mora biti lijevo podstablo korijena K. Stavimo to u lijevo podstablo.
Opet rekurzivno pozovemo funkciju s in2 i pre2, i ono ~sto nam vrati stavimo desno od K. Vratimo K.

Za 4 boda mo~zete pretpostaviti da su pre i in stvarno preorder i inorder obilasci istog stabla. Za 5 bodova morate to i provjeriti (sve ~sto tada smijete pretpostaviti je da su pre i in nizovi slova duljine najvi~se 70), te javiti gre~sku ako nisu.