Labor, 11-12. hét: bináris fák

Czirkos Zoltán, Pohl László · 2016.08.28.

Bináris fák és rekurzív algoritmusaik.

Felkészülés a laborra:

Megoldás

Az alábbi feladatok megoldása letölthető innen: binaris_fa.c.

1. Haladás

Ne feledd: a második nagy zh-ra jelentkezni kell! És a haladási naplót is hasznos töltögetned, hogy tudd, hol tartasz a készülésben. Mindkettő elérhető bejelentkezés után.

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

#include <stdio.h>
#include <stdlib.h>
 
typedef struct BiFa {
    int ertek;
    struct BiFa *bal, *jobb;
} BiFa;
 
BiFa *beszur(BiFa *gyoker, int ertek) {
    if (gyoker == NULL) {
        BiFa *uj = (BiFa*) malloc(sizeof(BiFa));
        uj->ertek = ertek;
        uj->bal = uj->jobb = NULL;
        return uj;
    }
    if (ertek < gyoker->ertek) {        /* balra szur */
        gyoker->bal = beszur(gyoker->bal, ertek);
    }
    else if (ertek > gyoker->ertek) {   /* jobbra szur */
        gyoker->jobb = beszur(gyoker->jobb, ertek);
    }
    else {
        /* mar benne van */
    }
    return gyoker;
}


int main(void) {
    int minta[] = {15, 96, 34, 12, 14, 56, 21, 11, 10, 9, 78, 43, 0};
    BiFa *gyoker = NULL;
    int i;
    for (i = 0; minta[i] > 0; i++)
        gyoker = beszur(gyoker, minta[i]);
 
    /* Ide tedd be a kipróbálandó függvények hívásait! */
 
    return 0;
}

3. Fa kiírása és törlése

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

Írd meg a fát törlő, rekurzív függvény törzsét, és hívd meg a main() függvény megfelelő helyén, hogy ne legyen memóriaszivárgás!

4. Elemek száma és összege

Írj 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 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 minta[] tömbben tárolt számok alapján)!

5. Elem megkeresése

Írj függvényt, amely megkeres egy elemet a fában, és visszaadja az arra mutató pointert! A visszatérési érték legyen NULL, ha az adott szám a fában nem szerepel.

Tipp

Tipp a megoldáshoz:

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

6. Negálás

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

Keresés a negált fában

Keress most meg egy elemet az előbbi függvénnyel. 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.)

7. Tükrözés

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

Tipp

Tipp a megoldáshoz:

  • Ü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.
  • … melyik 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!)

8. További feladatok

Ha elkészültél, folytasd a feladatgyűjtemény kapcsolódó feladataival!