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

Czirkos Zoltán · 2017.07.13.

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

(Bináris) fák. Az óra célja kettős: egyrészt a fák használatának bemutatása, másrészt a rekurzióval kapcsolatos kérdések újbóli áttekintése. A feladatok mindkét témakörrel foglalkoznak. Tekintsük át a feladatokat a rekurzió szemszögéből is: melyik függvény hogyan oldja meg a problémát fokozatos egyszerűsítésekkel (részfákra bontás) és triviális esetek (levelek, üres fa) feldolgozásával!

Felkészülés a gyakorlatra:

1. Fák tulajdonságai

Fa építése

A következő számokat a megadott sorrendben egy balról jobbra rendezett keresőfába szúrjuk, annak kiegyensúlyozása nélkül: 5, 8, 3, 6, 7, 2, 9, 1. Rajzoljuk le a keletkező fát!

Megoldás

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

Fa tulajdonságai

            o
           / \
          o   o
         /   / \
        o   o   o
       /     \
      o       o

Mennyi az itt látható bináris fa magassága és leveleinek száma?

Fa bejárása

            3
           / \
          4   9
         /   / \
        2   6   5
       /     \   \
      1       7   0

Rendelkezik-e a fenti fa keresőfa tulajdonsággal? Milyen sorrendben járja be egy a) inorder b) postorder c) preorder bejáró algoritmus a fa elemeit?

2. Típusok

Definiáljunk típust a lent megadott adatokat tartalmazó fákhoz! Ezeket az adatszerkezeteket a további feladatokban használni fogjuk.

  • Bináris fa, amely szavakat és azok előfordulásainak számát tárolja.
  • Bináris fa, amely tetszőlegesen hosszú neveket és hozzájuk tartozó telefonszámokat tárol. (Vigyázat, a telefonszámhoz nem elég egy egész szám, hiába van szám a nevében!)
  • Morse kódokat akarunk gyorsan feldolgozni. A kétféle bejövő jel TI és TÁ. Egy bináris fában ezt könnyen tárolhatjuk; a bejövő jeltől függően megyünk a fában balra (TI) vagy jobbra (TÁ); ha vége van a jelsorozatnak, akkor pedig az adott csomópontban tárolt betűt kiolvassuk.

Megoldás

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;

3. Fák bejárása – adott elemek kiírása

Egy telefonkönyvi adatokat tartalmazó, név szerint rendezett bináris fa ábrázolásához az előző feladatban megadott struktúrát használjuk. Készítsünk egy olyan szabványos ANSI C függvényt, amely paraméterként veszi át a fa gyökerének címét, és kiírja az összes „Nagy” vezetéknevű személyt telefonszámostul ABC sorrendben! A „Nagyító” vezetéknevű személy nem „Nagy” vezetéknevű személy!

Megoldás

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);
}

4. Fa magassága

Határozzuk meg meg, milyen magas egy bináris fa!

Megoldás

Érdemes abból a meghatározásból kiindulni, hogy a gyökértől legmesszebbi levél távolságát kell meghatározni:

  1. Üres fa magassága 0.
  2. Vegyük a bal és a jobb részfa magasságát.
  3. Válasszuk ki a nagyobbat.
  4. Adjunk hozzá egyet (ez a szint).
typedef struct BinFa {
    int adat;

    struct BinFa *bal, *jobb;
} BinFa;

int magassag(BinFa *gyoker) {
    int bal, jobb, max;

    if (gyoker == NULL) return 0;    /* 1 */

    bal  = magassag(gyoker->bal);    /* 2 */
    jobb = magassag(gyoker->jobb);
    /* melyik magasabb? */
    max  = bal > jobb ? bal : jobb;  /* 3 */

    return max + 1;                  /* 4 */
}

5. Egyformák-e? Egymás tükörképei-e?

Hasonlítsunk össze két fát: egyformák-e? Második feladat: hasonlítsunk össze két fát, hogy egymás tükörképei-e!

Megoldás

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.

6. Fa másolása; másolat tükrösen

Másoljunk le egy bináris fát! Figyeljünk arra, hogy a másolat fa az eredetitől független, ún. mély másolat legyen! Készítsünk róla olyan másolatot is, amely az eredetinek a tükörképe!

Megoldás

Fa másolása hibásan

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) {
    Fa *m;

    if (gy == NULL) return NULL;    /* ures fa masolata ures 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;
}

Tükrözve lemásolni ugyanígy kell. Csak olyankor a bal részfába kerül a jobb oldalinak a másolata, a jobb oldaliba pedig a bal másolata – persze az egyes másolatok is tükrözve kell legyenek, így ahhoz ugyanúgy csak egy függvény kell, amely a fentitől csak a részfák másolásánál különbözik:

m->bal = tukormasol(gy->jobb);      /* reszfak keresztbe */
m->jobb = tukormasol(gy->bal);

A fát másoló, tükrözve másoló és összehasonlító programok teljes forráskódja letölthető innen: famasol.c