Bináris fák a C nyelven: teljes útmutató kezdőknek

Informatec Digital » Algoritmusok » Bináris fák a C nyelven: teljes útmutató kezdőknek

Üdvözöljük ebben a C nyelvű bináris fákról szóló átfogó útmutatóban. Ebben a cikkben a bináris fák alapjait és azok C programozási nyelven való implementálását vizsgáljuk meg.

A bináris fák alapvető adatszerkezetek a számítástechnikában, és széles körben használják őket. Működésük és megvalósításuk megértése segít a komplex problémák hatékonyabb és elegánsabb megoldásában.

Ebben a cikkben a bináris fák alapjait vizsgáljuk meg, beleértve a szerkezetüket, a csomópontok beszúrását és törlését, a bejárást és az elemkeresést. Gyakorlati példákat is mutatunk C programozási nyelven , hogy láthasd, hogyan alkalmazhatók ezek a fogalmak a gyakorlatban.

Tehát kezdjük!

Mik azok a bináris fák?

A bináris fák egymáshoz kapcsolódó csomópontokból álló hierarchikus adatstruktúrák. Minden csomópontnak legfeljebb két gyermekcsomópontja lehet: egy a bal oldalon és egy a jobb oldalon. Ez a kétágú struktúra különbözteti meg a bináris fákat más adatstruktúráktól.

Egy bináris fában az első csomópontot gyökércsomópontnak nevezzük. A gyermek csomópontokat gyermekcsomópontoknak, a gyermek nélküli csomópontokat pedig levélcsomópontoknak nevezzük. Az azonos szinten lévő csomópontokat testvércsomópontoknak nevezzük.

A bináris fák előnyei

A bináris fák számos előnnyel rendelkeznek a hatékony adattárolás és keresés terén. A legfontosabb előnyök közé tartozik:

1. Hatékony keresésA bináris fák lehetővé teszik az elemek gyorsabb keresését futás közben, mint más adatstruktúrák, például a hivatkozott listák. Ez a fa hierarchikus felépítésének és az adatkészlet gyors particionálási képességének köszönhető.
2. Rugalmas be- és kiszerelésA bináris fák nagymértékben alkalmazkodnak a csomópont-beillesztési és -törlési műveletekhez. Ellentétben a statikus adatstruktúrákkal, például a tömbökkel, a bináris fák növekedhetnek és dinamikusan változtathatják szerkezetüket.
3. Hierarchikus kapcsolatok ábrázolásaA bináris fák különösen hasznosak az elemek közötti hierarchikus kapcsolatok ábrázolására. Például egy fájlkönyvtár-struktúrában minden könyvtár a fa csomópontjaként ábrázolható, az alkönyvtárak és a fájlok gyermekcsomópontjaiként.

Egy bináris fa szerkezete

Mielőtt belemerülnénk a bináris fák megvalósításába C-ben, fontos megérteni az alapvető szerkezetüket. A bináris fa minden csomópontja tartalmaz egy értéket és hivatkozásokat a bal és jobb oldali gyermekcsomópontjaira, ha van ilyen.

A következő táblázat egy bináris fa csomópontjának szerkezetét mutatja be:

Bináris csomópont
érték
Bal csomópont
Jobb csomópont

Minden csomópont bármilyen típusú adatot tárolhat, például egész számokat, karaktereket vagy összetettebb struktúrákat. A gyökércsomópont a fa kiindulópontja, és onnan érhetjük el az összes többi csomópontot.

Bináris fák megvalósítása C-ben

Most, hogy már ismerjük a bináris fák alapjait, itt az ideje, hogy implementáljuk őket C programozási nyelven . Ezután megnézzük, hogyan deklarálhatunk és használhatunk egy bináris fa struktúrát C-ben.

A bináris fastruktúra deklarálása

C-ben egy bináris fa szerkezetét egy szerkezet és mutatók segítségével deklarálhatjuk. Íme a szerkezet alapvető deklarációja:

struct NodoArbol {
    int valor;
    struct NodoArbol* izquierdo;
    struct NodoArbol* derecho;
};

