11. hét: bináris fák, többszörös indirekció

typedef struct Lista {
    int szam;
    struct Lista *kov;
} Lista;

void elso_vegere(Lista **peleje) {
    if (*peleje == NULL) return;
    if ((*peleje)->kov == NULL) return;

    Lista *elso = *peleje;
    Lista *iter;
    for (iter = elso; iter->kov != NULL; iter = iter->kov)
        ;

    iter->kov = elso;
    *peleje = elso->kov;
    elso->kov = NULL;
}

Lista *eleje;
eleje = (Lista*) malloc(sizeof(Lista));
eleje->szam = 3;
eleje->kov = (Lista*) malloc(sizeof(Lista));
eleje->kov->szam = 4;
eleje->kov->kov = NULL;

elso_vegere(&eleje);

typedef struct Lista {
   double szam;
   struct Lista *kov;
} Lista;

void utolso_elore(Lista **peleje) {
   if (*peleje==NULL) return;
   if ((*peleje)->kov==NULL) return;

   Lista *iter;
   for (iter = *peleje; iter->kov->kov != NULL; iter = iter->kov)
      ;
   Lista *utolso = iter->kov;

   utolso->kov = *peleje;
   *peleje = utolso;
   iter->kov = NULL;
}

eleje = (Lista*) malloc(sizeof(Lista));
eleje->szam = 3;
eleje->kov = (Lista*) malloc(sizeof(Lista));
eleje->kov->szam = 4;
eleje->kov->kov = NULL;

utolso_elore(&eleje);

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct Fa {
    int adat;
    struct Fa *b, *j;
} Fa;

bool lista_e(Fa *gy) {
    /* ha ures, akkor igen. ures fa, ures lista. */
    if (gy == NULL)
        return true;

    /* ha 2 gyerek van, az elagazas, szoval nem. */
    if (gy->b != NULL && gy->j != NULL)
        return false;

    /* ha balra a folytatas, akkor lehet, hogy jok
     * vagyunk. pontosabban ha a tobbi resz jo, akkor jo. */
    if (gy->b)
        return lista_e(gy->b);
    /* mert amugy jobbra ugyanez */
    return lista_e(gy->j);

}

Fa *uj_csomopont(int i) {
    Fa *uj = (Fa *) malloc(sizeof(Fa));
    uj->adat = i;
    uj->b = uj->j = NULL;

    return uj;
}

void fa_free(Fa *gy) {
    if (gy == NULL)
        return;
    fa_free(gy->b);
    fa_free(gy->j);
    free(gy);
}

int main(void) {
    Fa *gy = NULL;

    /* itt meg true */
    gy = uj_csomopont(1); /* itt is true */
    gy->b = uj_csomopont(2); /* itt is true */
    gy->j = uj_csomopont(3); /* itt false lesz */

    fa_free(gy->j);
    gy->j = NULL;           /* ujra true */
    gy->b->b = uj_csomopont(4); /* megint true */
    gy->b->b->j = uj_csomopont(5);  /* meg mindig */
    gy->b->b->b = uj_csomopont(6);  /* es most nem */

    printf("%d\n", lista_e(gy));

    fa_free(gy);

    return 0;
}

Nem elég azt vizsgálni, hogy a teljes fa gyökeréhez képest csak balra kisebbek, jobbra nagyobbak vannak-e. Az alábbi fában ez teljesül (a 2 és a 3 kisebbek a gyökérben lévő 5-nél, illetve a 6, 9 és 8 nagyobbak nála), mégsem keresőfa; a jelölt elemek elrontják azt.

    5
   / \
  3   9
 /   / \
2   6   8

Azt sem elég vizsgálni, hogy minden csomópont gyerekei balra kisebbek, jobbra nagyobbak-e. Az alábbi fában ez minden közvetlen kapcsolatban lévő elemre teljesül, mégsem keresőfáról van szó: a 6-os elem rossz helyen van, bár a 3-nál nagyobb, de az egész fát tekintve a gyökérben lévő 5-től jobbra keresnénk.

    5
   / \
  3   8
 / \   \
