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

Czirkos Zoltán · 2019.07.25.

Gyakorlófeladatok az előadás anyagához kapcsolódóan.

1. Bináris fák

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!

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.

2. Bináris fák – összetettebb feladatok

Törlés a fából

A tananyagban nem szerepel a bináris fából törlés, de nem nehéz megcsinálni.

  • Ha a törlendő elem levél, simán törölhető.
                5                       5
               / \                     / \
              3   8                   3   8
             /   / \                 /   / \
            2   6   9               2   6   9
           /     \   \             /         \
          1       7   10          1           10
    
  • Ha egy gyereke van, akkor is. Természetesen ilyenkor helyettesíteni kell a töröltet a gyerekével:
                5                       5
               / \                     / \
              3   8                   3   8
             /   / \                 /   / \
            2   6   9               2   7   9
           /     \   \             /         \
          1       7   10          1           10
    
  • Nehézség csak akkor adódik, ha a törlendő elemnek két gyereke van, mivel ilyenkor az egyetlen törölt elem helyét nem foglalhatja el a két gyereke:
                5
               / \
              3   8
             /   / \
            2   6   9
           /     \   \
          1       7   10
    
    Ilyenkor a törlendő elem tartalmát helyettesíteni kell akár az in-order bejárás szerint utána következő, akár az in-order bejárás szerint őt megelőző elemmel (mindegy, hogy melyikkel, lent mind a kettő ki van emelve). Utána pedig a helyettesítő elem könnyedén törölhető, mivel bizonyítható, hogy annak nulla vagy egy gyereke volt csak, tehát a probléma vissza van vezetve az előző két esetek egyikére.
                5                       5                       5
               / \                     / \                     / \
              3   8                   3   7                   3   7
             /   / \                 /   / \                 /   / \
            2   6   9               2   6   9               2   6   9
           /     \   \             /     \   \             /         \
          1       7   10          1       7   10          1           10
    

Feladatok:

  • Gondold ki, hogyan lehet megtalálni egy adott elemet követő, vagy adott elemet megelőző elemet! Ehhez ne másold ki a fát lineáris adatszerkezetbe (tömbbe vagy listába), az felesleges.
  • Magyarázd meg, miért igaz az a kijelentés, hogy az így megtalált elemnek nulla vagy egy gyereke van csak!
  • A törlésnél figyelni kell arra, hogy a szülő elem valamelyik referenciájára, vagy esetleg a fa gyökere módosul. Ezt a problémát úgy oldhatod meg, hogy mindig visszatérsz a fa (új) gyökerével.
  • Írj programot, amelyben egy függvénnyel tudod egy keresőfa egy adott elemét törölni!

Keresőfa-e

Írj függvényt, amely paraméterként egy egész számot tartozó fát kap, visszatérési értékében pedig azt jelzi, hogy ez rendelkezik-e keresőfa tulajdonsággal, vagy nem! Vagyis balra mindig a gyökértől kisebb, jobbra mindig a gyökértől nagyobb számok vannak, mindenhol.

Vizsgáld meg az algoritmusod futási idejét! Hogyan függ a fa csúcspontjainak számától?

Ha nem O(n) időben fut az algoritmusod, oldd meg azt O(n) időben is!

Fát másol, fák egyformák-e

Definiálj egy adatszerkezetet, amelyik karaktereket tároló bináris fa létrehozására alkalmas!

Írj egy függvényt, amelyik paraméterként egy ilyen bináris fa gyökerére mutató referenciát kap! Visszatérési értéke legyen egy másik bináris fa gyökerének referenciája, amelyik az előbbinek a másolata! (A másolást is végezze el a függvény!)

Írj egy függvényt, amelyik paraméterként két ilyen bináris fa gyökerét kapja! Térjen vissza igazzal a függvény, ha a paraméterként kapott két bináris fa egyforma, hamissal akkor, ha nem egyformák.