„Algoritmuselmélet - ZH, 2013.04.03.” változatai közötti eltérés

18. sor:

}}

===3. Feladat===

===3. Feladat (Van megoldás)===

~~TODO~~

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?

{{Rejtett

|mutatott=<big>'''Megoldás'''</big>

|szöveg=

~~TODO~~

{{Rejtett

|mutatott=<big>''Megjegyzés a feladathoz''</big>

|szöveg=

*Szokásos rendezést használó bináris keresőfa: <math>bal(x) < x < jobb(x)</math>

*Postorder:

**Rekurzívan <math> bal(x) \rightarrow jobb(x) \rightarrow x </math>. 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'''.

}}

*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>

**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 <math> < > < </math> sorrend van, ebből következik, hogy ilyen fa nem létezhet.

::::::::::[[File:post_tabla.GIF|400px]] [[File:graf.png|300px]]

}}

@@ 18. sor: / 18. sor: @@
 }}
-===3. Feladat===
+===3. Feladat (Van megoldás)===
-TODO
+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?
 {{Rejtett
 |mutatott=<big>'''Megoldás'''</big>
 |szöveg=
-TODO
+{{Rejtett
+|mutatott=<big>''Megjegyzés a feladathoz''</big>
+|szöveg=
+*Szokásos rendezést használó bináris keresőfa: <math>bal(x) < x < jobb(x)</math>
+*Postorder:
+**Rekurzívan <math> bal(x) \rightarrow jobb(x) \rightarrow x </math>. 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'''.
+}}
+*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>
+**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 <math> < > < </math> sorrend van, ebből következik, hogy ilyen fa nem létezhet.
+::::::::::[[File:post_tabla.GIF|400px]] [[File:graf.png|300px]]
 }}