2   6   9

A két tulajdonságnak együtt kell teljesülnie.

typedef struct BinFa {
    int szam;
    struct BinFa *bal, *jobb;
} BinFa;

/* maximumot keres a fában. a teljes fát vizsgálja, nem feltételez keresőfa
 * tulajdonságot. nem hívható üres fára. */
int max_fa(BinFa *gy) {
    int max = gy->szam;
    if (gy->bal != NULL) {
        int bal_max = max_fa(gy->bal);
        max = bal_max > max ? bal_max : max;
    }
    if (gy->jobb != NULL) {
        int jobb_max = max_fa(gy->jobb);
        max = jobb_max > max ? jobb_max : max;
    }
    return max;
}

int min_fa(BinFa *gy) {
    return /* ... mint fent ... */;
}

bool keresofa_e(BinFa *gy) {
    if (gy == NULL)     /* üres fa = keresőfa, mert nem hibás */
        return true;
    
    /* ha balra bárhol túl nagy elem van, vagy jobbra bárhol túl kicsi */
    if (max_fa(gy->bal) > gy->szam)
        return false;
    if (min_fa(gy->jobb) < gy->szam)
        return false;
    
    /* ha balra vagy jobbra nem keresőfa van */
    if (!keresofa_e(gy->bal) || !keresofa_e(gy->jobb))
        return false;
    
    /* egyébként az */
    return true;
}

Ez nem hatékony; minden részfát annyiszor bejár (sőt duplán annyiszor), amilyen magas részfában van.

Hatékonyabb megoldáshoz érdemes egy bejárásból kiindulni. Tudjuk, hogy a keresőfát inorder bejárva növekvő számsort kapunk. Tehát nem kell mást tenni, mint elvégezni a bejárást, és ha bárhol olyan számot találunk, amelyik egyenlő az előbb látottal vagy kisebb annál, akkor a fát hibásnak jelölhetjük. Az alábbi algoritmus egyszerűsített: nem áll meg a hibánál, és feltételezi, hogy a fában pozitív számok vannak; a lényeg így is látszik.

typedef struct BinFa {
    int szam;
    struct BinFa *bal, *jobb;
} BinFa;

void keresofa_hibat_keres(BinFa *gy, int *pmax, bool *prendben) {
    if (gy == NULL)
        return;
    
    keresofa_hibat_keres(gy->bal, pmax, prendben);
    if (gy->szam <= *pmax)  /* ha nem szabadna ilyennek jönnie... */
        *prendben = false;
    *pmax = gy->szam;
    keresofa_hibat_keres(gy->jobb, pmax, prendben);
}

bool keresofa_e(BinFa *gy) {
    int max = 0;
    bool rendben = true;
    
    keresofa_hibat_keres(gy, &max, &rendben);
    
    return rendben;
}

Másik megoldási lehetőség: figyelembe vehetjük azt is, hogy a hierarchia milyen intervallumba szorítja be a részfák csomópontjaiban található értékeket. Ehhez vegyük példának az alábbi fát:

    5
   / \
  3   9
     / \
    x   10

Ebben a fában az x-szel jelölt helyen (akár egy csomópont van ott, akár egy nagyobb részfa) csak 5-nél nagyobb, és 9-nél kisebb szám lehet. 5-nél nagyobb azért, mert a gyökérben lévő 5-től jobbra van (ha kisebb lenne, akkor az 5-től balra kellene legyen). 9-nél kisebb pedig azért, mert egy attól balra lévő részfáról van szó.

A megoldás így:

bool keresofa_e_belso(BinFa *gy, int *min, int *max) {
    if (gy == NULL)
        return true;
    
    if ((min != NULL && gy->szam <= *min)
        || (max != NULL && gy->szam >= *max))
        return false;
    
    return keresofa_e_belso(gy->bal, min, &gy->szam)
        && keresofa_e_belso(gy->jobb, &gy->szam, max);
}

