Binarna stabla u C-u: Potpuni vodič za početnike

Informatec Digital » Algoritmi » Binarna stabla u C-u: Potpuni vodič za početnike

Dobrodošli u ovaj sveobuhvatni vodič o binarnim stablima u C-u. U ovom ćemo članku istražiti osnove binarnih stabala i kako ih implementirati u programski jezik C Ako ste početnik u programiranju ili samo želite poboljšati svoje C vještine, ovaj je vodič za vas.

Binarna stabla su temeljne strukture podataka u računalstvu i koriste se u širokom rasponu primjena. Razumijevanje načina na koji funkcioniraju i kako ih implementirati pomoći će vam da učinkovitije i elegantnije rješavate složene probleme.

U ovom članku istražit ćemo osnove binarnih stabala, uključujući njihovu strukturu, umetanje i brisanje čvorova, prolazak kroz njih i pretraživanje elemenata. Također ćemo pružiti praktične primjere u programskom jeziku C kako biste mogli vidjeti kako se ovi koncepti primjenjuju u praksi.

Pa počnimo!

Što su binarna stabla?

Binarna stabla su hijerarhijske strukture podataka sastavljene od međusobno povezanih čvorova. Svaki čvor može imati do dva podređena čvora: jedan s lijeve i jedan s desne strane. Ova struktura s dvije grane ono je što razlikuje binarna stabla od ostalih struktura podataka.

U binarnom stablu, prvi čvor se naziva korijenski čvor. Čvorovi-djeteti nazivaju se čvorovi-djeteti, a čvorovi bez potomaka nazivaju se čvorovi-lišćari. Čvorovi na istoj razini nazivaju se srodnim čvorovima.

Prednosti binarnih stabala

Binarna stabla nude nekoliko prednosti u smislu učinkovite pohrane podataka i pretraživanja. Neke od ključnih prednosti uključuju:

1. Učinkovito pretraživanjeBinarna stabla omogućuju brže pretraživanje elemenata tijekom izvođenja od drugih struktura podataka, kao što su povezani popisi. To je zbog hijerarhijske strukture stabla i njegove sposobnosti da brzo podijeli skup podataka.
2. Fleksibilno umetanje i uklanjanjeBinarna stabla vrlo su prilagodljiva operacijama umetanja i brisanja čvorova. Za razliku od statičkih struktura podataka kao što su nizovi, binarna stabla mogu rasti i dinamički mijenjati svoju strukturu.
3. Prikaz hijerarhijskih odnosaBinarna stabla su posebno korisna za predstavljanje hijerarhijskih odnosa između elemenata. Na primjer, u strukturi direktorija datoteka, svaki direktorij može se predstaviti kao čvor u stablu, s poddirektorijima i datotekama kao svojim podređenim čvorovima.

Struktura binarnog stabla

Prije nego što zaronimo u implementaciju binarnih stabala u C-u, važno je razumjeti njihovu osnovnu strukturu. Svaki čvor u binarnom stablu sadrži vrijednost i reference na svoje lijeve i desne podređene čvorove, ako ih ima.

Sljedeća tablica prikazuje strukturu čvora u binarnom stablu:

Binarni čvor
hrabrost
Lijevi čvor
Desni čvor

Svaki čvor može pohraniti bilo koju vrstu podataka, kao što su cijeli brojevi, znakovi ili složenije strukture. Korijenski čvor je početna točka stabla i iz njega možemo pristupiti svim ostalim čvorovima.

Implementacija binarnih stabala u C

Sada kada imamo osnovno razumijevanje binarnih stabala, vrijeme je da ih implementiramo u programskom jeziku C. Zatim ćemo vidjeti kako deklarirati i koristiti binarnu strukturu stabla u C-u.

Deklaracija strukture binarnog stabla

U C-u možemo deklarirati strukturu binarnog stabla pomoću strukture i pokazivača. Ovdje je osnovna deklaracija strukture:

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

U ovoj strukturi, valor predstavlja vrijednost pohranjenu u čvoru, i izquierdo y derecho su pokazivači na lijevi i desni podređeni čvor, redom.

Stvaranje novog čvora

