13. labor: Fák bejárása

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 fa {
    int ertek;
    struct fa *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;
}
 
 
void torol(BiFa *gyoker) {
   printf("Nem irtad meg a torlo fuggvenyt!\n");
}
 
int main() {
    int i;
    BiFa *gyoker=NULL;
    int minta[]={15, 96, 34, 12, 14, 56, 21, 11, 10, 9, 78, 43, 0};
 
    for (i=0; minta[i]>0; i++)
        gyoker=beszur(gyoker, minta[i]);
 
    /* Ide szúrd be a kipróbálandó függvények hívásait! */
 
    torol(gyoker); /* A dinamikus adatszerkezetet fel kell szabadítani! */
    return 0;
}

Írd meg a fát törlő rekurzív függvény törzsét!

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

Í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)!

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

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

Írj egy rekurzív függvényt, amely tükröz egy paraméterként kapott fát! (Vigyázat: ez nem ugyanaz a feladat, mint ami a gyakorlaton szerepelt! Ott egy új fát kellett készíteni, amely tükörképe volt a paraméterként kapottnak, itt pedig egy meglévő fát kell módosítani.)

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 jobboldali 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!)

A Mikulás a szánjával nekihajtott a fent látható, a gyökérpointerével adott fának. A csomagok a puttonyából kihullottak és szétszóródtak a fa ágain. Ezért a Mikulás felmászik a fára, végigjárja az összes ágát, és az ott található ajándékokat összegyűjti. Mindet a fa gyökeréhez cipeli. Az egyes ágakon található ajándékok számai a fa elemeiben tárolt egész érték által adottak. Feladat: megírni azt a függvényt, amely a gyökérpointernél összegzi a fában tárolt elemeket, míg az összes többi, fában tárolt egészet kinullázza. (Régebbi vizsgafeladat.)

Adott a következő program, amely egy rendezett bináris fát épít. Minden elem tartalmaz egy kulcsot (ez a rendezés alapja), és egy értéket (ez egy karakter). Milyen üzenetet rejt az értékekben a fa?

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

char minta[][2]={{13, 105}, {22, 116}, {14, 111}, {45, 101}, {3, 99}, 
   {35, 32}, {23, 32}, {65, 32}, {18, 10}, {53, 97}, {17, 62}, 
   {27, 110}, {55, 33}, {15, 46}, {4, 108}, {59, 41}, {72, 32}, 
   {41, 102}, {6, 100}, {39, 110}, {60, 59}, {68, 116}, {31, 10}, 
   {74, 59}, {30, 123}, {63, 32}, {1, 105}, {16, 104}, {47, 108}, 
   {66, 114}, {28, 40}, {20, 105}, {26, 105}, {62, 32}, {29, 41}, 
   {46, 108}, {71, 110}, {25, 97}, {7, 101}, {64, 32}, {0, 35}, 
   {77, 10}, {50, 118}, {76, 125}, {56, 92}, {5, 117}, {34, 32}, 
   {48, 111}, {38, 105}, {8, 32}, {54, 103}, {19, 10}, {33, 32}, 
   {73, 48}, {32, 32}, {61, 10}, {51, 105}, {12, 100}, {36, 112}, 
   {67, 101}, {37, 114}, {44, 72}, {70, 114}, {58, 34}, {9, 60}, 
   {2, 110}, {52, 108}, {11, 116}, {10, 115}, {75, 10}, {24, 109}, 
   {40, 116}, {21, 110}, {49, 32}, {42, 40}, {43, 34}, {57, 110}, 
   {69, 117}, {78, 0}};

typedef struct fa {
    int kulcs;
    char ertek;
    struct fa *bal,*jobb;
} BiFa;

BiFa *beszur(BiFa *gyoker, BiFa *uj) {
    if (gyoker == NULL) return uj;
    if (gyoker->kulcs < uj->kulcs){ /* balra szur */
        if (gyoker->bal == NULL) gyoker->bal = uj;
        else beszur(gyoker->bal, uj);
    }
    else{ /* jobbra szur */
        if (gyoker->jobb == NULL) gyoker->jobb = uj;
        else beszur(gyoker->jobb, uj);
    }
    return gyoker;
}

void torol(BiFa *gyoker) {
    /* Írd meg a felszabadító függvényt! */
}

int main() {
    int i;
    BiFa *gyoker=NULL;

    for (i=0; i<sizeof(minta)/(2*sizeof(char)); i++) {
        BiFa *uj=(BiFa*)malloc(sizeof(BiFa));
        if (uj==NULL){
            fprintf(stderr,"Sikertelen memoriafoglalas\n");
            return 1;
        }
        uj->kulcs=minta[i][0];
        uj->ertek=minta[i][1];
        uj->bal = uj->jobb = NULL;
        gyoker=beszur(gyoker,uj);
    }

    torol(gyoker); /* A dinamikus adatszerkezetet fel kell szabadítani! */

    return 0;
}

Keresés rendezetlen fában

Írj rekurzív függvényt, amely nem feltételez semmilyen rendezettséget a fa elemei részéről, és úgy keres meg egy karaktert a fenti fában!

Tipp:

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

Lista építése

Írj függvényt, amely egyszeresen láncolt listát épít a fenti, karaktereket tároló fa azon elemeire mutató pointerekből, amelyek:

• az 'l' betűt tartalmazzák,
• whitespace (szóköz, újsor vagy tabulátor) karaktert tartalmaznak (ehhez használható az isspace() függvény),
• egy tetszőleges, paraméterként adott karaktert tartalmaznak.

Hol lehet ehhez többszörös indirekciót alkalmazni? Miért?