11. hét: bináris fák

Czirkos Zoltán · 2022.11.10.

Bináris fák – fák építése, mélységi bejárás rekurzióval.

1. Ötödik kis ZH

A hétfői alkalmakon lesz az ötödik kis ZH.

Este pedig a pótzárthelyi...

2. Felkészülés a laborra:

3. Bináris fák: a keretprogram

Az alábbi program létrehoz egy bináris keresőfát. A fa elemei egy egész típusú értéket tartalmaznak. Az órai feladatokat a program által létrehozott fával tudjátok kipróbálni. A létrehozott fa jobb oldalt látható.

class BinFa:
    def __init__(self, ertek):
        self.ertek = ertek
        self.bal = None
        self.jobb = None


def beszur(gyoker, ertek):
    if gyoker is None:
        gyoker = BinFa(ertek)
    elif ertek < gyoker.ertek:
        gyoker.bal = beszur(gyoker.bal, ertek)
    elif ertek > gyoker.ertek:
        gyoker.jobb = beszur(gyoker.jobb, ertek)
    else:
        pass
    return gyoker


def main():
    tesztadat = [15, 96, 34, 12, 14, 56, 21, 11, 10, 9, 78, 43]
    gyoker = None
    for x in tesztadat:
        gyoker = beszur(gyoker, x)


main()

4. Fa kiírása

Írj rekurzív függvényt, amely inorder (bal-gyökér-jobb) bejárja a fát, és kiírja a tárolt elemeket. A számokat növekvő sorrendben kell megkapjad, mert keresőfáról van szó.

5. Elemek száma és összege

Írj rekurzív függvényt, amely megszámolja és visszaadja a fa elemeinek számát! Ellenőrizd az algoritmus által adott eredményt a rajz alapján!

Írj rekurzív függvényt, amely meghatározza a fában tárolt számok összegét! Ellenőrizd ezt is a rajz alapján (vagy a listában tárolt számok alapján)!

6. Elem megkeresése

Írj függvényt, amely megkeres egy elemet a fában, és visszaadja a megtalált csomópont referenciáját! A visszatérési érték legyen None, ha az adott szám a fában nem szerepel.

Tipp
  • Legyen bármi a keresett adat, üres fában nincs benne.
  • Ha a fa gyökerében van a keresett elem, akkor már meg is találtuk.
  • Ha a fa gyökerében kisebb elem van, akkor jobbra kell továbbhaladni.
  • Ha nagyobb elem van ott, akkor viszont balra kell menni.

Ezt a függvényt iteratívan is könnyedén meg lehet csinálni, mert nem kell elágaznia a keresésnek. Választásod szerint adj iteratív vagy rekurzív megoldást!

7. Fa építése

Töröld most ki a fát építő függvényt és a fa csomópontját definiáló osztályt! A feladatod az lesz, hogy megírd ezeket egyedül újra.

Tipp az osztályhoz
  • A bináris fa csomópontjának adattagjai: valamilyen adat, illetve balra és jobbra mutató referenciák.
  • Hozza ezeket létre a konstruktor! Leggyakoribbak a levélelemek, a csomópontokban viszont mindig tárolunk adatot – ebből következik, mit érdemes átvenni a konstruktor paraméterében.
Tipp az építéshez
  • Az üres fa None értékkel reprezentálható. Viszont amikor az első elemet beszúrod, akkor ez a None érték megváltozik: vagyis olyan függvényt kell írnod, amelyik használatakor meg kell változtatni a fa gyökerét tároló változót. Legegyszerűbb ezt úgy megoldani, hogy a függvény visszatér ezzel.
  • Üres fa esetén a függvény létrehozza a csomópontot.
  • Ha nem üres a fa, akkor a bal vagy jobb oldali részfába kell beszúrnia, ha a gyökérben látott elemnél kisebb vagy nagyobb az új szám.
  • Egyenlő nem lehet, mert a fában minden elem egyszer szerepelhet.

8. A fa magassága

Milyen magas a fa? Írj rekurzív, globális változót nem használó függvényt a magasság meghatározására!

Tipp
  • Az üres fa magassága 0.
  • Ha nem üres a fa, akkor a magasságát a nagyobbik részfája határozza meg. A lenti ábra mutat erre példát. Ha bal oldali részfa magassága 2, a jobb oldalié 4, akkor a jobb oldali magasabb, tehát azon múlt.
  • A teljes fa magassága ilyenkor 5.

9. Negálás

Írj függvényt, amely ellentettjére változtat, azaz -1-szeresére szoroz minden elemet a fában!

Keress most meg egy elemet a fentebb megírt keresőfüggvényeddel. Mit tapasztalsz? Miért történik ez? Hogyan módosítanád a kereső függvényt, hogy működjön az így kapott fán? (Ha kell, rajzold le egy kis részletét a gyökértől indulva a negált fának, és képzeletben hajtsd rajta végre az algoritmust! Ki is írathatod a negált fát az inorder bejárás függvényeddel.)

10. Tükrözés

Írj egy rekurzív függvényt, amely tükröz egy paraméterként kapott fát!

Tipp
  • Üres fán nincs mit tükrözni.
  • A fa elemeiben tárolt adatokat sem kell változni. A tükrözés által a szerkezete változik, nem az adatok!
  • A tükrözés megcseréli a bal és jobb oldali részfákat.

Keresés a negált, tükrözött fában

Most működik a módosított kereső függvény? Miért? Írasd ki a fa tartalmát az inorder függvénnyel, vagy készíts rajzot!

11. További feladatok

Ha végeztél, dolgozhatsz a nagy házi feladatodon vagy a kiadott szorgalmi feladatokon is.