Pemët binare në C: Një udhëzues i plotë për fillestarët

Informatec Digital » Algoritme » Pemët binare në C: Një udhëzues i plotë për fillestarët

Mirë se vini në këtë udhëzues gjithëpërfshirës mbi pemët binare në C. Në këtë artikull, ne do të shqyrtojmë bazat e pemëve binare dhe si t'i zbatojmë ato në gjuhën e programimit C Nëse jeni fillestar në programim ose thjesht dëshironi të përmirësoni aftësitë tuaja C, ky udhëzues është për ju.

Pemët binare janë struktura themelore të të dhënave në shkencën kompjuterike dhe përdoren në një gamë të gjerë aplikimesh. Të kuptuarit se si funksionojnë ato dhe si t'i zbatoni ato do t'ju ndihmojë të zgjidhni problemet komplekse në mënyrë më efikase dhe elegante.

Gjatë gjithë këtij artikulli, do të shqyrtojmë bazat e pemëve binare, duke përfshirë strukturën e tyre, futjen dhe fshirjen e nyjeve, përshkimin dhe kërkimin e elementeve. Gjithashtu do të ofrojmë shembuj praktikë në gjuhën e programimit C, në mënyrë që të shihni se si zbatohen këto koncepte në praktikë.

Pra, le të fillojmë!

Çfarë janë pemët binare?

Pemët binare janë struktura hierarkike të të dhënave të përbëra nga nyje të ndërlidhura. Çdo nyje mund të ketë deri në dy nyje fëmijë: një në të majtë dhe një në të djathtë. Kjo strukturë me dy degë është ajo që i dallon pemët binare nga strukturat e tjera të të dhënave.

Në një pemë binare, nyja e parë quhet nyja rrënjë. Nyjet fëmijë quhen nyje fëmijë, dhe nyjet pa fëmijë quhen nyje gjethe. Nyjet në të njëjtin nivel quhen nyje si motra.

Përfitimet e pemëve binare

Pemët binare ofrojnë disa përparësi në drejtim të ruajtjes dhe kërkimit efikas të të dhënave. Disa nga përfitimet kryesore përfshijnë:

1. Kërkim efikasPemët binare lejojnë që elementet të kërkohen në kohën e ekzekutimit më shpejt se strukturat e tjera të të dhënave, siç janë listat e lidhura. Kjo është për shkak të strukturës hierarkike të pemës dhe aftësisë së saj për të ndarë shpejt grupin e të dhënave.
2. Futje dhe heqje fleksibëlPemët binare janë shumë të adaptueshme ndaj operacioneve të futjes dhe fshirjes së nyjeve. Ndryshe nga strukturat statike të të dhënave siç janë vargjet, pemët binare mund të rriten dhe të ndryshojnë strukturën e tyre në mënyrë dinamike.
3. Përfaqësimi i marrëdhënieve hierarkikePemët binare janë veçanërisht të dobishme për përfaqësimin e marrëdhënieve hierarkike ndërmjet elementeve. Për shembull, në një strukturë drejtorie skedari, çdo direktori mund të përfaqësohet si një nyje në pemë, me nëndrejtori dhe skedarë si nyjet e saj fëmijë.

Struktura e një peme binare

Përpara se të zhytemi në zbatimin e pemëve binare në C, është e rëndësishme të kuptojmë strukturën e tyre bazë. Çdo nyje në një pemë binare përmban një vlerë dhe referenca në nyjet e saj të fëmijës majtas dhe djathtas, nëse ka ndonjë.

Tabela e mëposhtme tregon strukturën e një nyje në një pemë binare:

Nyja binare
trimëri
Nyja e majtë
Nyja e djathtë

Çdo nyje mund të ruajë çdo lloj të dhënash, të tilla si numra të plotë, karaktere ose struktura më komplekse. Nyja rrënjësore është pika e fillimit të pemës dhe prej saj mund të aksesojmë të gjitha nyjet e tjera.

Zbatimi i pemëve binare në C

Tani që kemi një kuptim bazë të pemëve binare, është koha t'i zbatojmë ato në gjuhën e programimit C. Më pas, do të shohim se si të deklarojmë dhe përdorim një strukturë peme binare në C.

Deklarimi i strukturës së pemës binare

Në C, ne mund të deklarojmë strukturën e një peme binare duke përdorur një strukturë dhe tregues. Këtu është deklarata bazë e strukturës:

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

Në këtë strukturë, valor përfaqëson vlerën e ruajtur në nyje, dhe izquierdo y derecho janë tregues drejt nyjeve të fëmijës majtas dhe djathtas, përkatësisht.

Krijimi i një nyje të re