Da bismo stvorili novi čvor u binarnom stablu, moramo dodijeliti memoriju za čvor i postaviti njegove vrijednosti. Ovdje je C funkcija koja stvara novi čvor:

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

Funkcija malloc Koristi se za dodjelu dinamičke memorije čvoru. Zatim postavljamo vrijednosti čvora i vraćamo stvoreni čvor.

Umetanje čvorova

Umetanje čvorova temeljni je proces u binarnim stablima. Omogućuje vam dodavanje novih elemenata u stablo na ispravnom položaju na temelju vrijednosti čvora. Ispod je C funkcija za umetanje čvora u binarno stablo:

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

Ova funkcija prima pokazivač na korijen stabla i vrijednost čvora za umetanje. Ako je korijen nula, to znači da je stablo prazno i ​​da stvaramo novi čvor u korijenu. U suprotnom, uspoređujemo vrijednost čvora s vrijednošću korijena i odlučujemo hoćemo li umetnuti čvor lijevo ili desno.

Brisanje čvorova

Brisanje čvorova u binarnom stablu može biti malo složenije. Ovisi o nekoliko slučajeva, primjerice o tome ima li čvor koji se briše djecu ili ne. Ispod je C funkcija za brisanje čvora u binarnom stablu:

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

U ovoj funkciji provjeravamo je li vrijednost čvora manja, veća ili jednaka vrijednosti trenutnog korijena. Ovisno o slučaju, provodimo sljedeće radnje:

• Ako je vrijednost manja, idemo lijevo od stabla.
• Ako je vrijednost veća, idemo desno od stabla.
• Ako je vrijednost jednaka, nalazimo najbližeg nasljednika čvora (najmanji čvor u desnom podstablu) i zamjenjujemo ga trenutnim čvorom. Zatim uklanjamo nasljednika iz desnog podstabla.

Traverzacije u binarnim stablima

Obilasci su operacije koje nam omogućuju da posjećujemo sve čvorove binarnog stabla određenim redoslijedom. Postoje tri uobičajene vrste tura:

Obilazak po redu : Prvo posjećuje lijevo podstablo, zatim trenutni čvor i na kraju desno podstablo. Evo C funkcije koja izvodi obilazak binarnog stabla po redu:

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

Preduređeni obilazak : Prvo posjećuje trenutni čvor, zatim lijevo podstablo i na kraju desno podstablo. Evo C funkcije koja izvodi preduređeni obilazak binarnog stabla:

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

Prolazak nakon redoslijeda : Prvo posjećuje lijevo podstablo, zatim desno podstablo i na kraju trenutni čvor. Evo C funkcije koja izvodi prolazak binarnog stabla nakon redoslijeda:

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

Traženje elemenata

Traženje elemenata u binarnom stablu omogućuje nam brzo pronalaženje određene vrijednosti unutar strukture podataka. Ovdje je C funkcija za traženje elementa u binarnom stablu:

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

Ova funkcija izvodi rekurzivno pretraživanje u binarnom stablu. Ako je vrijednost trenutnog čvora jednaka traženoj vrijednosti, vraća se čvor. U suprotnom, lijevo ili desno podstablo se pretražuje na temelju vrijednosti i proces se ponavlja dok se vrijednost ne pronađe ili dok se ne dosegne nulti čvor.

Primjeri implementacije binarnih stabala u C-u

Sada kada smo pokrili osnove binarnih stabala i kako ih implementirati u C, pogledajmo neke praktične primjere.

Primjer 1: Stvaranje binarnog stabla

Pretpostavimo da želimo stvoriti binarno stablo sa sljedećim vrijednostima: 10, 5, 15, 3, 7, 13, 18. Evo kako to možemo učiniti u C-u:

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

U ovom primjeru stvaramo pokazivač na korijen stabla i zatim koristimo funkciju insertarNodo za dodavanje vrijednosti stablu.

Primjer 2: Redoslijedno obilaženje binarnog stabla

Za ispis vrijednosti binarnog stabla po redu, možemo pozvati funkciju inOrden kako slijedi:

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

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

    return 0;
}

Ovaj primjer će ispisati vrijednosti u stablu uzlaznim redoslijedom.

Često postavljana pitanja

