Binarna drevesa v C: popoln vodnik za začetnike

Informatec Digital » Algoritmi » Binarna drevesa v jeziku C: Popoln vodnik za začetnike

Dobrodošli v tem izčrpnem vodniku o binarnih drevesih v C. V tem članku bomo raziskali osnove binarnih dreves in kako jih implementirati v programski jezik C. Če ste začetnik v programiranju ali samo želite izboljšati svoje znanje C, je ta vodnik za vas.

Binarna drevesa so temeljne podatkovne strukture v računalništvu in se uporabljajo v številnih aplikacijah. Razumevanje njihovega delovanja in njihove implementacije vam bo pomagalo pri učinkovitejšem in elegantnejšem reševanju kompleksnih problemov.

V tem članku bomo raziskali osnove binarnih dreves, vključno z njihovo strukturo, vstavljanjem in brisanjem vozlišč, prečkanjem in iskanjem elementov. Predstavili bomo tudi praktične primere v programskem jeziku C , da boste lahko videli, kako se ti koncepti uporabljajo v praksi.

Pa začnimo!

Kaj so binarna drevesa?

Binarna drevesa so hierarhične podatkovne strukture, sestavljene iz med seboj povezanih vozlišč. Vsako vozlišče ima lahko do dve podrejeni vozlišči: eno na levi in ​​eno na desni. Ta dvovejna struktura je tisto, po čemer se binarna drevesa razlikujejo od drugih podatkovnih struktur.

V binarnem drevesu se prvo vozlišče imenuje korensko vozlišče. Podrejena vozlišča se imenujejo podrejena vozlišča, vozlišča brez otrok pa listna vozlišča. Vozlišča na isti ravni se imenujejo sorodna vozlišča.

Prednosti binarnih dreves

Binarna drevesa ponujajo številne prednosti v smislu učinkovitega shranjevanja in iskanja podatkov. Nekatere ključne prednosti vključujejo:

1. Učinkovito iskanjeBinarna drevesa omogočajo hitrejše iskanje elementov med izvajanjem kot druge podatkovne strukture, kot so povezani seznami. To je posledica hierarhične strukture drevesa in njegove zmožnosti hitre razdelitve nabora podatkov.
2. Prilagodljivo vstavljanje in odstranjevanjeBinarna drevesa so zelo prilagodljiva operacijam vstavljanja in brisanja vozlišč. Za razliko od statičnih podatkovnih struktur, kot so polja, lahko binarna drevesa dinamično rastejo in spreminjajo svojo strukturo.
3. Predstavitev hierarhičnih odnosovBinarna drevesa so še posebej uporabna za predstavljanje hierarhičnih odnosov med elementi. Na primer, v strukturi datotečnega imenika je lahko vsak imenik predstavljen kot vozlišče v drevesu, s podimeniki in datotekami kot podrejenimi vozlišči.

Struktura binarnega drevesa

Preden se poglobimo v implementacijo binarnih dreves v C, je pomembno razumeti njihovo osnovno strukturo. Vsako vozlišče v binarnem drevesu vsebuje vrednost in sklice na svoje levo in desno podrejeno vozlišče, če jih ima.

Naslednja tabela prikazuje strukturo vozlišča v binarnem drevesu:

Binarno vozlišče
Valor
Levo vozlišče
Desno vozlišče

Vsako vozlišče lahko shrani katero koli vrsto podatkov, kot so cela števila, znaki ali bolj zapletene strukture. Korensko vozlišče je izhodišče drevesa in iz njega lahko dostopamo do vseh ostalih vozlišč.

Implementacija binarnih dreves v C

Zdaj, ko imamo osnovno razumevanje binarnih dreves, je čas, da jih implementiramo v programskem jeziku C. Nato bomo videli, kako deklarirati in uporabljati binarno drevesno strukturo v jeziku C.

Deklaracija binarne drevesne strukture

V C lahko deklariramo strukturo binarnega drevesa z uporabo strukture in kazalcev. Tukaj je osnovna deklaracija strukture:

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

V tej strukturi, valor predstavlja vrednost, shranjeno v vozlišču, in izquierdo y derecho so kazalci na levo in desno podrejeno vozlišče.

Ustvarjanje novega vozlišča

