Arbori binari în C: un ghid complet pentru începători

Informatec Digital » Algoritmi » Arbori binari în C: un ghid complet pentru începători

Bine ați venit la acest ghid cuprinzător despre arborii binari în C. În acest articol, vom explora elementele de bază ale arborilor binari și cum să le implementăm în limbajul de programare C Dacă sunteți începător în programare sau doriți doar să vă îmbunătățiți abilitățile C, acest ghid este pentru dvs.

Arborii binari sunt structuri de date fundamentale în informatică și sunt utilizați într-o gamă largă de aplicații. Înțelegerea modului în care funcționează și a modului în care să îi implementați vă va ajuta să rezolvați probleme complexe mai eficient și mai elegant.

Pe parcursul acestui articol, vom explora elementele fundamentale ale arborilor binari, inclusiv structura lor, inserarea și ștergerea nodurilor, traversarea și căutarea elementelor. De asemenea, vom oferi exemple practice în limbajul de programare C, astfel încât să puteți vedea cum se aplică aceste concepte în practică.

Asadar, haideti sa începem!

Ce sunt arborii binari?

Arborii binari sunt structuri de date ierarhice compuse din noduri interconectate. Fiecare nod poate avea până la două noduri copil: unul la stânga și unul la dreapta. Această structură cu două ramuri este cea care distinge arborii binari de alte structuri de date.

Într-un arbore binar, primul nod este numit nodul rădăcină. Nodurile copil sunt numite noduri copil, iar nodurile fără copii sunt numite noduri frunză. Nodurile de la același nivel sunt numite noduri frați.

Beneficiile arborilor binari

Arborii binari oferă mai multe avantaje în ceea ce privește stocarea și căutarea eficientă a datelor. Unele dintre beneficiile cheie includ:

1. Căutare eficientăArborii binari permit căutarea elementelor în timpul execuției mai rapid decât alte structuri de date, cum ar fi listele legate. Acest lucru se datorează structurii ierarhice a arborelui și capacității sale de a partiționa rapid setul de date.
2. Introducere și îndepărtare flexibileArborii binari sunt foarte adaptabili la operațiunile de inserare și ștergere a nodurilor. Spre deosebire de structurile de date statice, cum ar fi matricele, arborii binari pot crește și își pot schimba structura în mod dinamic.
3. Reprezentarea relaţiilor ierarhiceArborii binari sunt folositori în special pentru reprezentarea relațiilor ierarhice dintre elemente. De exemplu, într-o structură de director de fișiere, fiecare director poate fi reprezentat ca un nod în arbore, cu subdirectoare și fișiere ca noduri secundare.

Structura unui arbore binar

Înainte de a ne aprofunda în implementarea arborilor binari în C, este important să înțelegem structura lor de bază. Fiecare nod dintr-un arbore binar conține o valoare și referințe la nodurile sale secundare din stânga și din dreapta, dacă are.

Următorul tabel arată structura unui nod într-un arbore binar:

Nod binar
bravură
Nodul din stânga
Nodul drept

Fiecare nod poate stoca orice tip de date, cum ar fi numere întregi, caractere sau structuri mai complexe. Nodul rădăcină este punctul de pornire al arborelui și de la acesta putem accesa toate celelalte noduri.

Implementarea arborilor binari în C

Acum, că avem o înțelegere de bază a arborilor binari, este timpul să îi implementăm în limbajul de programare C. În continuare, vom vedea cum se declară și se utilizează o structură de arbore binar în C.

Declararea structurii arborelui binar

În C, putem declara structura unui arbore binar folosind o structură și pointeri. Iată declarația de bază a structurii:

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

În această structură, valor reprezintă valoarea stocată în nod și izquierdo y derecho sunt pointeri către nodurile copil stânga și respectiv dreapta.

Crearea unui nou nod

Pentru a crea un nou nod în arborele binar, trebuie să alocăm memorie pentru nod și să îi setăm valorile. Iată o funcție C care creează un nou nod:

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

