Mikulás
A Mikulás a szánjával nekihajtott a gyökérpointeré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érpointerné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 C-ben az adatszerkezetet! Í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
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 az 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!
Pontosan kettő vagy nulla leszármazott
Egy bináris fa max. 50 betűs szavakat tárol. Definiáld C-ben az adatszerkezetet! Í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!
Két régebbi kis ZH
A. Egy bináris fa szavakat tárol, max. 30 betűseket. Definiáld C-ben az adatszerkezetet! Í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.
B. Egy bináris fa szavakat tárol, amelyek dinamikusan foglalt sztringben vannak. Definiáld a fát! Írj függvényt, amelyik egy ilyen fát teljesen felszabadít (minden hozzá tartozó dinamikus memóriaterületettel együtt!) Í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.
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ó pointert kap! Visszatérési értéke
legyen egy má - sik bináris fa gyökerére mutató pointer, 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ére mutató pointert kap! 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.
Írj egy függvényt, amelyik felszabadít egy paraméterként kapott bináris fát!
Van egy fánk, és…
1) Feltételezve, hogy az egyik már tartalmaz adatot, másold le azt!
2) Hasonlítsd őket össze; írd ki a képernyőre, hogy „egyformák”, ha azok. Szabadítsd fel utána a fákat.
Kulcs szerint rendezett fa
Adott a következő program, amelyben egy kétdimenziós tömb elemeinek első fele egy kulcs, második fele egy érték. Például a legelső elemnél a 13 a kulcs, a 105 pedig az érték.
char minta[][2]={{13, 105}, {22, 116}, {14, 111}, {45, 101}, {3, 99},
{35, 32}, {23, 32}, {65, 32}, {18, 10}, {53, 97}, {17, 62},
{27, 110}, {55, 33}, {15, 46}, {4, 108}, {59, 41}, {72, 32},
{41, 102}, {6, 100}, {39, 110}, {60, 59}, {68, 116}, {31, 10},
{74, 59}, {30, 123}, {63, 32}, {1, 105}, {16, 104}, {47, 108},
{66, 114}, {28, 40}, {20, 105}, {26, 105}, {62, 32}, {29, 41},
{46, 108}, {71, 110}, {25, 97}, {7, 101}, {64, 32}, {0, 35},
{77, 10}, {50, 118}, {76, 125}, {56, 92}, {5, 117}, {34, 32},
{48, 111}, {38, 105}, {8, 32}, {54, 103}, {19, 10}, {33, 32},
{73, 48}, {32, 32}, {61, 10}, {51, 105}, {12, 100}, {36, 112},
{67, 101}, {37, 114}, {44, 72}, {70, 114}, {58, 34}, {9, 60},
{2, 110}, {52, 108}, {11, 116}, {10, 115}, {75, 10}, {24, 109},
{40, 116}, {21, 110}, {49, 32}, {42, 40}, {43, 34}, {57, 110},
{69, 117}, {78, 0}};Írj egy programot, amely felépít egy bináris fát, amely ezeket a kulcs-érték párokat tartalmazza, és a kulcs szerint rendezve van! Az értékeket karakternek tekintve, járd be a keletkező fát a kulcs szerint növekvő sorrendben, és írd ki a karaktereket! Milyen üzenetet rejt a fa?
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 pointerrel.
- Amúgy lehet, hogy a bal oldali részfában lesz. Ha ott megtaláljuk, akkor egy onnan származó pointerrel kell visszatérni.
- Ugyanez lehet a jobb oldali részfánál is.
- Ha egyikben sem – akkor
NULLpointer.
Lista építése
Írj függvényt, amely egyszeresen láncolt listát épít a fenti, karaktereket tároló fa azon elemeire mutató pointerekből, amelyek:
- az
'l'betűt tartalmazzák, - whitespace (szóköz, újsor vagy tabulátor) karaktert tartalmaznak (ehhez használható az
isspace()függvény), - egy tetszőleges, paraméterként adott karaktert tartalmaznak.
Hol lehet ehhez többszörös indirekciót alkalmazni? Miért?
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 10Ilyenkor 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 pointere, vagy esetleg a fa gyökere pointer módosul. Ezért a programban a faelemekben szülőre mutató pointert lehet érdemes használni, vagy a program kétszeres indirekcióval egyszerűsíthető. Gondold végig, hogy a nulla vagy egy gyerekű elem törlése hogyan működik pointerek szintjén! Ezt a problémát megoldhatod úgy is, 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!
Fák bejárása – háromágú fa
Definiáljunk adatszerkezetet egész számok háromágú fában való tárolásához! Írjunk függvényt, amely paraméterként veszi át egy ilyen elemekből álló fa gyökerének címét, valamint egy egész számot, és megszámolja, hogy hány olyan elem van a fában, amely kisebb a paraméterként kapott számnál (ez a függvény visszatérési értéke)!