Ebben a szerkezetben valor a csomópontban tárolt értéket jelenti, és izquierdo y derecho mutatók a bal, illetve a jobb gyermekcsomópontra.

Új csomópont létrehozása

Új csomópont létrehozásához a bináris fában memóriát kell lefoglalnunk a csomópont számára, és be kell állítani az értékeit. Itt van egy C függvény, amely új csomópontot hoz létre:

struct NodoArbol* crearNodo(int valor) {
    struct NodoArbol* nodo = (struct NodoArbol*)malloc(sizeof(struct NodoArbol));
    nodo->valor = valor;
    nodo->izquierdo = NULL;
    nodo->derecho = NULL;
    return nodo;
}

A funkció malloc A dinamikus memória csomóponthoz való lefoglalására szolgál. Ezután beállítjuk a csomópont értékeit, és visszaadjuk a létrehozott csomópontot.

Csomópontok beillesztése

A csomópontbeillesztés a bináris fák alapvető folyamata. Lehetővé teszi új elemek hozzáadását a fához a megfelelő pozícióban a csomópontérték alapján. Az alábbiakban egy C függvény található, amellyel egy csomópontot beszúrhat egy bináris fába:

struct NodoArbol* insertarNodo(struct NodoArbol* raiz, int valor) {
    if (raiz == NULL) {
        return crearNodo(valor);
    }

    if (valor < raiz->valor) {
        raiz->izquierdo = insertarNodo(raiz->izquierdo, valor);
    } else if (valor > raiz->valor) {
        raiz->derecho = insertarNodo(raiz->derecho, valor);
    }

    return raiz;
}

Ez a függvény egy mutatót kap a fa gyökerére és a beillesztendő csomópont értékére. Ha a gyökér nulla, az azt jelenti, hogy a fa üres, és létrehozunk egy új csomópontot a gyökérben. Ellenkező esetben összehasonlítjuk a csomópont értékét a gyökér értékével, és eldöntjük, hogy a csomópontot balra vagy jobbra illesztjük be.

Csomópontok törlése

A bináris fában lévő csomópontok törlése kissé bonyolultabb lehet. Ez több esettől függ, például, hogy a törölni kívánt csomópontnak vannak-e gyermekei vagy sem. Az alábbiakban látható egy C függvény a bináris fa csomópontjának törlésére:

struct NodoArbol* eliminarNodo(struct NodoArbol* raiz, int valor) {
    if (raiz == NULL) {
        return raiz;
    }

    if (valor < raiz->valor) {
        raiz->izquierdo = eliminarNodo(raiz->izquierdo, valor);
    } else if (valor > raiz->valor) {
        raiz->derecho = eliminarNodo(raiz->derecho, valor);
    } else {
        if (raiz->izquierdo == NULL) {
            struct NodoArbol* temp = raiz->derecho;
            free(raiz);
            return temp;
        } else if (raiz->derecho == NULL) {
            struct NodoArbol* temp = raiz->izquierdo;
            free(raiz);
            return temp;
        }

        struct NodoArbol* sucesor = encontrarSucesor(raiz->derecho);
        raiz->valor = sucesor->valor;
        raiz->derecho = eliminarNodo(raiz->derecho, sucesor->valor);
    }

    return raiz;
}

Ebben a függvényben ellenőrizzük, hogy a csomópont értéke kisebb-e, nagyobb-e vagy egyenlő-e az aktuális gyökér értékével. Az esettől függően a következő műveleteket hajtjuk végre:

• Ha az érték kisebb, akkor a fa bal oldalára megyünk.
• Ha az érték nagyobb, akkor a fától jobbra megyünk.
• Ha az érték egyenlő, akkor megkeressük a csomópont legközelebbi utódját (a jobb oldali részfa legkisebb csomópontját), és lecseréljük az aktuális csomópontra. Ezután eltávolítjuk az utódot a jobb oldali részfáról.

Bejárások bináris fákon

A bejárások olyan műveletek, amelyek lehetővé teszik számunkra, hogy egy bináris fa összes csomópontját egy bizonyos sorrendben meglátogassuk. A túráknak három általános típusa van:

In-order bejárás : Először a bal oldali részfát látogatja meg, majd az aktuális csomópontot, végül pedig a jobb oldali részfát. Íme egy C függvény, amely egy bináris fa in-order bejárását hajtja végre:

void inOrden(struct NodoArbol* raiz) {
    if (raiz != NULL) {
        inOrden(raiz->izquierdo);
        printf("%d ", raiz->valor);
        inOrden(raiz->derecho);
    }
}

Előresorolt ​​bejárás : Először az aktuális csomópontot látogatja meg, majd a bal oldali részfát, végül pedig a jobb oldali részfát. Íme egy C függvény, amely egy bináris fa elősorolt ​​bejárását hajtja végre:

void preOrden(struct NodoArbol* raiz) {
    if (raiz != NULL) {
        printf("%d ", raiz->valor);
        preOrden(raiz->izquierdo);
        preOrden(raiz->derecho);
    }
}

Utósorrend szerinti bejárás : Először a bal oldali részfát, majd a jobb oldali részfát, végül pedig az aktuális csomópontot látogatja meg. Íme egy C függvény, amely egy bináris fa utósorrend szerinti bejárását hajtja végre:

void postOrden(struct NodoArbol* raiz) {
    if (raiz != NULL) {
        postOrden(raiz->izquierdo);
        postOrden(raiz->derecho);
        printf("%d ", raiz->valor);
    }
}

Elemek keresése

A bináris fában lévő elemek keresése lehetővé teszi, hogy gyorsan megtaláljunk egy adott értéket az adatstruktúrán belül. Itt van egy C függvény, amellyel elemet kereshet egy bináris fában:

struct NodoArbol* buscarElemento(struct NodoArbol* raiz, int valor) {
    if (raiz == NULL || raiz->valor == valor) {
        return raiz;
    }

    if (valor < raiz->valor) {
        return buscarElemento(raiz->izquierdo, valor);
    } else {
        return buscarElemento(raiz->derecho, valor);
    }
}

Ez a függvény rekurzív keresést hajt végre a bináris fában. Ha az aktuális csomópont értéke megegyezik a keresett értékkel, akkor a csomópont visszaadásra kerül. Ellenkező esetben a rendszer a bal vagy a jobb részfát keresi az érték alapján, és a folyamat addig ismétlődik, amíg meg nem találja az értéket, vagy el nem éri a null csomópontot.

Példák bináris fák megvalósítására C-ben

Most, hogy megismertük a bináris fák alapjait és azok megvalósítását C-ben, nézzünk meg néhány gyakorlati példát.

1. példa: Bináris fa létrehozása

Tegyük fel, hogy egy bináris fát szeretnénk létrehozni a következő értékekkel: 10, 5, 15, 3, 7, 13, 18. C-ben a következőképpen tehetjük meg:

int main() {
    struct NodoArbol* raiz = NULL;

    raiz = insertarNodo(raiz, 10);
    raiz = insertarNodo(raiz, 5);
    raiz = insertarNodo(raiz, 15);
    raiz = insertarNodo(raiz, 3);
    raiz = insertarNodo(raiz, 7);
    raiz = insertarNodo(raiz, 13);
    raiz = insertarNodo(raiz, 18);

    return 0;
}

Ebben a példában létrehozunk egy mutatót a fa gyökerére, majd használjuk a függvényt insertarNodo az értékek hozzáadásához a fához.

2. példa: A bináris fa sorrendben történő bejárása

A bináris fa értékeinek sorrendben történő kinyomtatásához hívhatjuk a függvényt inOrden alábbiak szerint:

int main() {
    // Crear el árbol binario

    printf("Recorrido en orden: ");
    inOrden(raiz);
    printf("\n");

    return 0;
}

Ez a példa a fában lévő értékeket növekvő sorrendben nyomtatja ki.

Preguntas frecuentes

1. Mi a különbség a bináris fa és a bináris keresőfa között?

A bináris keresőfa (BST) egy speciális bináris fa, amelyben az elemek úgy vannak elrendezve, hogy a kisebb értékek a bal oldalon, a nagyobbak pedig a jobb oldalon legyenek. Ez a hagyományos bináris fához képest hatékonyabb keresést tesz lehetővé az elemek között.