bool keresofa_e(BinFa *gy) {
    return keresofa_e_belso(gy, NULL, NULL);
}

A függvény a fa gyökere mellett átvesz egy minimumot és egy maximumot is – ezek között kellene legyen az adott részfa összes eleme. Ha ez nem teljesül az adott csomópontnál, hamissal tér vissza, amúgy pedig vizsgálja a részfákat. Amikor balra halad, akkor a gyökér határozza meg a maximumot (annál nagyobb elem a gyökértől balra nem lehet), amikor jobbra, akkor pedig a gyökér a minimumot adja (annál jobbra kisebb elem nem lehet). A keresést úgy kell elindítani, hogy mindkét pointer NULL értékű; a gyökér esetében még nincs sem alsó, sem felső határ.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

typedef struct Fa {
    char adat[51];
    struct Fa *b, *j;
} Fa;

bool ketto_vagy_nulla_e(Fa *gy) {
    /* ha ures, akkor igen. ha nincs kerdes, akkor igazat valaszolunk. */
    if (gy==NULL)
        return true;

    /* ha 2 gyerek van, az elagazas.
     * akkor ez rendben van - ha a reszfak is rendben vannak */
    if (gy->b!=NULL && gy->j!=NULL)
        return ketto_vagy_nulla_e(gy->b) && ketto_vagy_nulla_e(gy->j);

    /* ha nincs gyerek, akkor mi rendben
     * vagyunk, mert a vegen vagyunk.
     * ez amugy egyesitheto lenne a fentivel, mert
     * ha mindketto null, akkor kvne(null)&&kvne(null) = true,
     * vagyis a fenti kifejezes is helyes eredmenyt ad */
    if (gy->b==NULL && gy->j==NULL)
        return true;

    /* most csak az lehet, hogy egy fele van felolunk
     * tovabb menes, ami viszont nem jo. */
    return false;
}

Fa *uj_csomopont(char *szo) {
    Fa *uj=(Fa *) malloc(sizeof(Fa));
    strcpy(uj->adat, szo);
    uj->b=uj->j=NULL;

    return uj;
}

void fa_free(Fa *gy) {
    if (gy==NULL)
        return;
    fa_free(gy->b);
    fa_free(gy->j);
    free(gy);
}

int main(void) {
    Fa *gy = NULL;

    /* itt true */
    gy=uj_csomopont("1"); /* itt is true */

    gy->b=uj_csomopont("2");  /* itt false, most igy nez ki / */

    gy->j=uj_csomopont("3");  /* megint true, most igy nez ki /\ */

    gy->b->b=uj_csomopont("4");   /* megint false /\
                                                 /   */

    gy->b->j=uj_csomopont("5");   /* ujra true /\
                                              /\  */


    gy->b->b=uj_csomopont("6");
    gy->b->j=uj_csomopont("7");   /* es vegul true  /\
                                                   /\/\ */

    printf("%d\n", ketto_vagy_nulla_e(gy));

    fa_free(gy);

    return 0;
}

Onnantól van nem teljesen kitöltve, ahol van benne egy NULL pointer. Tehát a gyökérhez legközelebbi NULL pointert kell keresni. Ha a gyökér maga is NULL, akkor ez a távolság nulla. Ha nem, akkor 1 + a két részfából a kisebbik érték.

Úgy is lehet gondolkozni, hogy egy fa adott szintjein lévő elemek száma egy teljesen kitöltött fában a kettő hatványait adják ki: 1, 2, 4, 8 stb. Ameddig ez igaz a szintekre, addig teljesen ki van töltve. Már csak kell egy ciklus, amelyik az egyre mélyebb szinteket ellenőrzi a külön segédfüggvény hívásával. Ez sokkal lassabb megoldás, de helyes.

A megoldás közösen tartalmazza a két feladat által kért függvényeket. Az első feladat maximum 30 betűs sztringjei helyett is a második feladat dinamikusan foglalt sztringjei szerepelnek.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Fa {
    char *sztring;
    struct Fa *bal, *jobb;
} Fa;

