„Algoritmuselmélet - ZH, 2013.04.03.” változatai közötti eltérés
A VIK Wikiből
| 34. sor: | 34. sor: | ||
}} | }} | ||
*Első lépésnek írjuk fel egy táblázatba a számokat (az oszlopszámot tudjuk, ez esetben 11, sorok száma meg majd alakul...). | *Első lépésnek írjuk fel egy táblázatba a számokat (az oszlopszámot tudjuk, ez esetben 11, sorok száma meg majd alakul...). | ||
*A továbbiakban az i. sorban jelöljük, hogy melyik elem a gyökér (=), és hogy melyek a nála kisebbek (<), avagy nagyobbak (>) ''(a képen keretezéssel jelzem, hogy melyik az éppen figyelt lista).'' Ez azért hasznos, mert a posztorder bejárás során, ezzel a technikával mindig olyan sorrendet kell kapjunk, hogy <math> < < < ... < < > > ... > > = </math>, vagyis nem állhat fel olyan helyzet, hogy <math> ... < > < ...=</math> vagy <math> ... > < > ...=</math> | *A továbbiakban az i. sorban jelöljük, hogy melyik elem a gyökér (=), és hogy melyek a nála kisebbek (<), avagy nagyobbak (>) ''(a képen keretezéssel jelzem, hogy melyik az éppen figyelt lista).'' Ez azért hasznos, mert a posztorder bejárás során, ezzel a technikával mindig olyan sorrendet kell kapjunk, hogy <math> < < < ... < < > > ... > > = </math>, vagyis nem állhat fel olyan helyzet, hogy <math> ... < > < ...=</math> vagy <math> ... > < > ...=</math>. | ||
**Az 1. sorban a 9 lesz a gyökér. Felrajzoljuk a 9-t gyökérnek. ''(Bal oldalt lesz a hiba, de gyakorlásképp nézzük inkább a jobb oldalt.)'' | **Az 1. sorban a 9 lesz a gyökér. Felrajzoljuk a 9-t gyökérnek. ''(Bal oldalt lesz a hiba, de gyakorlásképp nézzük inkább a jobb oldalt.)'' | ||
**A 2. sorban a 12 lesz a gyökér, így a 12-est felrajzoljuk a 9-es jobb fiának. Nála csak a 11 a kisebb (a vizsgált listában), így a 11-t berajzoljuk a 12 bal fiának. | **A 2. sorban a 12 lesz a gyökér, így a 12-est felrajzoljuk a 9-es jobb fiának. Nála csak a 11 a kisebb (a vizsgált listában), így a 11-t berajzoljuk a 12 bal fiának. | ||
A lap 2013. június 12., 20:34-kori változata
2013.04.03. ZH megoldásai
1. Feladat
TODO
Megoldás
TODO
2. Feladat
TODO
Megoldás
TODO
3. Feladat (Van megoldás)
Kaphatjuk-e az 1,7,3,6,11,15,22,17,14,12,9 számsorozatot úgy, hogy egy (a szokásos rendezést használó) bináris keresőfában tárolt elemeket posztorder sorrendben kiolvasunk?
Megoldás
Első lépésnek írjuk fel egy táblázatba a számokat (az oszlopszámot tudjuk, ez esetben 11, sorok száma meg majd alakul...).
A továbbiakban az i. sorban jelöljük, hogy melyik elem a gyökér (=), és hogy melyek a nála kisebbek (<), avagy nagyobbak (>) (a képen keretezéssel jelzem, hogy melyik az éppen figyelt lista). Ez azért hasznos, mert a posztorder bejárás során, ezzel a technikával mindig olyan sorrendet kell kapjunk, hogy , vagyis nem állhat fel olyan helyzet, hogy vagy .
Megjegyzés a feladathoz
- Szokásos rendezést használó bináris keresőfa:
- Postorder:
- Rekurzívan . Magyarul előbb meglátogatja a gyökérnél kisebbeket, utána a nagyobbakat, és ezután jön csak a gyökér.
- Egyik fontos tulajdonsága, hogy a gyökér az mindig a (figyelt) lista végén van.
- Az 1. sorban a 9 lesz a gyökér. Felrajzoljuk a 9-t gyökérnek. (Bal oldalt lesz a hiba, de gyakorlásképp nézzük inkább a jobb oldalt.)
- A 2. sorban a 12 lesz a gyökér, így a 12-est felrajzoljuk a 9-es jobb fiának. Nála csak a 11 a kisebb (a vizsgált listában), így a 11-t berajzoljuk a 12 bal fiának.
- A 3. sorban 14 lesz a gyökér, így e 14-est felrajzoljuk a 12-es jobb fiának.
- A 4. sorban a 17 lesz a gyökér, így ez a 14-es jobb fia lesz. A 15 és 22 pedig értelemszerűen a bal, és jobb fia lesz 17-nek.
- Az 5. sorban a gyökér a 6 lesz, így azt berajzoljuk a 9-es bal fiának. És itt látszik is, hogy hiba van, hiszen sorrend van, ebből következik, hogy ilyen fa nem létezhet.
4. Feladat
TODO
Megoldás
TODO
5. Feladat
TODO
Megoldás
TODO
6. Feladat
TODO
Megoldás
TODO
7. Feladat
TODO
Megoldás
TODO
8. Feladat
TODO
Megoldás
TODO