1. Koja je razlika između binarnog stabla i binarnog stabla pretraživanja?

Binarno stablo pretraživanja (BST) posebna je vrsta binarnog stabla u kojem su elementi raspoređeni tako da su manje vrijednosti s lijeve, a veće vrijednosti s desne strane. To omogućuje učinkovitije pretraživanje elemenata u usporedbi s uobičajenim binarnim stablom.

2. Mogu li imati čvorove s dupliciranim vrijednostima u binarnom stablu?

Da, moguće je imati čvorove s dupliciranim vrijednostima u binarnom stablu. Međutim, ovisno o implementaciji i specifičnim pravilima binarnog stabla, mogu postojati različiti načini rješavanja dvostrukih čvorova. Neke implementacije mogu dopustiti duplikate i pohraniti ih bilo kojim redoslijedom, dok druge mogu zahtijevati da se dupliciranim vrijednostima posebno postupa ili da se odbace.

3. Kako mogu ukloniti određeni čvor iz binarnog stabla?

Da biste uklonili određeni čvor iz binarnog stabla, morate slijediti ove korake:

1. Pronađite čvor koji želite izbrisati pomoću pretraživanja stabla.
2. Razmotrite različite slučajeve eliminacije:
   • Ako čvor nema djecu, možete ga jednostavno izbrisati i osloboditi njegovu memoriju.
   • Ako čvor ima samo jedno dijete, možete zamijeniti čvor njegovim dijetetom.
   • Ako čvor ima dva djeteta, morate pronaći najbližeg nasljednika (najmanji čvor u desnom podstablu) i zamijeniti vrijednost čvora koji se briše s vrijednošću nasljednika. Zatim uklonite nasljednika iz stabla.
3. Po potrebi prilagođava poveznice i pokazivače za održavanje ispravne strukture stabla.

4. Što je puno binarno stablo?

Puno binarno stablo je posebna vrsta binarnog stabla u kojem su sve razine, osim eventualno zadnje, potpuno popunjene, a čvorovi posljednje razine smješteni su što je moguće više ulijevo. To znači da svi čvorovi imaju dvoje djece, osim eventualno čvorova na posljednjoj razini, koji mogu imati jedno ili nijedno dijete.

5. Kolika je visina binarnog stabla?

Visina binarnog stabla je duljina najdužeg puta od korijena do lista. Drugim riječima, to je najveći broj rubova između korijena i bilo kojeg lista u stablu. Visina se mjeri brojem razina, tako da stablo sa samo jednim čvorom ima visinu 0, a prazno stablo nema visinu.

6. Kada trebam koristiti binarno stablo u svojim programima?

Binarna stabla su korisna u raznim situacijama. Neki uobičajeni slučajevi u kojima možete koristiti binarna stabla uključuju:

• Učinkovito traženje elemenata: Ako trebate brzo potražiti elemente u strukturi podataka, binarno stablo može pružiti učinkovit pristup podacima.
• Predstavljanje hijerarhijskih odnosa: binarna stabla su idealna za predstavljanje hijerarhijskih odnosa, kao što je struktura direktorija u datotečni sustav.
• Razvrstavanje podataka: Možete koristiti stabla binarnog pretraživanja za učinkovito sortiranje podataka i izvođenje pretraživanja, umetanja i brisanja u logaritamskom vremenu.

Ne zaboravite procijeniti svoje zahtjeve i razmotriti složenost operacija na binarnim stablima prije nego što ih odlučite koristiti u svojim programima.

Zaključak

U ovom opsežnom vodiču istražili smo temeljne koncepte binarnih stabala u C-u. Naučili smo o njihovoj strukturi, kako umetati i uklanjati čvorove, izvoditi obilaske i tražiti elemente u binarnom stablu.

Nadamo se da vam je ovaj vodič pružio solidno razumijevanje binarnih stabala i kako ih implementirati u C. Binarna stabla su svestrane i moćne strukture podataka koje vam mogu pomoći u rješavanju širokog spektra problema u programiranju.

Ne zaboravite vježbati i eksperimentirati s navedenim primjerima kako biste ojačali svoje razumijevanje binarnih stabala u C-u. Sretno na vašem putu učenja i razvoja softvera!