Për të krijuar një nyje të re në pemën binare, duhet të ndajmë memorie për nyjen dhe të vendosim vlerat e saj. Këtu është një funksion C që krijon një nyje të re:

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

Funksioni malloc Përdoret për të alokuar memorie dinamike në nyje. Më pas vendosim vlerat e nyjes dhe kthejmë nyjen e krijuar.

Futja e nyjeve

Futja e nyjeve është një proces themelor në pemët binare. Ju lejon të shtoni elementë të rinj në pemë në pozicionin e duhur bazuar në vlerën e nyjës. Më poshtë është një funksion C për të futur një nyje në një pemë binare:

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

Ky funksion merr një tregues në rrënjën e pemës dhe vlerën e nyjës për të futur. Nëse rrënja është e pavlefshme, do të thotë se pema është bosh dhe ne krijojmë një nyje të re në rrënjë. Përndryshe, ne krahasojmë vlerën e nyjës me vlerën e rrënjës dhe vendosim nëse nyja do të futet majtas apo djathtas.

Fshirja e nyjeve

Fshirja e nyjeve në një pemë binare mund të jetë pak më komplekse. Varet nga disa raste, si p.sh. nëse nyja që do të fshihet ka fëmijë apo jo. Më poshtë është një funksion C për të fshirë një nyje në një pemë binare:

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

Në këtë funksion, ne kontrollojmë nëse vlera e nyjës është më e vogël, më e madhe ose e barabartë me vlerën e rrënjës aktuale. Në varësi të rastit, ne kryejmë veprimet e mëposhtme:

• Nëse vlera është më e vogël, shkojmë në të majtë të pemës.
• Nëse vlera është më e madhe, shkojmë në të djathtë të pemës.
• Nëse vlera është e barabartë, gjejmë pasardhësin më të afërt të nyjës (nyjen më të vogël në nënpemën e djathtë) dhe e zëvendësojmë atë me nyjen aktuale. Pastaj heqim pasardhësin nga nënpema e djathtë.

Kalimet në pemë binare

Kalimet janë operacione që na lejojnë të vizitojmë të gjitha nyjet e një peme binare në një rend të caktuar. Ekzistojnë tre lloje të zakonshme të turneve:

Përshkimi sipas renditjes : Viziton së pari nënpemën e majtë, pastaj nyjen aktuale dhe së fundmi nënpemën e djathtë. Ja një funksion C që kryen një përshkim sipas renditjes së një peme binare:

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

Kalimi paraprak i renditjes : Viziton së pari nyjen aktuale, pastaj nënpemën e majtë dhe së fundmi nënpemën e djathtë. Ja një funksion C që kryen një kalim paraprak të një peme binare:

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

Përshkimi pas renditjes : Viziton së pari nënpemën e majtë, pastaj nënpemën e djathtë dhe së fundmi nyjen aktuale. Ja një funksion C që kryen një përshkim pas renditjes së një peme binare:

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

Kërkoni për elementë

Kërkimi i elementeve në një pemë binare na lejon të gjejmë shpejt një vlerë specifike brenda strukturës së të dhënave. Këtu është një funksion C për të kërkuar një element në një pemë binare:

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

Ky funksion kryen një kërkim rekurziv në pemën binare. Nëse vlera e nyjes aktuale është e barabartë me vlerën e kërkuar, nyja kthehet. Përndryshe, nënpema e majtë ose e djathtë kërkohet në bazë të vlerës dhe procesi përsëritet derisa të gjendet vlera ose të arrihet një nyje null.

Shembuj të zbatimit të pemëve binare në C

Tani që kemi mbuluar bazat e pemëve binare dhe si t'i zbatojmë ato në C, le të shohim disa shembuj praktikë.

Shembulli 1: Krijimi i një peme binare

Supozoni se duam të krijojmë një pemë binare me vlerat e mëposhtme: 10, 5, 15, 3, 7, 13, 18. Ja se si mund ta bëjmë atë në C:

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

Në këtë shembull, ne krijojmë një tregues në rrënjën e pemës dhe më pas përdorim funksionin insertarNodo për të shtuar vlerat në pemë.

Shembulli 2: Kalimi sipas renditjes së pemës binare

Për të shtypur vlerat e pemës binare sipas radhës, mund të thërrasim funksionin inOrden si në vazhdim:

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

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

    return 0;
}

Ky shembull do të printojë vlerat në pemë në rend rritës.

Pyetje të shpeshta

1. Cili është ndryshimi midis një peme binare dhe një peme kërkimi binare?

