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

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

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

Binarna stabla su fundamentalne strukture podataka u računarstvu i koriste se u širokom spektru primjena. Razumijevanje njihovog funkcionisanja i načina implementacije pomoći će vam da efikasnije 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 pretragu 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!

Šta 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 lijevo i jedan desno. Ova struktura sa dvije grane je ono što razlikuje binarna stabla od drugih struktura podataka.

U binarnom stablu, prvi čvor se naziva korijenski čvor. Podređeni čvorovi se nazivaju podređeni čvorovi, a čvorovi bez djece nazivaju se čvorovi listova. Čvorovi na istom nivou nazivaju se srodni čvorovi.

Prednosti binarnih stabala

Binarna stabla nude nekoliko prednosti u smislu efikasnog skladištenja i pretraživanja podataka. Neke od ključnih prednosti uključuju:

1. Efikasna pretragaBinarna stabla omogućavaju da se elementi pretražuju u vremenu izvođenja brže od drugih struktura podataka, kao što su povezane liste. To je zbog hijerarhijske strukture stabla i njegove sposobnosti da brzo particionira skup podataka.
2. Fleksibilno umetanje i uklanjanjeBinarna stabla su vrlo prilagodljiva operacijama umetanja i brisanja čvorova. Za razliku od statičkih struktura podataka kao što su nizovi, binarna stabla mogu dinamički rasti i mijenjati svoju strukturu.
3. Predstavljanje hijerarhijskih odnosaBinarna stabla su posebno korisna za predstavljanje hijerarhijskih odnosa između elemenata. Na primjer, u strukturi direktorija datoteka, svaki direktorij može biti predstavljen kao čvor u stablu, sa poddirektorijumima i datotekama kao 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 njegov lijevi i desni podređeni čvor, ako ih ima.

Sljedeća tabela 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 tač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.

Deklarisanje strukture binarnog stabla

U C-u možemo deklarisati strukturu binarnog stabla koristeći strukturu i pokazivače. Evo osnovne deklaracije 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, respektivno.

Kreiranje novog čvora

Da bismo kreirali novi čvor u binarnom stablu, moramo dodijeliti memoriju za čvor i postaviti njegove vrijednosti. Evo C funkcije koja kreira 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 kreirani čvor.

Umetanje čvorova

Umetanje čvorova je osnovni proces u binarnim stablima. Omogućava vam da dodate nove elemente stablu na ispravnu poziciju na osnovu 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 null, to znači da je stablo prazno i ​​da kreiramo novi čvor u korijenu. U suprotnom, upoređujemo vrijednost čvora sa vrijednošću korijena i odlučujemo da li ćemo čvor umetnuti lijevo ili desno.

Brisanje čvorova

Brisanje čvorova u binarnom stablu može biti malo složenije. Zavisi od nekoliko slučajeva, kao što je da li čvor koji treba obrisati ima 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 da li je vrijednost čvora manja, veća ili jednaka vrijednosti trenutnog korijena. U zavisnosti od slučaja, sprovodimo sledeć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.

Prelasci u binarnim stablima

Prelasci su operacije koje nam omogućavaju da posjetimo sve čvorove binarnog stabla određenim redoslijedom. Postoje tri uobičajene vrste tura:

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

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

Prethodni obilazak : Prvo posjećuje trenutni čvor, zatim lijevo podstablo i na kraju desno podstablo. Evo C funkcije koja izvodi prethodni 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);
    }
}

Potražite elemente

Traženje elemenata u binarnom stablu omogućava nam da brzo pronađemo određenu vrijednost unutar strukture podataka. Evo C funkcije 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 vrši rekurzivnu pretragu u binarnom stablu. Ako je vrijednost trenutnog čvora jednaka traženoj vrijednosti, čvor se vraća. U suprotnom, lijevo ili desno podstablo se traži na osnovu vrijednosti i proces se ponavlja sve dok se vrijednost ne pronađe ili dok se ne dostigne nulti čvor.

Primjeri implementacije binarnih stabala u C

Sada kada smo pokrili osnove binarnih stabala i kako ih implementirati u C, pogledajmo nekoliko praktičnih primjera.

Primjer 1: Kreiranje binarnog stabla

Pretpostavimo da želimo da kreiramo binarno stablo sa sledećim vrednostima: 10, 5, 15, 3, 7, 13, 18. Evo kako to možemo da uradimo u 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;
}

U ovom primjeru kreiramo pokazivač na korijen stabla, a zatim koristimo funkciju insertarNodo da dodate vrijednosti stablu.

Primjer 2: Obilaženje binarnog stabla po redu

Za ispis vrijednosti binarnog stabla po redu, možemo pozvati funkciju inOrden kao što 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 stabla binarnog pretraživanja?

Binarno stablo pretraživanja (BST) je posebna vrsta binarnog stabla u kojoj su elementi raspoređeni tako da su manje vrijednosti lijevo, a veće desno. Ovo omogućava efikasnije pretraživanje elemenata u poređenju sa običnim binarnim stablom.

2. Mogu li imati čvorove sa dupliranim vrijednostima u binarnom stablu?

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

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

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

1. Pronađite čvor koji želite da izbrišete koristeći pretragu stabla.
2. Razmotrite različite slučajeve eliminacije:
   • Ako čvor nema djece, možete ga jednostavno izbrisati i osloboditi njegovu memoriju.
   • Ako čvor ima samo jedno dijete, možete zamijeniti čvor njegovim podređenim.
   • Ako čvor ima dva potomka, morate pronaći najbližeg nasljednika (najmanji čvor u desnom podstablu) i zamijeniti vrijednost čvora koji treba obrisati vrijednošću nasljednika. Zatim uklonite nasljednika iz stabla.
3. Prilagođava veze i pokazivače prema potrebi za održavanje ispravne strukture stabla.

4. Šta je puno binarno stablo?

Puno binarno stablo je posebna vrsta binarnog stabla u kojoj su svi nivoi, osim eventualno posljednjeg, potpuno popunjeni, a čvorovi posljednjeg nivoa se nalaze što je više moguće lijevo. To znači da svi čvorovi imaju dva djeteta, osim eventualno čvorova na posljednjem nivou, koji mogu imati jedno dijete ili nijedno.

5. Kolika je visina binarnog stabla?

Visina binarnog stabla je dužina najduže staze od korena do lista. Drugim riječima, to je maksimalni broj rubova između korijena i bilo kojeg lista u stablu. Visina se mjeri u smislu broja nivoa, tako da drvo sa samo jednim čvorom ima visinu 0, a prazno drvo nema visinu.

6. Kada treba da koristim 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:

• Efikasno traženje elemenata: Ako trebate brzo potražiti elemente u strukturi podataka, binarno stablo može pružiti efikasan pristup podacima.
• Predstavljanje hijerarhijskih odnosa: Binarna stabla su idealna za predstavljanje hijerarhijskih odnosa, kao što je struktura direktorija u sistem datoteka.
• Sortiranje podataka: Možete koristiti binarna stabla pretraživanja za efikasno sortiranje podataka i obavljanje pretraživanja, umetanja i brisanja u logaritamskom vremenu.

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

zaključak

U ovom sveobuhvatnom vodiču istražili smo osnovne koncepte binarnih stabala u C. Naučili smo o njihovoj strukturi, kako umetati i uklanjati čvorove, obavljati prelaske 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. Sretno na vašem putu učenja i razvoja softvera!