Binaarsed puud C-s: täielik juhend algajatele

Informatec Digital » Algoritmid » Binaarpuud C-keeles: täielik juhend algajatele

Tere tulemast sellesse põhjalikusse C-keelse binaarpuude juhendisse. Selles artiklis uurime binaarpuude põhitõdesid ja seda, kuidas neid C-programmeerimiskeeles rakendada.

Binaarpuud on arvutiteaduse põhilised andmestruktuurid ja neid kasutatakse paljudes rakendustes. Nende toimimise ja rakendamise mõistmine aitab teil keerulisi probleeme tõhusamalt ja elegantsemalt lahendada.

Selles artiklis uurime binaarpuude põhitõdesid, sealhulgas nende struktuuri, sõlmede lisamist ja kustutamist, läbimist ja elementide otsingut. Samuti pakume praktilisi näiteid C -programmeerimiskeeles, et näeksite, kuidas neid kontseptsioone praktikas rakendatakse.

Nii et alustame!

Mis on kahendpuud?

Binaarsed puud on omavahel ühendatud sõlmedest koosnevad hierarhilised andmestruktuurid. Igal sõlmel võib olla kuni kaks alamsõlme: üks vasakul ja teine ​​paremal. See kaheharuline struktuur eristab binaarpuid teistest andmestruktuuridest.

Binaarses puus nimetatakse esimest sõlme juursõlmeks. Lapssõlmedeks nimetatakse lapssõlmedeks ja ilma lasteta sõlmedeks lehesõlmedeks. Samal tasemel asuvaid sõlme nimetatakse vendsõlmedeks.

Binaarsete puude eelised

Binaarsed puud pakuvad tõhusa andmete salvestamise ja otsimise osas mitmeid eeliseid. Mõned peamised eelised hõlmavad järgmist:

1. Tõhus otsingBinaarpuud võimaldavad elemente käitamise ajal otsida kiiremini kui muud andmestruktuurid, näiteks lingitud loendid. See on tingitud puu hierarhilisest struktuurist ja selle võimest andmekogum kiiresti jaotada.
2. Paindlik sisestamine ja eemaldamineBinaarsed puud on sõlmede sisestamise ja kustutamise toimingute jaoks väga kohandatavad. Erinevalt staatilistest andmestruktuuridest, nagu massiivid, võivad binaarsed puud kasvada ja oma struktuuri dünaamiliselt muuta.
3. Hierarhiliste suhete kujutamineBinaarsed puud on eriti kasulikud elementidevaheliste hierarhiliste suhete kujutamiseks. Näiteks failikataloogi struktuuris saab iga kataloogi esitada puu sõlmena, alamkataloogid ja failid on selle alamsõlmed.

Binaarse puu struktuur

Enne kahendpuude juurutamist C-s on oluline mõista nende põhistruktuuri. Iga binaarpuu sõlm sisaldab väärtust ja viiteid selle vasak- ja parempoolsele alamsõlmele, kui see on olemas.

Järgmine tabel näitab kahendpuu sõlme struktuuri:

Binaarne sõlm
vaprus
Vasak sõlm
Parem sõlm

Iga sõlm võib salvestada mis tahes tüüpi andmeid, näiteks täisarve, märke või keerukamaid struktuure. Juursõlm on puu alguspunkt ja sealt pääseme ligi kõikidele teistele sõlmedele.

Binaarsete puude rakendamine C-s

Nüüd, kui meil on binaarpuude põhiteadmised, on aeg need C-programmeerimiskeeles rakendada . Järgmisena vaatame, kuidas C-keeles binaarpuu struktuuri deklareerida ja kasutada.

Binaarse puustruktuuri deklareerimine

C-s saame binaarpuu struktuuri deklareerida, kasutades struktuuri ja viiteid. Siin on struktuuri põhideklaratsioon:

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

Selles struktuuris valor tähistab sõlme salvestatud väärtust ja izquierdo y derecho on osutajad vastavalt vasakule ja paremale alamsõlmele.

Uue sõlme loomine

Binaarpuus uue sõlme loomiseks peame eraldama sõlmele mälu ja määrama selle väärtused. Siin on C-funktsioon, mis loob uue sõlme:

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