int dinnye_papaja_kozott(Fa *gy) {
    int db;

    if (gy == NULL)     /* ha nincs fa, 0 ilyen szo van */
        return 0;

    db = 0;
    if (strcmp(gy->sztring, "dinnye") >= 0 && strcmp(gy->sztring, "papaja") <= 0)
        db = 1;

    /* ez + a reszfakban levok */
    return db + dinnye_papaja_kozott(gy->bal) + dinnye_papaja_kozott(gy->jobb);
}

void free_fa(Fa *gy) {
    if (gy == NULL)     /* ha nincs is csomopont */
        return;

    /* elobb a reszfak */
    free_fa(gy->bal);
    free_fa(gy->jobb);

    /* utana maga a csomopont */
    if (gy->sztring)    /* ha van sztring, free */
        free(gy->sztring);
    free(gy);
}

Fa *uj_csomopont(char *str) {
    Fa *uj = (Fa *) malloc(sizeof(Fa));
    uj->sztring = malloc(strlen(str) + 1);
    strcpy(uj->sztring, str);
    uj->bal = uj->jobb = NULL;

    return uj;
}

int main(void) {
    Fa *gy;

    gy = uj_csomopont("kigyo");
    gy->bal = uj_csomopont("cseresznye");
    gy->jobb = uj_csomopont("free");
    gy->bal->bal = uj_csomopont("gyumolcsos");

    printf("dinnye-papaja kozott: %d\n", dinnye_papaja_kozott(gy));

    free_fa(gy);

    return 0;
}

Ez a vizsga négy különböző csoportjainak feladataiból összegyúrt nagy feladat. Az A csoportban olyan programrészt kellett írni, amelyik egy bináris fát lemásol; a B csoportban pedig úgyszint fát kellett másolni, de úgy, hogy a másolat az eredetinek a tükörképe legyen. Hogy lehet lemásolni egy fát? Egy fa másolata az a gyökér csomópontjának a másolata (1. malloc, 2. adat másolása), és a két részfájának másolata (itt a rekurzió.) Az új csomópont bal oldali részfája az eredeti fa bal oldali részfájának másolata; és a jobb oldalira ugyanez. Természetesen üres fa másolata üres fa.