Një pemë kërkimi binar (BST) është një lloj i veçantë i pemës binare në të cilin elementët janë rregulluar në mënyrë që vlerat më të vogla të jenë në të majtë dhe vlerat më të mëdha janë në të djathtë. Kjo lejon një kërkim më efikas të elementeve në krahasim me një pemë të rregullt binare.

2. A mund të kem nyje me vlera të dyfishta në një pemë binare?

Po, është e mundur të keni nyje me vlera të dyfishta në një pemë binare. Megjithatë, në varësi të zbatimit dhe rregullave specifike të pemës binare, mund të ketë mënyra të ndryshme për t'u marrë me nyjet e dyfishta. Disa zbatime mund të lejojnë dublikatë dhe t'i ruajnë ato në çdo mënyrë, ndërsa të tjerët mund të kërkojnë që vlerat e kopjuara të trajtohen posaçërisht ose të hidhen poshtë.

3. Si mund të heq një nyje specifike nga një pemë binare?

Për të hequr një nyje specifike nga një pemë binare, duhet të ndiqni këto hapa:

1. Gjeni nyjen që dëshironi të fshini duke përdorur një kërkim peme.
2. Konsideroni rastet e ndryshme të eliminimit:
   • Nëse nyja nuk ka fëmijë, thjesht mund ta fshini dhe të lironi kujtesën e saj.
   • Nëse nyja ka vetëm një fëmijë, ju mund ta zëvendësoni nyjen me fëmijën e saj.
   • Nëse nyja ka dy fëmijë, ju duhet të gjeni pasardhësin më të afërt (nyjen më të vogël në nënpemën e djathtë) dhe të zëvendësoni vlerën e nyjes që do të fshihet me vlerën e pasuesit. Pastaj hiqni pasardhësin nga pema.
3. Rregullon lidhjet dhe treguesit sipas nevojës për të ruajtur strukturën e duhur të pemës.

4. Çfarë është një pemë binare e plotë?

Një pemë binare e plotë është një lloj i veçantë i pemës binare në të cilën të gjitha nivelet, përveç ndoshta të fundit, janë të mbushura plotësisht, dhe nyjet e nivelit të fundit janë të vendosura sa më larg që të jetë e mundur në të majtë. Kjo do të thotë që të gjitha nyjet kanë dy fëmijë, me përjashtim të nyjeve në nivelin e fundit, të cilat mund të kenë një ose asnjë fëmijë.

5. Sa është lartësia e një peme binare?

Lartësia e një peme binare është gjatësia e shtegut më të gjatë nga rrënja në një gjethe. Me fjalë të tjera, është numri maksimal i skajeve midis rrënjës dhe çdo gjetheje në pemë. Lartësia matet me numrin e niveleve, kështu që një pemë me vetëm një nyje ka një lartësi prej 0, dhe një pemë bosh nuk ka lartësi.

6. Kur duhet të përdor një pemë binare në programet e mia?

Pemët binare janë të dobishme në një sërë situatash. Disa raste të zakonshme kur mund të përdorni pemë binare përfshijnë:

• Kërkimi efikas i elementeve: Nëse ju duhet të kërkoni shpejt elementë në një strukturë të dhënash, një pemë binare mund të sigurojë qasje efikase në të dhëna.
• Përfaqësimi i marrëdhënieve hierarkike: Pemët binare janë ideale për përfaqësimin e marrëdhënieve hierarkike, siç është struktura e drejtorisë në një sistemi i skedarëve.
• Renditja e të dhënave: Ju mund të përdorni pemët binar të kërkimit për të renditur në mënyrë efikase të dhënat dhe për të kryer kërkime, futje dhe fshirje në kohën logaritmike.

Mos harroni të vlerësoni kërkesat tuaja dhe të merrni parasysh kompleksitetin e operacioneve në pemë binare përpara se të vendosni t'i përdorni ato në programet tuaja.

Përfundim

Në këtë udhëzues gjithëpërfshirës, ​​ne kemi eksploruar konceptet themelore të pemëve binare në C. Ne kemi mësuar rreth strukturës së tyre, si të futim dhe heqim nyjet, të kryejmë kalime dhe të kërkojmë elemente në një pemë binare.

Shpresojmë që ky udhëzues t'ju ketë dhënë një kuptim të fortë të pemëve binare dhe si t'i zbatoni ato në C. Pemët binare janë struktura të gjithanshme dhe të fuqishme të të dhënave që mund t'ju ndihmojnë të zgjidhni një gamë të gjerë problemesh në programim.

Mos harroni të praktikoni dhe eksperimentoni me shembujt e dhënë për të forcuar të kuptuarit tuaj për pemët binare në C. Fat i mirë në udhëtimin tuaj të mësimit dhe zhvillimit të softuerit!