Funktsioon malloc Seda kasutatakse dünaamilise mälu eraldamiseks sõlmele. Seejärel määrame sõlme väärtused ja tagastame loodud sõlme.

Sõlmede sisestamine

Sõlmede sisestamine on kahendpuude põhiprotsess. Võimaldab lisada puule uusi elemente õiges kohas sõlme väärtuse alusel. Allpool on C-funktsioon sõlme lisamiseks binaarpuusse:

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

See funktsioon võtab vastu viida puu juurele ja sisestatava sõlme väärtusele. Kui juur on null, tähendab see, et puu on tühi ja me loome juure uue sõlme. Vastasel juhul võrdleme sõlme väärtust juurväärtusega ja otsustame, kas sisestada sõlm vasakule või paremale.

Sõlmede kustutamine

Sõlmede kustutamine binaarpuust võib olla veidi keerulisem. See sõltub mitmest juhtumist, näiteks sellest, kas kustutataval sõlmel on lapsed või mitte. Allpool on C-funktsioon binaarpuu sõlme kustutamiseks:

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

Selles funktsioonis kontrollime, kas sõlme väärtus on väiksem, suurem või võrdne praeguse juure väärtusega. Olenevalt juhtumist teostame järgmisi toiminguid:

• Kui väärtus on väiksem, läheme puust vasakule.
• Kui väärtus on suurem, läheme puust paremale.
• Kui väärtus on võrdne, leiame sõlme lähima järglase (parempoolse alampuu väikseima sõlme) ja asendame selle praeguse sõlmega. Seejärel eemaldame parempoolsest alampuust järglase.

Ringkäigud kahendpuudel

Läbimised on toimingud, mis võimaldavad külastada binaarpuu kõiki sõlme teatud järjekorras. Levinud on kolm tüüpi ekskursioone:

Järjekorras läbimine : külastab esmalt vasakpoolset alampuud, seejärel praegust sõlme ja lõpuks paremat alampuud. Siin on C-funktsioon, mis teostab binaarpuu järjestikuse läbimise:

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

Eeltellimisel läbimine : külastab esmalt praegust sõlme, seejärel vasakpoolset alampuud ja lõpuks paremat alampuud. Siin on C-funktsioon, mis teostab binaarpuu eeltellimisel läbimise:

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

Järeljärjestuse läbimine : külastab esmalt vasakpoolset alampuud, seejärel paremat alampuud ja lõpuks praegust sõlme. Siin on C-funktsioon, mis teostab binaarpuu järeljärjestuse läbimise:

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

Otsige elemente

Elementide otsimine binaarpuust võimaldab meil kiiresti leida andmestruktuurist konkreetse väärtuse. Siin on funktsioon C elemendi otsimiseks binaarpuust:

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

See funktsioon teostab binaarpuus rekursiivse otsingu. Kui praeguse sõlme väärtus on võrdne otsitava väärtusega, tagastatakse sõlm. Vastasel juhul otsitakse väärtuse alusel vasakut või paremat alampuud ja protsessi korratakse, kuni väärtus leitakse või jõutakse nullsõlme.

Näited kahendpuude rakendamisest C-s

Nüüd, kui oleme käsitlenud kahendpuude põhitõdesid ja nende rakendamist C-s, vaatame mõnda praktilist näidet.

Näide 1: binaarpuu loomine

Oletame, et tahame luua binaarpuu järgmiste väärtustega: 10, 5, 15, 3, 7, 13, 18. C-s saame seda teha järgmiselt:

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

Selles näites loome kursori puu juure ja seejärel kasutame funktsiooni insertarNodo puule väärtuste lisamiseks.

Näide 2: binaarpuu läbimine järjekorras

Binaarse puu väärtuste järjekorras printimiseks saame funktsiooni kutsuda inOrden järgnevalt:

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

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

    return 0;
}

See näide prindib puu väärtused kasvavas järjekorras.

Preguntas frecuentes

1. Mis vahe on kahendpuul ja binaarsel otsingupuul?

