# 14. hét: láncolt listák és bináris fák

Czirkos Zoltán · 2025.11.25.

Láncolt listák és bináris fák – listák műveletei, fák építése, mélységi bejárás rekurzióval.

## 1. Felkészülés a laborra:

- A rekurzióról szóló előadás átismétlése.
- A láncolt listákról és bináris fákról tanultak áttekintése.

## 2. Láncolt lista: a keretprogram

Az alábbi program létrehoz egy egyszeres láncolt, strázsa nélküli listát. A következő feladatokat ezzel a listával tudjátok kipróbálni.

    class ListaElem:
        def __init__(self, adat):
            self.adat= adat
            self.kov= None

    def lista_letrehoz():
        eleje= None
        elemek= [8, 14, 13, 17, 1, 19, 16, 5, 3, 11, 2, 15, 9, 10, 6, 22, 4, 7, 18, 27]
        for e in elemek:
            uj= ListaElem(e)
            uj.kov= eleje
            eleje= uj
        return eleje

Másold be egy új projektbe a kódot! (A további feladatokat is abban oldd majd meg!)

Írj függvényt, amely kiírja a képernyőre a listában tárolt számokat! A képernyőn ezt kell kapjad:

     27 18 7 4 22 6 10 9 15 2 11 3 5 16 19 1 17 13 14 8

Miért vannak a listában fordítva a számok, a tömbbeli sorrendhez képest?

## 3. A lista műveletei

- Írj függvényt, ami meghatározza a lista hosszát!
- Írj függvényt, ami hozzáfűz a lista végéhez!
- Írj függvényt, ami megkeres egy elemet és kitörli az első előfordulását a listából!

Ügyelj arra, hogy ezek a függvények üres listára is működjenek!

Tipp
A törlés megvalósítása nem egyszerű. Ha a lista első elemét töröljük, módosítani kell az „eleje” referenciát, (ii) ha középről kell törölnünk, akkor szükség van egy lemaradó referenciára, mert az előző elemre is szükség van. Valahogy így:

        mozgo= eleje
        lemarado= None
        while mozgo != None and mozgo.adat != mit:
            lemarado= mozgo
            mozgo= mozgo.kov

Utána már a piros nyilak mutatják, mit kell csinálni.

## 4. 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()

## 5. 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ó.

## 6. 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)!

## 7. 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!

## 8. 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.

## 9. 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.

## 10. 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.)

## 11. 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!