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

Czirkos Zoltán · 2018.08.22.

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. Ötödik kis ZH

Ezen az órán van az ötödik kis ZH.

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

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

Fa bejárása

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

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?

3. Típusok

Definiáljunk típust a lent megadott adatokat tartalmazó fákhoz!

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

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

5. 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. Ahhoz kell végül egyet adni, ami a gyökérhez tartozó szint:

  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) {
    if (gyoker == NULL) return 0;    /* 1 */

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

    return max + 1;                  /* 4 */
}

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

7. Fa másolása

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!

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) {
    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.

8. További feladatok

  • Oldjuk meg a fenti névkeresős feladatot úgy, hogy kihasználjuk a fa rendezettségét!
  • Adott egy bináris fa. Ellenőrizzük, hogy rendelkezik-e keresőfa tulajdonsággal!
  • Oldjuk meg az előző feladatot O(n) lépésszámmal! (Megoldás a feladatgyűjteményben.)