Binárne stromy v C: Kompletná príručka pre začiatočníkov

Informatec Digital » Algoritmy » Binárne stromy v jazyku C: Kompletný sprievodca pre začiatočníkov

Vitajte v tejto komplexnej príručke o binárnych stromoch v jazyku C. V tomto článku preskúmame základy binárnych stromov a spôsob ich implementácie v programovacom jazyku C Ak ste začiatočník v programovaní alebo si len chcete zlepšiť svoje zručnosti v jazyku C, táto príručka je určená práve vám.

Binárne stromy sú základné dátové štruktúry v informatike a používajú sa v širokej škále aplikácií. Pochopenie toho, ako fungujú a ako ich implementovať, vám pomôže riešiť zložité problémy efektívnejšie a elegantnejšie.

V tomto článku preskúmame základy binárnych stromov vrátane ich štruktúry, vkladania a mazania uzlov, prechádzania a vyhľadávania prvkov. Uvedieme tiež praktické príklady v programovacom jazyku C , aby ste videli, ako sa tieto koncepty uplatňujú v praxi.

Tak poďme na to!

Čo sú binárne stromy?

Binárne stromy sú hierarchické dátové štruktúry zložené zo vzájomne prepojených uzlov. Každý uzol môže mať až dva podradené uzly: jeden vľavo a jeden vpravo. Táto dvojvetvová štruktúra je to, čo odlišuje binárne stromy od iných dátových štruktúr.

V binárnom strome sa prvý uzol nazýva koreňový uzol. Podradené uzly sa nazývajú podradené uzly a uzly bez potomkov sa nazývajú listové uzly. Uzly na rovnakej úrovni sa nazývajú súrodenecké uzly.

Výhody binárnych stromov

Binárne stromy ponúkajú niekoľko výhod z hľadiska efektívneho ukladania a vyhľadávania údajov. Niektoré z kľúčových výhod zahŕňajú:

1. Efektívne vyhľadávanieBinárne stromy umožňujú prehľadávanie prvkov za behu rýchlejšie ako iné dátové štruktúry, ako napríklad prepojené zoznamy. Je to spôsobené hierarchickou štruktúrou stromu a jeho schopnosťou rýchlo rozdeliť súbor údajov.
2. Flexibilné vkladanie a vyberanieBinárne stromy sú vysoko adaptabilné na operácie vkladania a odstraňovania uzlov. Na rozdiel od statických dátových štruktúr, ako sú polia, môžu binárne stromy rásť a dynamicky meniť svoju štruktúru.
3. Znázornenie hierarchických vzťahovBinárne stromy sú užitočné najmä na reprezentáciu hierarchických vzťahov medzi prvkami. Napríklad v štruktúre súborových adresárov môže byť každý adresár reprezentovaný ako uzol v strome s podadresármi a súbormi ako jeho dcérskymi uzlami.

Štruktúra binárneho stromu

Predtým, ako sa ponoríme do implementácie binárnych stromov v C, je dôležité pochopiť ich základnú štruktúru. Každý uzol v binárnom strome obsahuje hodnotu a odkazy na jeho ľavý a pravý podriadený uzol, ak nejaké má.

Nasledujúca tabuľka zobrazuje štruktúru uzla v binárnom strome:

Binárny uzol
chrabrosť
Ľavý uzol
Pravý uzol

Každý uzol môže uchovávať akýkoľvek typ údajov, ako sú celé čísla, znaky alebo zložitejšie štruktúry. Koreňový uzol je počiatočným bodom stromu a z neho môžeme pristupovať ku všetkým ostatným uzlom.

Implementácia binárnych stromov v C

Teraz, keď máme základné znalosti o binárnych stromoch, je čas implementovať ich v programovacom jazyku C. Ďalej si ukážeme, ako deklarovať a používať štruktúru binárneho stromu v jazyku C.

Deklarácia binárnej stromovej štruktúry

V C môžeme deklarovať štruktúru binárneho stromu pomocou štruktúry a ukazovateľov. Tu je základná deklarácia štruktúry:

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

V tejto štruktúre valor predstavuje hodnotu uloženú v uzle a izquierdo y derecho sú ukazovatele na ľavý a pravý podriadený uzol.

Vytvorenie nového uzla

Aby sme vytvorili nový uzol v binárnom strome, musíme uzlu alokovať pamäť a nastaviť jeho hodnoty. Tu je funkcia C, ktorá vytvorí nový uzol:

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