2. Lehetnek-e duplikált értékekkel rendelkező csomópontok egy bináris fában?

Igen, lehetséges, hogy egy bináris fában duplikált értékekkel rendelkező csomópontok legyenek. A megvalósítástól és a bináris fa konkrét szabályaitól függően azonban különböző módokon lehet kezelni a duplikált csomópontokat. Egyes megvalósítások engedélyezhetik a duplikációkat, és tetszőleges sorrendben tárolhatják azokat, míg mások megkövetelhetik, hogy az ismétlődő értékeket speciálisan kezeljék vagy eldobják.

3. Hogyan távolíthatok el egy adott csomópontot egy bináris fából?

Egy adott csomópont bináris fából való eltávolításához kövesse az alábbi lépéseket:

1. Keresse meg a törölni kívánt csomópontot fakereséssel.
2. Tekintsük az eltávolítás különböző eseteit:
   • Ha a csomópontnak nincsenek gyermekei, egyszerűen törölheti, és felszabadíthatja a memóriáját.
   • Ha a csomópontnak csak egy gyermeke van, lecserélheti a csomópontot a gyermekével.
   • Ha a csomópontnak két gyermeke van, meg kell keresni a legközelebbi utódát (a jobb oldali részfa legkisebb csomópontját), és a törölni kívánt csomópont értékét az utód értékére kell cserélni. Ezután távolítsa el az utódot a fáról.
3. Szükség szerint módosítja a hivatkozásokat és mutatókat, hogy fenntartsa a megfelelő fastruktúrát.

4. Mi az a teljes bináris fa?

A teljes bináris fa a bináris fa egy speciális típusa, amelyben minden szint, esetleg az utolsó kivételével, teljesen ki van töltve, és az utolsó szint csomópontjai a lehető legtávolabbra helyezkednek el. Ez azt jelenti, hogy minden csomópontnak két gyermeke van, kivéve esetleg az utolsó szinten lévő csomópontokat, amelyeknek lehet egy gyermeke vagy nincsenek gyermekei.

5. Mekkora a bináris fa magassága?

A bináris fa magassága a gyökértől a levélig vezető leghosszabb út hossza. Más szóval, ez a gyökér és a fa bármely levele közötti élek maximális száma. A magasság mérése a szintek számában történik, tehát a csak egy csomóponttal rendelkező fa magassága 0, az üres fának nincs magassága.

6. Mikor használjak bináris fát a programjaimban?

A bináris fák különféle helyzetekben hasznosak. Néhány gyakori eset, amikor bináris fákat használhat:

• Hatékony elemkeresés: Ha gyorsan meg kell keresnie egy adatszerkezet elemeit, egy bináris fa hatékony hozzáférést biztosíthat az adatokhoz.
• Hierarchikus kapcsolatok ábrázolása: A bináris fák ideálisak a hierarchikus kapcsolatok ábrázolására, mint például a könyvtárszerkezet fájlrendszer.
• Adatrendezés: A bináris keresési fák segítségével hatékonyan rendezheti az adatokat, és logaritmikus időben hajthat végre kereséseket, beszúrásokat és törléseket.

Ne felejtse el felmérni igényeit, és mérlegelje a bináris fákon végzett műveletek összetettségét, mielőtt úgy döntene, hogy ezeket a programjaiban használja.

Következtetés

Ebben az átfogó útmutatóban a C nyelvű bináris fák alapvető fogalmait tártuk fel. Megismertük a szerkezetüket, a csomópontok beillesztését és eltávolítását, a bejárások végrehajtását és az elemek keresését egy bináris fában.

Reméljük, hogy ez az útmutató alapos ismereteket adott a bináris fákról és azok C-ben való megvalósításáról. A bináris fák sokoldalú és hatékony adatstruktúrák, amelyek segíthetnek a programozás során felmerülő problémák széles körének megoldásában.

Ne felejtsen el gyakorolni és kísérletezni a bemutatott példákkal, hogy jobban megértse a bináris fákat C nyelven. Sok sikert a szoftvertanulási és -fejlesztési úthoz!