Funcția malloc Este folosit pentru a aloca memorie dinamică nodului. Apoi setăm valorile nodului și returnăm nodul creat.

Inserarea nodurilor

Inserarea nodurilor este un proces fundamental în arborii binari. Vă permite să adăugați elemente noi în arbore la poziția corectă pe baza valorii nodului. Mai jos este o funcție C pentru a insera un nod într-un arbore binar:

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

Această funcție primește un pointer către rădăcina arborelui și valoarea nodului de inserat. Dacă rădăcina este nulă, înseamnă că arborele este gol și creăm un nou nod la rădăcină. În caz contrar, comparăm valoarea nodului cu valoarea rădăcinii și decidem dacă introducem nodul la stânga sau la dreapta.

Ștergerea nodurilor

Ștergerea nodurilor dintr-un arbore binar poate fi puțin mai complexă. Depinde de mai multe cazuri, cum ar fi dacă nodul de șters are copii sau nu. Mai jos este o funcție C pentru a șterge un nod dintr-un arbore binar:

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 această funcție, verificăm dacă valoarea nodului este mai mică, mai mare sau egală cu valoarea rădăcinii curente. În funcție de caz, efectuăm următoarele acțiuni:

• Dacă valoarea este mai mică, mergem în stânga arborelui.
• Dacă valoarea este mai mare, mergem în dreapta arborelui.
• Dacă valoarea este egală, găsim succesorul cel mai apropiat al nodului (cel mai mic nod din subarborele din dreapta) și îl înlocuim cu nodul curent. Apoi eliminăm succesorul din subarborele din dreapta.

Traversări în arbori binari

Traversarile sunt operațiuni care ne permit să vizităm toate nodurile unui arbore binar într-o anumită ordine. Există trei tipuri comune de tururi:

Parcurgere în ordine : Vizitează mai întâi subarborele din stânga, apoi nodul curent și în final subarborele din dreapta. Iată o funcție C care efectuează o parcurgere în ordine a unui arbore binar:

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

Parcurgere în preordine : Vizitează mai întâi nodul curent, apoi subarborele stâng și în final subarborele drept. Iată o funcție C care efectuează o parcurgere în preordine a unui arbore binar:

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

Parcurgere post-ordine : Vizitează mai întâi subarborele din stânga, apoi subarborele din dreapta și în final nodul curent. Iată o funcție C care efectuează o parcurgere post-ordine a unui arbore binar:

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

Căutați elemente

Căutarea elementelor într-un arbore binar ne permite să găsim rapid o anumită valoare în structura de date. Iată o funcție C pentru a căuta un element într-un arbore binar:

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

Această funcție efectuează o căutare recursivă în arborele binar. Dacă valoarea nodului curent este egală cu valoarea căutată, nodul este returnat. În caz contrar, subarborele din stânga sau din dreapta este căutat pe baza valorii și procesul se repetă până când valoarea este găsită sau se ajunge la un nod nul.

Exemple de implementare a arborilor binari în C

Acum că am acoperit elementele de bază ale arborilor binari și cum să le implementăm în C, să ne uităm la câteva exemple practice.

Exemplul 1: Crearea unui arbore binar

Să presupunem că vrem să creăm un arbore binar cu următoarele valori: 10, 5, 15, 3, 7, 13, 18. Iată cum putem face acest lucru î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 acest exemplu, creăm un pointer către rădăcina arborelui și apoi folosim funcția insertarNodo pentru a adăuga valorile la arbore.

Exemplul 2: parcurgerea în ordine a arborelui binar

Pentru a tipări în ordine valorile arborelui binar, putem apela funcția inOrden după cum urmează:

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

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

    return 0;
}

Acest exemplu va tipări valorile în arbore în ordine crescătoare.

Întrebări frecvente

1. Care este diferența dintre un arbore binar și un arbore binar de căutare?