Če želite ustvariti novo vozlišče v binarnem drevesu, moramo vozlišču dodeliti pomnilnik in nastaviti njegove vrednosti. Tukaj je funkcija C, ki ustvari novo vozlišče:

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 Uporablja se za dodelitev dinamičnega pomnilnika vozlišču. Nato nastavimo vrednosti vozlišča in vrnemo ustvarjeno vozlišče.

Vstavljanje vozlišč

Vstavljanje vozlišč je temeljni proces v binarnih drevesih. Omogoča dodajanje novih elementov v drevo na pravilen položaj glede na vrednost vozlišča. Spodaj je funkcija C za vstavljanje vozlišča v binarno drevo:

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

Ta funkcija prejme kazalec na koren drevesa in vrednost vozlišča za vstavljanje. Če je root enak nič, to pomeni, da je drevo prazno in v korenu ustvarimo novo vozlišče. V nasprotnem primeru primerjamo vrednost vozlišča z vrednostjo korena in se odločimo, ali bomo vozlišče vstavili levo ali desno.

Brisanje vozlišč

Brisanje vozlišč v binarnem drevesu je lahko nekoliko bolj zapleteno. Odvisno je od več primerov, na primer od tega, ali ima vozlišče, ki ga želite izbrisati, otroke ali ne. Spodaj je funkcija C za brisanje vozlišča v binarnem drevesu:

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

V tej funkciji preverimo, ali je vrednost vozlišča manjša, večja ali enaka vrednosti trenutnega korena. Odvisno od primera izvajamo naslednje ukrepe:

• Če je vrednost manjša, gremo levo od drevesa.
• Če je vrednost večja, gremo desno od drevesa.
• Če je vrednost enaka, poiščemo najbližjega naslednika vozlišča (najmanjše vozlišče v desnem poddrevesu) in ga nadomestimo s trenutnim vozliščem. Nato odstranimo naslednika iz desnega poddrevesa.

Prehodi v binarnih drevesih

Prehodi so operacije, ki nam omogočajo obisk vseh vozlišč binarnega drevesa v določenem vrstnem redu. Obstajajo tri običajne vrste potovanj:

Prehajanje po vrstnem redu : Najprej obišče levo poddrevo, nato trenutno vozlišče in na koncu desno poddrevo. Tukaj je funkcija v jeziku C, ki izvede prehajanje binarnega drevesa po vrstnem redu:

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

Predhodni prehod : Najprej obišče trenutno vozlišče, nato levo poddrevo in na koncu desno poddrevo. Tukaj je funkcija C, ki izvede predhodni prehod binarnega drevesa:

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

Prehajanje po vrstnem redu : Najprej obišče levo poddrevo, nato desno poddrevo in na koncu trenutno vozlišče. Tukaj je funkcija C, ki izvede prehajanje po vrstnem redu binarnega drevesa:

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

Iskanje elementov

Iskanje elementov v binarnem drevesu nam omogoča hitro iskanje določene vrednosti znotraj podatkovne strukture. Tukaj je funkcija C za iskanje elementa v binarnem drevesu:

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

Ta funkcija izvaja rekurzivno iskanje v binarnem drevesu. Če je vrednost trenutnega vozlišča enaka iskani vrednosti, se vrne vozlišče. V nasprotnem primeru se na podlagi vrednosti išče levo ali desno poddrevo in postopek se ponavlja, dokler se vrednost ne najde ali ni doseženo ničelno vozlišče.

Primeri implementacije binarnih dreves v C

Zdaj, ko smo obravnavali osnove binarnih dreves in kako jih implementirati v C, si poglejmo nekaj praktičnih primerov.

Primer 1: Ustvarjanje binarnega drevesa

Recimo, da želimo ustvariti binarno drevo z naslednjimi vrednostmi: 10, 5, 15, 3, 7, 13, 18. Evo, kako lahko to naredimo v 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;
}

V tem primeru ustvarimo kazalec na koren drevesa in nato uporabimo funkcijo insertarNodo da dodate vrednosti v drevo.

Primer 2: Prehod binarnega drevesa po vrstnem redu

Če želite natisniti vrednosti binarnega drevesa po vrstnem redu, lahko pokličemo funkcijo inOrden kot sledi:

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

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

    return 0;
}

Ta primer bo natisnil vrednosti v drevesu v naraščajočem vrstnem redu.

Pogosto zastavljena vprašanja