Funkcia malloc Používa sa na pridelenie dynamickej pamäte uzlu. Potom nastavíme hodnoty uzla a vrátime vytvorený uzol.

Vkladanie uzlov

Vkladanie uzlov je základným procesom v binárnych stromoch. Umožňuje pridať nové prvky do stromu na správnu pozíciu na základe hodnoty uzla. Nižšie je funkcia C na vloženie uzla do binárneho stromu:

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

Táto funkcia dostane ukazovateľ na koreň stromu a hodnotu uzla, ktorý sa má vložiť. Ak je root null, znamená to, že strom je prázdny a v koreni vytvoríme nový uzol. V opačnom prípade porovnáme hodnotu uzla s hodnotou koreňa a rozhodneme sa, či uzol vložíme doľava alebo doprava.

Odstránenie uzlov

Odstránenie uzlov v binárnom strome môže byť o niečo zložitejšie. Závisí to od niekoľkých prípadov, napríklad či uzol, ktorý sa má odstrániť, má deti alebo nie. Nižšie je uvedená funkcia C na odstránenie uzla v binárnom strome:

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 tejto funkcii kontrolujeme, či je hodnota uzla menšia, väčšia alebo rovná hodnote aktuálneho koreňa. V závislosti od prípadu vykonávame nasledujúce akcie:

• Ak je hodnota menšia, ideme naľavo od stromu.
• Ak je hodnota väčšia, ideme napravo od stromu.
• Ak je hodnota rovnaká, nájdeme najbližšieho nasledovníka uzla (najmenší uzol v pravom podstrome) a nahradíme ho aktuálnym uzlom. Potom odstránime následníka z pravého podstromu.

Prechody v binárnych stromoch

Traverzály sú operácie, ktoré nám umožňujú navštíviť všetky uzly binárneho stromu v určitom poradí. Existujú tri bežné typy zájazdov:

Prechod v poradí : Najprv navštívi ľavý podstrom, potom aktuálny uzol a nakoniec pravý podstrom. Tu je funkcia v jazyku C, ktorá vykonáva prechod binárneho stromu v poradí:

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

Prechod v predstihu : Najprv navštívi aktuálny uzol, potom ľavý podstrom a nakoniec pravý podstrom. Tu je funkcia v jazyku C, ktorá vykonáva prechod v predstihu binárneho stromu:

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

Prechod po poradí : Najprv navštívi ľavý podstrom, potom pravý podstrom a nakoniec aktuálny uzol. Tu je funkcia v jazyku C, ktorá vykonáva prechod binárneho stromu po poradí:

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

Hľadajte prvky

Vyhľadávanie prvkov v binárnom strome nám umožňuje rýchlo nájsť konkrétnu hodnotu v rámci dátovej štruktúry. Tu je funkcia C na vyhľadanie prvku v binárnom strome:

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

Táto funkcia vykonáva rekurzívne vyhľadávanie v binárnom strome. Ak sa hodnota aktuálneho uzla rovná hľadanej hodnote, uzol sa vráti. V opačnom prípade sa vyhľadáva ľavý alebo pravý podstrom na základe hodnoty a proces sa opakuje, kým sa nenájde hodnota alebo sa nedosiahne nulový uzol.

Príklady implementácie binárnych stromov v C

Teraz, keď sme prebrali základy binárnych stromov a ako ich implementovať v C, pozrime sa na niekoľko praktických príkladov.

Príklad 1: Vytvorenie binárneho stromu

Predpokladajme, že chceme vytvoriť binárny strom s nasledujúcimi hodnotami: 10, 5, 15, 3, 7, 13, 18. Takto to môžeme urobiť 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 tomto príklade vytvoríme ukazovateľ na koreň stromu a potom použijeme funkciu insertarNodo pridať hodnoty do stromu.

Príklad 2: Priebeh binárneho stromu v poradí

Ak chcete vytlačiť hodnoty binárneho stromu v poradí, môžeme zavolať funkciu inOrden nasledovne:

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

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

    return 0;
}

Tento príklad vytlačí hodnoty v strome vo vzostupnom poradí.

Najčastejšie otázky

1. Aký je rozdiel medzi binárnym stromom a binárnym vyhľadávacím stromom?

