Gyakorlat, 13. hét: bináris fák

Definiálj típust, amely segítségével valós számokból álló bináris fa építhető!

Írj függvényt, amelyik megmondja, hogy milyen magas a paraméterként kapott fa!

Mutass példát a függvény használatára! Hozz létre egy változót, amelyik a fa gyökerét mutatja (fát építeni nem kell most), alkalmazd rajta a függvényt, és írd ki az eredményt!

typedef struct BinFa {
    double adat;
    struct BinFa *bal, *jobb;
} BinFa;

int magassag(BinFa *gyoker) {
    if (gyoker == NULL)
        return 0;
    int bal = magassag(gyoker->bal);
    int jobb = magassag(gyoker->jobb);
    int max = bal > jobb ? bal : jobb;
    return max + 1;
}

BinFa *gy = ...;
printf("A fa magassága %d", magassag(gy));

Mindegyik tétel 1 pontos:

1. Típusdefiníció: struktúra, benne double/float adat, és bal/jobb részfa
2. bal/jobb részfánál helyes a pointer típusa (struct BinFa), és mindkettő pointer (*bal, jobb – nem jó!)
3. Magasság függvény: helyes fejléc, int érték és BinFa* paraméter
4. báziskritérium: üres fára nullát ad; nem dereferálja a null pointert
5. rekurzív hívás a két részfára
6. a rekurzív hívások eredményeinek felhasználása, maximum meghatározása
7. a részfák magassága 1x meghatározva, változóban eltárolva; m(bal) > m(jobb) ? m(bal) : m(jobb) feleslegesen hívná kétszer
8. maximum + 1 a visszatérési érték, mert a gyökér is számít
9. Példa: itt is pointer a változó, a függvény hívása helyes

Egyebek: Minden nem említett hibáért -1p (pl. adattag -> helyett . operátorral)

            5
           / \
          3   8
         /   / \
        2   6   9
       /     \
      1       7

typedef struct Szo {
    char szo[30+1];
    int elofordulas;

    struct Szo *bal, *jobb;    /* bal es jobb oldali leszarmazottak */
} Szo;

typedef struct Nev {
    char *nev;                 /* tetszőlegesen hosszú név - din. tömb */
    char szam[21];             /* max. 20 karakteres telefonszám */
    struct Nev *bal, *jobb;
} Nev;

typedef struct Morze {
    char betu;

    struct Morze *ti, *ta;     /* a kovetkezo jel ti vagy ta lehet */
} Morze;

Itt használhatjuk az strncmp()-t, amely a két sztringet csak valahányadik karakterig hasonlítja össze. A „Nagy” vezetéknevűek név sztringje úgy kezdődik, hogy „Nagy ”, vagyis tuti egy szóköz van a végén (ez pl. a „Nagyító” névnél nem igaz).

A rendezettség lehetővé tenné, hogy szisztematikusan találjuk meg ezeket; itt ezzel nem foglalkozunk, hanem az egész fát bejárjuk.

void nagy_kiir(Nev *gy) {
    if (gy == NULL) return;

    nagy_kiir(gy->bal);
    /* 5 = strlen("Nagy ") */
    if (strncmp("Nagy ", gy->nev, 5) == 0)
        printf("%s %s\n", gy->nev, gy->szam);
    nagy_kiir(gy->jobb);
}

Az összehasonlítás a következő módon képzelhető el. A függvény ebben az esetben két fát kap. Ha mind a két fa üres (NULL), akkor igazat kell válaszoljon; két üres fa ugyanis egyforma. Ha az egyik fa üres, a másik meg nem, akkor nem egyformák (legyen bármi is a másikban, ha az első teljesen üres). Ezekkel a NULL pointeres eseteket lerendeztük. Ha egyik fa sem üres, akkor össze kell hasonlítani őket: akkor egyformák, ha a gyökérelemeik egyformák, és a bal részfáik egyformák, és a jobb részfáik egyformák.

Buktató: hogy két fa inorder bejárással ugyanazt a listát adja, nem biztosan jelenti azt, hogy a két fa egyforma! Egy „5” gyökerű fa, aminek a balra leszármazottja „7”, és annak a balra leszármazottja „9”, a 9-7-5 számsort adja inorder bejárva; a „7” gyökerű fa, amelyiknek a bal leszármazottja „9”, a jobb pedig „5”, úgyszint. Pedig az egyik ilyen / alakú, a másik meg ilyen /\.

bool egyforma_e(Fa *egyik, Fa *masik) {
   if (egyik == NULL && masik == NULL)  /* ket ures fa egyforma */
      return true;
   if (egyik != NULL && masik == NULL)  /* ures vs. nem ures -> nem egyforma */
      return false;
   if (egyik == NULL && masik != NULL)  /* detto */
      return false;

   return egyik->szam == masik->szam              /* egyforma szam a gyokerben */
       && egyforma_e(egyik->bal, masik->bal)      /* es egyformak a bal reszfak */
       && egyforma_e(egyik->jobb, masik->jobb);   /* es a jobb reszfak */
}

Hogy a két fa egymásnak tükörképe-e, azt ugyanígy lehet ellenőrizni, csak legalul a feltételnél a bal részfát a jobbal kell hasonlítani, és fordítva.

A bináris fa lemásolása nem csak abból áll, hogy egy új pointert ráállítunk a régi fa gyökerére, és azon keresztül ugyanazt látjuk. A másolat egy, az eredetitől teljesen független fa kell legyen, függetlenül módosítható, akár törölhető. Emiatt nem elég az, hogy Fa *masolat = eredeti, és az sem, hogy a gyökér csomópontot lemásoljuk, a pointereivel együtt. Így keletkezne az ábrán látható állapot, amely hibás!

Fa *masolat = (Fa *) malloc(sizeof(Fa));
masolat->adat = eredeti->adat;   ← idáig még akár jó is lehetne
masolat->bal = eredeti->bal;     ← EZ HIBÁS!
masolat->jobb = eredeti->jobb;   ← EZ IS HIBÁS!

A fa másolása rekurzív: egy másolat csomóponthoz tartozó bal és jobb oldali részfa az eredeti csomópont bal és jobb oldali részfáinak másolata.

Fa *masol(Fa *gy) {
    if (gy == NULL) return NULL;        /* ures fa masolata ures fa */

    Fa *m = (Fa *) malloc(sizeof(Fa));  /* uj csomopont es adat */
    m->adat = gy->adat;
    m->bal = masol(gy->bal);            /* reszfak */
    m->jobb = masol(gy->jobb);

    return m;
}

A fát másoló és összehasonlító programok teljes forráskódja letölthető innen: famasol.c. Ez tükrözött másolatot is készít.