Binaarne otsingupuu (BST) on kahendpuu eritüüp, milles elemendid on paigutatud nii, et väiksemad väärtused on vasakul ja suuremad paremal. See võimaldab elementide tõhusamat otsimist võrreldes tavalise kahendpuuga.

2. Kas binaarpuus võib olla topeltväärtustega sõlmi?

Jah, binaarpuus võib olla topeltväärtustega sõlme. Olenevalt binaarpuu rakendamisest ja konkreetsetest reeglitest võib aga dubleerivate sõlmedega toime tulla erinevaid viise. Mõned rakendused võivad lubada duplikaate ja neid suvalises järjekorras salvestada, samas kui teised võivad nõuda, et duplikaatväärtusi käsitletaks spetsiaalselt või neist loobutaks.

3. Kuidas ma saan binaarpuust konkreetse sõlme eemaldada?

Konkreetse sõlme eemaldamiseks binaarpuust peate järgima neid samme.

1. Otsige puuotsingu abil üles sõlm, mille soovite kustutada.
2. Mõelge erinevatele kõrvaldamisjuhtumitele:
   • Kui sõlmel pole lapsi, saate selle lihtsalt kustutada ja selle mälu vabastada.
   • Kui sõlmel on ainult üks alam, saate sõlme asendada selle lapsega.
   • Kui sõlmel on kaks last, tuleb leida lähim järglane (parempoolse alampuu väikseim sõlm) ja asendada kustutatava sõlme väärtus järglase väärtusega. Seejärel eemaldage järglane puu küljest.
3. Reguleerib linke ja viiteid vastavalt vajadusele, et säilitada õige puu struktuur.

4. Mis on täisbinaarne puu?

Täisbinaarpuu on kahendpuu eritüüp, mille kõik tasemed, välja arvatud võib-olla viimane, on täielikult täidetud ja viimase taseme sõlmed asuvad võimalikult vasakul. See tähendab, et kõigil sõlmedel on kaks last, välja arvatud võib-olla viimase taseme sõlmed, millel võib olla üks või mitte ühtegi last.

5. Mis on kahendpuu kõrgus?

Binaarse puu kõrgus on pikima tee pikkus juurest leheni. Teisisõnu, see on maksimaalne servade arv juure ja puu mis tahes lehe vahel. Kõrgust mõõdetakse tasemete arvu järgi, nii et ainult ühe sõlmega puu kõrgus on 0 ja tühja puu kõrgus puudub.

6. Millal peaksin oma programmides kasutama binaarpuud?

Binaarsed puud on kasulikud erinevates olukordades. Mõned levinumad juhtumid, kus võite kasutada kahendpuid, on järgmised:

• Tõhus elementide otsing: kui teil on vaja kiiresti otsida elemente andmestruktuurist, võib kahendpuu anda andmetele tõhusa juurdepääsu.
• Hierarhiliste suhete esitamine: binaarpuud on ideaalsed hierarhiliste suhete, näiteks kataloogistruktuuri esitamiseks failisüsteem.
• Andmete sortimine: saate kasutada binaarseid otsingupuid andmete tõhusaks sortimiseks ning otsingute, sisestamiste ja kustutamiste tegemiseks logaritmilise aja jooksul.

Ärge unustage hinnata oma nõudeid ja kaaluda kahendpuudega tehtavate toimingute keerukust, enne kui otsustate neid oma programmides kasutada.

Järeldus

Selles põhjalikus juhendis oleme uurinud kahendpuude põhimõisteid C-s. Oleme õppinud tundma nende struktuuri, kuidas sisestada ja eemaldada sõlme, sooritada läbisõite ja otsida kahendpuust elemente.

Loodame, et see juhend on andnud teile põhjaliku ülevaate binaarpuudest ja nende rakendamisest C-s. Binaarsed puud on mitmekülgsed ja võimsad andmestruktuurid, mis aitavad teil lahendada paljusid programmeerimisega seotud probleeme.

Ärge unustage harjutada ja katsetada esitatud näidetega, et tugevdada oma arusaamist binaarpuudest C-s. Edu teile tarkvara õppimise ja arendamise teekonnal!