Binárny vyhľadávací strom (BST) je špeciálny typ binárneho stromu, v ktorom sú prvky usporiadané tak, že menšie hodnoty sú vľavo a väčšie hodnoty sú vpravo. To umožňuje efektívnejšie vyhľadávanie prvkov v porovnaní s bežným binárnym stromom.

2. Môžem mať uzly s duplicitnými hodnotami v binárnom strome?

Áno, v binárnom strome je možné mať uzly s duplicitnými hodnotami. V závislosti od implementácie a špecifických pravidiel binárneho stromu však môžu existovať rôzne spôsoby riešenia duplicitných uzlov. Niektoré implementácie môžu povoliť duplikáty a ukladať ich v ľubovoľnom poradí, zatiaľ čo iné môžu vyžadovať špeciálne zaobchádzanie s duplicitnými hodnotami alebo ich vyradenie.

3. Ako môžem odstrániť konkrétny uzol z binárneho stromu?

Ak chcete odstrániť konkrétny uzol z binárneho stromu, musíte postupovať podľa týchto krokov:

1. Nájdite uzol, ktorý chcete odstrániť, pomocou stromového vyhľadávania.
2. Zvážte rôzne prípady eliminácie:
   • Ak uzol nemá žiadne potomky, môžete ho jednoducho vymazať a uvoľniť jeho pamäť.
   • Ak má uzol iba jedného potomka, môžete uzol nahradiť jeho potomkom.
   • Ak má uzol dvoch potomkov, musíte nájsť najbližšieho následníka (najmenší uzol v pravom podstrome) a nahradiť hodnotu uzla, ktorý sa má vymazať, hodnotou následníka. Potom odstráňte nástupcu zo stromu.
3. Prispôsobuje odkazy a ukazovatele podľa potreby, aby sa zachovala správna stromová štruktúra.

4. Čo je úplný binárny strom?

Úplný binárny strom je špeciálny typ binárneho stromu, v ktorom sú všetky úrovne, okrem prípadnej poslednej, úplne vyplnené a uzly poslednej úrovne sú umiestnené čo najviac vľavo. To znamená, že všetky uzly majú dvoch potomkov, možno s výnimkou uzlov na poslednej úrovni, ktoré môžu mať jedného alebo žiadneho potomka.

5. Akú výšku má binárny strom?

Výška binárneho stromu je dĺžka najdlhšej cesty od koreňa po list. Inými slovami, je to maximálny počet hrán medzi koreňom a akýmkoľvek listom v strome. Výška sa meria počtom úrovní, takže strom s iba jedným uzlom má výšku 0 a prázdny strom nemá výšku.

6. Kedy by som mal vo svojich programoch použiť binárny strom?

Binárne stromy sú užitočné v rôznych situáciách. Niektoré bežné prípady, kedy by ste mohli použiť binárne stromy, zahŕňajú:

• Efektívne vyhľadávanie prvkov: Ak potrebujete rýchlo vyhľadať prvky v dátovej štruktúre, binárny strom môže poskytnúť efektívny prístup k údajom.
• Reprezentácia hierarchických vzťahov: Binárne stromy sú ideálne na reprezentáciu hierarchických vzťahov, ako je napríklad štruktúra adresára v súborový systém.
• Triedenie údajov: Môžete použiť binárne vyhľadávacie stromy na efektívne triedenie údajov a vyhľadávanie, vkladanie a mazanie v logaritmickom čase.

Nezabudnite zhodnotiť svoje požiadavky a zvážiť zložitosť operácií s binárnymi stromami predtým, ako sa ich rozhodnete použiť vo svojich programoch.

Záver

V tejto komplexnej príručke sme preskúmali základné koncepty binárnych stromov v jazyku C. Dozvedeli sme sa o ich štruktúre, ako vkladať a odstraňovať uzly, vykonávať prechody a hľadať prvky v binárnom strome.

Dúfame, že vám táto príručka poskytla solídne pochopenie binárnych stromov a ich implementácie v jazyku C. Binárne stromy sú všestranné a výkonné dátové štruktúry, ktoré vám môžu pomôcť vyriešiť širokú škálu problémov v programovaní.

Nezabudnite si precvičiť a experimentovať s poskytnutými príkladmi, aby ste posilnili svoje chápanie binárnych stromov v jazyku C. Veľa šťastia na vašej ceste učenia sa a vývoja softvéru!