Un arbore binar de căutare (BST) este un tip special de arbore binar în care elementele sunt aranjate astfel încât valorile mai mici să fie în stânga și valorile mai mari în dreapta. Acest lucru permite o căutare mai eficientă a elementelor în comparație cu un arbore binar obișnuit.

2. Pot avea noduri cu valori duplicate într-un arbore binar?

Da, este posibil să aveți noduri cu valori duplicate într-un arbore binar. Cu toate acestea, în funcție de implementare și de regulile specifice ale arborelui binar, pot exista moduri diferite de a trata nodurile duplicate. Unele implementări pot permite duplicate și le stochează în orice ordine, în timp ce altele pot necesita ca valorile duplicate să fie tratate special sau eliminate.

3. Cum pot elimina un anumit nod dintr-un arbore binar?

Pentru a elimina un anumit nod dintr-un arbore binar, trebuie să urmați acești pași:

1. Găsiți nodul pe care doriți să-l ștergeți folosind o căutare în arbore.
2. Luați în considerare diferitele cazuri de eliminare:
   • Dacă nodul nu are copii, puteți pur și simplu să-l ștergeți și să-i eliberați memoria.
   • Dacă nodul are un singur copil, puteți înlocui nodul cu copilul său.
   • Dacă nodul are doi copii, trebuie să găsiți cel mai apropiat succesor (cel mai mic nod din subarborele din dreapta) și să înlocuiți valoarea nodului de șters cu valoarea succesorului. Apoi eliminați succesorul din arbore.
3. Ajustează legăturile și indicatorii după cum este necesar pentru a menține structura corectă a arborescentului.

4. Ce este un arbore binar complet?

Un arbore binar complet este un tip special de arbore binar în care toate nivelurile, cu excepția eventualului ultimului, sunt complet umplute, iar nodurile ultimului nivel sunt situate cât mai în stânga posibil. Aceasta înseamnă că toate nodurile au doi copii, cu excepția, eventual, nodurile de la ultimul nivel, care pot avea unul sau niciun copil.

5. Care este înălțimea unui arbore binar?

Înălțimea unui arbore binar este lungimea celei mai lungi căi de la rădăcină la o frunză. Cu alte cuvinte, este numărul maxim de margini dintre rădăcină și orice frunză din copac. Înălțimea este măsurată în funcție de numărul de niveluri, astfel încât un arbore cu un singur nod are o înălțime de 0, iar un arbore gol nu are înălțime.

6. Când ar trebui să folosesc un arbore binar în programele mele?

Arborii binari sunt utili într-o varietate de situații. Unele cazuri comune în care ați putea folosi arbori binari includ:

• Căutare eficientă a elementelor: dacă trebuie să căutați rapid elemente dintr-o structură de date, un arbore binar poate oferi acces eficient la date.
• Reprezentarea relațiilor ierarhice: arborii binari sunt ideali pentru reprezentarea relațiilor ierarhice, cum ar fi structura de directoare într-un sistem de fișiere.
• Sortarea datelor: puteți utiliza arbori binari de căutare pentru a sorta eficient datele și pentru a efectua căutări, inserări și ștergeri în timp logaritmic.

Nu uitați să vă evaluați cerințele și să luați în considerare complexitatea operațiunilor pe arbori binari înainte de a decide să le utilizați în programele dumneavoastră.

Concluzie

În acest ghid cuprinzător, am explorat conceptele fundamentale ale arborilor binari în C. Am învățat despre structura lor, cum să inserăm și să eliminam noduri, să efectuăm traversări și să căutăm elemente într-un arbore binar.

Sperăm că acest ghid v-a oferit o înțelegere solidă a arborilor binari și a modului de implementare a acestora în C. Arborii binari sunt structuri de date versatile și puternice care vă pot ajuta să rezolvați o gamă largă de probleme în programare.

Nu uitați să exersați și să experimentați cu exemplele oferite pentru a vă consolida înțelegerea arborilor binari în C. Mult succes în călătoria dvs. de învățare și dezvoltare a software-ului!