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

• 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.

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?

• Í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.

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()

Í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ó.

Í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)!

Í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.

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!

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.

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!

Í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.)

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

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!

Ha a laborfeladatokkal elkészültél, dolgozz a példatárban lévő feladatokon, a szorgalmi feladatokon, a minta vizsgán, vagy a házi feladatodon.

Informatikusok próbálják lekódolni az Algoritmusok és gráfok tárgyon tanult algoritmusokat. Ezzel két legyet lehet ütni egy csapásra, mert két tantárgyat is gyakoroltok egyszerre.