Fa *masol(Fa *gy) {
    Fa *m;

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

    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:

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

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.

bool egyforma_e(Fa *egyik, Fa *masik) {
    if (egyik==NULL && masik==NULL)     /* ket ures fa egyforma */
        return true;
    if (egyik!=NULL && masik==NULL)     /* ures fa es nem ures fa -> nem egyf */
        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 lent a feltételnél a bal részfát a jobbal kell hasonlítani, és fordítva. A teljes kódot, néhány aprósággal kiegészítve, hogy működjön, lásd lent.

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 /\.

A teljes, kipróbálható program:

#include <stdlib.h>
#include <stdio.h>

typedef struct Fa {
    int szam;                   /* double, float, char, ... */
    struct Fa *bal, *jobb;
} Fa;

/* ezt mindegyik keri */
void torol(Fa *gy) {
    if (gy==NULL)
        return;
    torol(gy->bal);
    torol(gy->jobb);
    free(gy);
}

/* ezt semelyik nem keri, csak nekem kellett */
Fa *uj(int szam) {
    Fa *uj=malloc(sizeof(Fa));
    uj->szam=szam;
    uj->bal=uj->jobb=NULL;
    return uj;
}

/* ezt sem kerte egyik feladat sem */
void kiir(Fa *gy) {
    if (gy==NULL)
        return;
    kiir(gy->bal);
    printf("%d\n", gy->szam);
    kiir(gy->jobb);
}

/* A */
Fa *masol(Fa *gy) {
    Fa *uj;
    if (gy==NULL)
        return NULL;
    uj=malloc(sizeof(Fa));
    uj->szam=gy->szam;
    uj->bal=masol(gy->bal);
    uj->jobb=masol(gy->jobb);
    return uj;
}

/* B */
Fa *tukormasol(Fa *gy) {
    Fa *uj;
    if (gy==NULL)
        return NULL;
    uj=malloc(sizeof(Fa));
    uj->szam=gy->szam;
    uj->jobb=tukormasol(gy->bal);    /* itt a kutya elasva */
    uj->bal=tukormasol(gy->jobb);    /* bal <- jobb, jobb <- bal */
    return uj;
}

/* C */
bool egyforma_e(Fa *egyik, Fa *masik) {
    if (egyik==NULL && masik==NULL)   /* ket ures fa egyforma */
        return true;
    if (egyik!=NULL && masik==NULL)   /* ures fa es nem ures fa -> nem egyf */
        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 */
}

/* D */
bool tukros_e(Fa *egyik, Fa *masik) {
    if (egyik==NULL && masik==NULL)   /* ket ures fa egyforma */
        return true;
    if (egyik!=NULL && masik==NULL)   /* ures fa es nem ures fa -> nem egyf */
        return false;
    if (egyik==NULL && masik!=NULL)   /* detto */
        return false;

    return egyik->szam==masik->szam                  /* egyforma szam a gyokerben */
           && tukros_e(egyik->bal, masik->jobb)      /* es bal reszfa ~ jobb reszfa */
           && tukros_e(egyik->jobb, masik->bal);     /* illetve jobb reszfa ~ bal reszfa */
}

int main(void) {
    Fa *eredeti;
    Fa *masolat;
    Fa *tukormasolat;

    /* hogy legyen min kiprobalni, nem feladat */
    eredeti=uj(5);
    eredeti->bal=uj(7);
    eredeti->jobb=uj(9);

    /* A */
    masolat=masol(eredeti);
    /* B */
    tukormasolat=tukormasol(eredeti);

    kiir(eredeti);
    kiir(masolat);
    kiir(tukormasolat);

    /* C */
    printf("egyforma eredeti,masolat: %s\n", egyforma_e(eredeti, masolat)?"egyforma":"nem az");
    printf("egyforma eredeti,tukormasolat: %s\n", egyforma_e(eredeti, tukormasolat)?"egyforma":"nem az");

    /* D */
    printf("tukros eredeti,masolat: %s\n", tukros_e(eredeti, masolat)?"tukros":"nem az");
    printf("tukros eredeti,tukormasolat: %s\n", tukros_e(eredeti, tukormasolat)?"tukros":"nem az");

    /* mind keri */
    torol(eredeti);
    torol(masolat);
    torol(tukormasolat);

    return 0;
}

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

Egy adott elemet megelőző és az azt követő elem könnyen megtalálható iteratív algoritmussal is. Az őt megelőző elem a nála kisebbek közül a legnagyobb, tehát a bal oldali részfájának jobb szélső eleme. Az őt követő elem pedig szimmetrikusan a jobb oldali részfájának bal szélső eleme.

Az így megtalált elemek mindenképp legfeljebb egy gyerekkel rendelkeznek csak: a bal szélső elem azért, mert nincs bal oldali szomszédja (különben nem ő lenne a bal szélső), a jobb szélső pedig ugyanígy, csak a másik irányba.

Egy fában annyit találunk a megadott keresett elemből, ahány olyan van a bal oldali, plusz a középső, plusz a jobb oldali részfájában; plusz a csomópont saját tartalma alapján 0 vagy 1. Ezt a C kódban is egy sorba írva látható; a legutolsó sorban a kérdőjel-kettőspontos kifejezés kiértékelve 1-et vagy 0-t ad eredményül, ha az adott elem kisebb n-nél, illetve nem.

A háromágú fa feldolgozása semmiben nem tér el a bináris fáétól – ezt is rekurzívan kell csinálni.

typedef struct TriFa {
    int a;
    struct TriFa *bal, *kozep, *jobb;
} TriFa;

int kisebb(TriFa *p, int n) {
    if (p == NULL)
        return 0;
    return kisebb(p->jobb, n)
           + kisebb(p->kozep, n)
           + kisebb(p->bal, n)
           + (p->a<n?1:0);
}