Mikulás
A Mikulás a szánjával nekihajtott a fent látható, gyökerével adott fának. A csomagok a puttonyából kihullottak és szétszóródtak a fa ágain. Ezért a Mikulás felmászik a fára, végigjárja az összes ágát, és az ott található ajándékokat összegyűjti. Mindet a fa gyökeréhez cipeli. Az egyes ágakon található ajándékok számai a fa elemeiben tárolt egész érték által adottak. Feladat: megírni azt a függvényt, amely a gyökérnél összegzi a fában tárolt elemeket, míg az összes többi, fában tárolt egészet kinullázza.
Szintek sorszáma
0
/ \
1 1
/ \ \
2 2 2
Definiálj bináris fa típust, melynek csomópontjai egész számokat tartalmaznak!
Írj függvényt, amelyik bejárja a fát, és minden csomópontba beírja azt, hogy hányadik szinten van! A fa gyökere a nulladik szint.
Az ábra bejárás után mutajta egy ilyen fa tartalmát.
Cseresznye
Nevezzük cseresznyének az olyan részletet a bináris fában, ahol egy csomópontnak pontosan két gyereke van, azoknak pedig már nincsenek további gyerekeik!
Írj függvényt, amely paraméterként kap egy bináris fát, és megadja, hány cseresznye van rajta!
Kukac
Egy bináris fa egész számokat tárol. Definiáld az ehhez szükséges osztályt! Írj függvényt, amelyik megmondja egy ilyen fáról, hogy kukac-e. Másképp fogalmazva, listává fajult-e, vagyis úgy néz-e ki, mint a lent látható fák. A visszatérési értékében jelezze ezt, logikai igaz értékkel. Írj egy rövid programrészt, amelyben definiálsz egy fát, és meghívod arra a fára a megírt függvényt.
o vagy o vagy o
/ \ /
o o o
/ \ \
o o o
Pontosan kettő vagy nulla leszármazott
Egy bináris fa szavakat tárol. Definiáld az ehhez szükséges osztályt! Írj függvényt, amelyik megmondja egy ilyen fáról, hogy minden csomópontnak pontosan kettő vagy nulla leszármazottja van-e. A visszatérési értékében jelezze ezt, logikai igaz értékkel. Írj egy rövid programrészt, amelyben definiálsz egy fát, és meghívod arra a fára a megírt függvényt.
o
/ \
/ \
o o
/ \ / \
o o o o
ez pl. ilyen
o
/ \
/ \
o o
/ \ \
o o o
ez meg nem
Meddig van teljesen kitöltve?
Írj egy függvényt, amelyik megkapja egy fának a gyökerét, és megmondja, hogy a fa felső hány szintje van teljesen kitöltve!
Megoldás
Onnantól van nem teljesen kitöltve, ahol van benne egy None referencia. Tehát a gyökérhez legközelebbi
None referenciát kell keresni. Ha a gyökér maga is None, akkor ez a távolság nulla. Ha nem, akkor 1 + a
két részfából a kisebbik érték.
Úgy is lehet gondolkozni, hogy egy fa adott szintjein lévő elemek száma egy teljesen kitöltött fában a kettő hatványait adják ki: 1, 2, 4, 8 stb. Ameddig ez igaz a szintekre, addig teljesen ki van töltve. Már csak kell egy ciklus, amelyik az egyre mélyebb szinteket ellenőrzi a külön segédfüggvény hívásával. Ez sokkal lassabb megoldás, de helyes.
Adott szavak között
Egy bináris fa szavakat tárol. Definiáld a szükséges osztályt! Írj függvényt, amelyik megszámolja, hogy egy ilyen fában hány olyan csomópont van, amelyik a „dinnye” és a „papaja” közötti szavakat tárolja az ABC-ben (beleértve pontosan ezeket is.) Az eredményt visszatérési értékként adja. Írj egy rövid programrészt, amelyben definiálsz egy fát, és meghívod arra a fára a megírt függvényt.
Keresés rendezetlen fában
Írj rekurzív függvényt, amely nem feltételez semmilyen rendezettséget a fa elemei részéről (az értékek részéről), és úgy keres meg egy karaktert a fenti fában!
Tipp
- Ha üres a fa, akkor nincs meg a keresett elem.
- Ha a gyökérelem pont az, amit keresünk, akkor arra kell visszatérni referenciával.
- Amúgy lehet, hogy a bal oldali részfában lesz. Ha ott megtaláljuk, akkor egy onnan származó referenciával kell visszatérni.
- Ugyanez lehet a jobb oldali részfánál is.
- Ha egyikben sem – akkor
None.