1. Kakšna je razlika med binarnim drevesom in binarnim iskalnim drevesom?

Binarno iskalno drevo (BST) je posebna vrsta binarnega drevesa, v katerem so elementi razporejeni tako, da so manjše vrednosti na levi in ​​večje vrednosti na desni. To omogoča učinkovitejše iskanje elementov v primerjavi z običajnim binarnim drevesom.

2. Ali lahko imam vozlišča s podvojenimi vrednostmi v binarnem drevesu?

Da, možno je imeti vozlišča s podvojenimi vrednostmi v binarnem drevesu. Vendar pa lahko glede na izvedbo in posebna pravila binarnega drevesa obstajajo različni načini obravnavanja podvojenih vozlišč. Nekatere izvedbe lahko dovolijo dvojnike in jih shranijo v poljubnem vrstnem redu, druge pa lahko zahtevajo, da se podvojene vrednosti obravnavajo posebej ali zavržejo.

3. Kako lahko odstranim določeno vozlišče iz binarnega drevesa?

Če želite odstraniti določeno vozlišče iz binarnega drevesa, morate slediti tem korakom:

1. Z iskanjem po drevesu poiščite vozlišče, ki ga želite izbrisati.
2. Razmislite o različnih primerih izločanja:
   • Če vozlišče nima otrok, ga lahko preprosto izbrišete in sprostite njegov pomnilnik.
   • Če ima vozlišče samo enega podrejenega, ga lahko zamenjate z njegovim podrejenim.
   • Če ima vozlišče dva otroka, morate najti najbližjega naslednika (najmanjše vozlišče v desnem poddrevesu) in nadomestiti vrednost vozlišča, ki ga želite izbrisati, z vrednostjo naslednika. Nato odstranite naslednika iz drevesa.
3. Po potrebi prilagodi povezave in kazalce za vzdrževanje pravilne drevesne strukture.

4. Kaj je polno binarno drevo?

Polno binarno drevo je posebna vrsta binarnega drevesa, v katerem so vsi nivoji, razen morda zadnjega, v celoti zapolnjeni, vozlišča zadnjega nivoja pa se nahajajo čim bolj levo. To pomeni, da imajo vsa vozlišča dva otroka, razen morebiti vozlišča na zadnji ravni, ki imajo lahko enega ali nobenega otroka.

5. Kakšna je višina binarnega drevesa?

Višina binarnega drevesa je dolžina najdaljše poti od korenine do lista. Z drugimi besedami, to je največje število robov med korenino in katerim koli listom v drevesu. Višina se meri glede na število ravni, tako da ima drevo z enim vozliščem višino 0, prazno drevo pa nima višine.

6. Kdaj naj v svojih programih uporabim binarno drevo?

Binarna drevesa so uporabna v različnih situacijah. Nekateri pogosti primeri, ko lahko uporabite binarna drevesa, vključujejo:

• Učinkovito iskanje elementov: Če morate hitro poiskati elemente v podatkovni strukturi, lahko binarno drevo zagotovi učinkovit dostop do podatkov.
• Predstavljanje hierarhičnih odnosov: Binarna drevesa so idealna za predstavljanje hierarhičnih odnosov, kot je struktura imenika v datotečni sistem.
• Razvrščanje podatkov: z binarnimi iskalnimi drevesi lahko učinkovito razvrščate podatke in izvajate iskanja, vstavljanja in brisanja v logaritemskem času.

Ne pozabite oceniti svojih zahtev in razmisliti o kompleksnosti operacij na binarnih drevesih, preden se odločite za njihovo uporabo v svojih programih.

Zaključek

V tem obsežnem vodniku smo raziskali temeljne koncepte binarnih dreves v C. Spoznali smo njihovo strukturo, kako vstaviti in odstraniti vozlišča, izvajati prehode in iskati elemente v binarnem drevesu.

Upamo, da ste s tem vodnikom dobro razumeli binarna drevesa in kako jih implementirati v C. Binarna drevesa so vsestranske in zmogljive podatkovne strukture, ki vam lahko pomagajo pri reševanju številnih težav pri programiranju.

Ne pozabite vaditi in eksperimentirati s ponujenimi primeri, da okrepite svoje razumevanje binarnih dreves v C. Vso srečo na vaši poti učenja in razvoja programske opreme!