Binārie koki C: pilnīga rokasgrāmata iesācējiem

Informatec Digital » Algoritmi » Binārie koki C: pilnīga rokasgrāmata iesācējiem

Laipni lūdzam šajā visaptverošajā rokasgrāmatā par binārajiem kokiem C valodā. Šajā rakstā mēs izpētīsim bināro koku pamatus un to, kā tos ieviest C programmēšanas valodā. Ja esat iesācējs programmēšanas jomā vai vienkārši vēlaties uzlabot savas C prasmes, šī rokasgrāmata ir paredzēta jums.

Binārie koki ir fundamentālas datu struktūras datorzinātnēs un tiek izmantoti plašā lietojumprogrammu klāstā. Izpratne par to darbību un ieviešanu palīdzēs jums efektīvāk un elegantāk risināt sarežģītas problēmas.

Šajā rakstā mēs izpētīsim bināro koku pamatus, tostarp to struktūru, mezglu ievietošanu un dzēšanu, šķērsošanu un elementu meklēšanu. Mēs arī sniegsim praktiskus piemērus C programmēšanas valodā , lai jūs varētu redzēt, kā šie jēdzieni tiek pielietoti praksē.

Tātad sāksim!

Kas ir binārie koki?

Binārie koki ir hierarhiskas datu struktūras, kas sastāv no savstarpēji savienotiem mezgliem. Katram mezglam var būt ne vairāk kā divi pakārtotie mezgli: viens kreisajā un otrs labajā pusē. Šī divu zaru struktūra atšķir bināros kokus no citām datu struktūrām.

Binārajā kokā pirmo mezglu sauc par saknes mezglu. Bērnu mezglus sauc par bērnu mezgliem, un mezglus bez bērniem sauc par lapu mezgliem. Vienā līmenī esošos mezglus sauc par brāļu un māsu mezgliem.

Bināro koku priekšrocības

Binārie koki piedāvā vairākas priekšrocības efektīvas datu uzglabāšanas un meklēšanas ziņā. Dažas no galvenajām priekšrocībām ietver:

1. Efektīva meklēšanaBinārie koki nodrošina elementu meklēšanu izpildlaikā ātrāk nekā citās datu struktūrās, piemēram, saistītajos sarakstos. Tas ir saistīts ar koka hierarhisko struktūru un spēju ātri sadalīt datu kopu.
2. Elastīga ievietošana un noņemšanaBinārie koki ir ļoti pielāgojami mezglu ievietošanas un dzēšanas darbībām. Atšķirībā no statiskām datu struktūrām, piemēram, masīviem, binārie koki var augt un dinamiski mainīt savu struktūru.
3. Hierarhisko attiecību attēlojumsBinārie koki ir īpaši noderīgi, lai attēlotu hierarhiskas attiecības starp elementiem. Piemēram, failu direktoriju struktūrā katru direktoriju var attēlot kā mezglu kokā, bet apakšdirektorijus un failus kā tā atvasinātos mezglus.

Binārā koka struktūra

Pirms ienirt bināro koku ieviešanā C, ir svarīgi saprast to pamatstruktūru. Katrs binārā koka mezgls satur vērtību un atsauces uz tā kreiso un labo pakārtotajiem mezgliem, ja tādi ir.

Šajā tabulā ir parādīta binārā koka mezgla struktūra:

Binārais mezgls
varonība
Kreisais mezgls
Labais mezgls

Katrs mezgls var uzglabāt jebkura veida datus, piemēram, veselus skaitļus, rakstzīmes vai sarežģītākas struktūras. Saknes mezgls ir koka sākuma punkts, un no tā mēs varam piekļūt visiem pārējiem mezgliem.

Bināro koku ieviešana C

Tagad, kad mums ir pamatzināšanas par binārajiem kokiem, ir pienācis laiks tos ieviest C programmēšanas valodā . Tālāk mēs redzēsim, kā deklarēt un izmantot binārā koka struktūru C valodā.

Binārā koka struktūras deklarēšana

Programmā C mēs varam deklarēt binārā koka struktūru, izmantojot struktūru un norādes. Šeit ir struktūras pamata deklarācija:

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

Šajā struktūrā valor apzīmē mezglā saglabāto vērtību un izquierdo y derecho ir attiecīgi norādes uz kreiso un labo pakārtotajiem mezgliem.

Jauna mezgla izveide

Lai izveidotu jaunu mezglu binārajā kokā, mums ir jāpiešķir atmiņa mezglam un jāiestata tā vērtības. Šeit ir C funkcija, kas izveido jaunu mezglu:

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 To izmanto, lai mezglam piešķirtu dinamisko atmiņu. Pēc tam mēs iestatām mezgla vērtības un atgriežam izveidoto mezglu.

Mezglu ievietošana

Mezglu ievietošana ir būtisks process binārajos kokos. Ļauj pievienot kokam jaunus elementus pareizajā pozīcijā, pamatojoties uz mezgla vērtību. Zemāk ir C funkcija, lai ievietotu mezglu binārajā kokā:

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

Šī funkcija saņem rādītāju uz koka sakni un ievietojamā mezgla vērtību. Ja saknes vērtība ir nulle, tas nozīmē, ka koks ir tukšs, un mēs izveidojam jaunu mezglu saknē. Pretējā gadījumā mēs salīdzinām mezgla vērtību ar saknes vērtību un izlemjam, vai ievietot mezglu pa kreisi vai pa labi.

Notiek mezglu dzēšana

Mezglu dzēšana binārajā kokā var būt nedaudz sarežģītāka. Tas ir atkarīgs no vairākiem gadījumiem, piemēram, vai dzēšamajam mezglam ir bērni vai nav. Zemāk ir C funkcija, lai dzēstu mezglu binārajā kokā:

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

Šajā funkcijā mēs pārbaudām, vai mezgla vērtība ir mazāka, lielāka vai vienāda ar pašreizējās saknes vērtību. Atkarībā no gadījuma mēs veicam šādas darbības:

• Ja vērtība ir mazāka, mēs ejam pa kreisi no koka.
• Ja vērtība ir lielāka, mēs ejam pa labi no koka.
• Ja vērtība ir vienāda, mēs atrodam mezgla tuvāko pēcteci (mazāko mezglu labajā apakškokā) un aizstājam to ar pašreizējo mezglu. Tad mēs noņemam pēcteci no labā apakškoka.

Pārbraucieni bināros kokos

Traverāles ir darbības, kas ļauj mums noteiktā secībā apmeklēt visus binārā koka mezglus. Ir trīs izplatīti ekskursiju veidi:

Šķērsošana konsekventā secībā : Vispirms apmeklē kreiso apakškoku, tad pašreizējo mezglu un visbeidzot labo apakškoku. Šeit ir C funkcija, kas veic binārā koka šķērsošanu konsekventā secībā:

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

Šķērsošana pirms pasūtījuma : Vispirms apmeklē pašreizējo mezglu, tad kreiso apakškoku un visbeidzot labo apakškoku. Šeit ir C funkcija, kas veic binārā koka šķērsošanu pirms pasūtījuma:

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

Pēcpasūtījuma šķērsošana : Vispirms apmeklē kreiso apakškoku, tad labo apakškoku un visbeidzot pašreizējo mezglu. Šeit ir C funkcija, kas veic binārā koka šķērsošanu pēc pasūtīšanas:

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

Meklējiet elementus

Elementu meklēšana binārajā kokā ļauj ātri atrast konkrētu vērtību datu struktūrā. Šeit ir C funkcija, lai meklētu elementu binārā kokā:

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

Šī funkcija veic rekursīvu meklēšanu binārajā kokā. Ja pašreizējā mezgla vērtība ir vienāda ar meklēto vērtību, mezgls tiek atgriezts. Pretējā gadījumā tiek meklēts kreisais vai labais apakškoks, pamatojoties uz vērtību, un process tiek atkārtots, līdz tiek atrasta vērtība vai sasniegts nulles mezgls.

Bināro koku ieviešanas piemēri C

Tagad, kad esam apskatījuši bināro koku pamatus un to, kā tos ieviest programmā C, apskatīsim dažus praktiskus piemērus.

1. piemērs: Binārā koka izveide

Pieņemsim, ka mēs vēlamies izveidot bināro koku ar šādām vērtībām: 10, 5, 15, 3, 7, 13, 18. Lūk, kā mēs to varam izdarīt C valodā:

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

Šajā piemērā mēs izveidojam rādītāju uz koka sakni un pēc tam izmantojam funkciju insertarNodo lai pievienotu vērtības kokam.

2. piemērs. Binārā koka šķērsošana secībā

Lai izdrukātu binārā koka vērtības secībā, mēs varam izsaukt funkciju inOrden šādi:

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

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

    return 0;
}

Šajā piemērā vērtības kokā tiks drukātas augošā secībā.

Bieži uzdotie jautājumi

1. Kāda ir atšķirība starp bināro koku un bināro meklēšanas koku?

Binārais meklēšanas koks (BST) ir īpašs binārā koka veids, kurā elementi ir sakārtoti tā, lai mazākas vērtības būtu kreisajā pusē, bet lielākas - labajā pusē. Tas ļauj efektīvāk meklēt elementus, salīdzinot ar parastu bināro koku.

2. Vai binārajā kokā var būt mezgli ar dublētām vērtībām?

Jā, binārajā kokā var būt mezgli ar dublētām vērtībām. Tomēr atkarībā no ieviešanas un īpašajiem binārā koka noteikumiem var būt dažādi veidi, kā rīkoties ar dublētiem mezgliem. Dažas ieviešanas var atļaut dublikātus un saglabāt tos jebkurā secībā, savukārt citas var pieprasīt, lai dublikātu vērtības tiktu īpaši apstrādātas vai izmestas.

3. Kā es varu noņemt noteiktu mezglu no binārā koka?

Lai noņemtu noteiktu mezglu no binārā koka, jums ir jāveic šādas darbības:

1. Atrodiet mezglu, kuru vēlaties dzēst, izmantojot meklēšanu kokā.
2. Apsveriet dažādus likvidēšanas gadījumus:
   • Ja mezglam nav bērnu, varat to vienkārši izdzēst un atbrīvot tā atmiņu.
   • Ja mezglam ir tikai viens bērns, mezglu var aizstāt ar tā bērnu.
   • Ja mezglam ir divi bērni, jums ir jāatrod tuvākais pēctecis (mazākais mezgls labajā apakškokā) un jāaizstāj dzēšamā mezgla vērtība ar pēcteča vērtību. Pēc tam noņemiet pēcteci no koka.
3. Pielāgo saites un norādes pēc vajadzības, lai uzturētu pareizo koka struktūru.

4. Kas ir pilns binārais koks?

Pilns binārais koks ir īpašs binārā koka veids, kurā visi līmeņi, izņemot, iespējams, pēdējo, ir pilnībā aizpildīti, un pēdējā līmeņa mezgli atrodas pēc iespējas tālāk pa kreisi. Tas nozīmē, ka visiem mezgliem ir divi bērni, izņemot, iespējams, pēdējā līmeņa mezglus, kuriem var būt viens vai bez bērniem.

5. Kāds ir binārā koka augstums?

Binārā koka augstums ir garākā ceļa garums no saknes līdz lapai. Citiem vārdiem sakot, tas ir maksimālais malu skaits starp sakni un jebkuru lapu kokā. Augstumu mēra līmeņu skaita izteiksmē, tāpēc kokam ar tikai vienu mezglu augstums ir 0, bet tukšam kokam augstuma nav.

6. Kad manās programmās vajadzētu izmantot bināro koku?

Binārie koki ir noderīgi dažādās situācijās. Daži izplatīti gadījumi, kad varat izmantot bināros kokus, ir šādi:

• Efektīva elementu meklēšana: ja nepieciešams ātri meklēt elementus datu struktūrā, binārais koks var nodrošināt efektīvu piekļuvi datiem.
• Hierarhisku attiecību attēlošana: binārie koki ir ideāli piemēroti, lai attēlotu hierarhiskas attiecības, piemēram, direktoriju struktūru failu sistēma.
• Datu kārtošana: varat izmantot bināros meklēšanas kokus, lai efektīvi kārtotu datus un veiktu meklēšanu, ievietošanu un dzēšanu logaritmiskā laikā.

Neaizmirstiet novērtēt savas prasības un apsveriet operāciju sarežģītību ar binārajiem kokiem, pirms izlemjat tos izmantot savās programmās.

Secinājums

Šajā visaptverošajā rokasgrāmatā mēs esam izpētījuši bināro koku pamatjēdzienus valodā C. Mēs esam uzzinājuši par to struktūru, kā ievietot un noņemt mezglus, veikt pārvietošanos un meklēt elementus binārajā kokā.

Mēs ceram, ka šī rokasgrāmata ir devusi jums pamatīgu izpratni par binārajiem kokiem un to ieviešanu programmā C. Binārie koki ir daudzpusīgas un jaudīgas datu struktūras, kas var palīdzēt atrisināt dažādas programmēšanas problēmas.

Neaizmirstiet praktizēt un eksperimentēt ar sniegtajiem piemēriem, lai stiprinātu izpratni par binārajiem kokiem programmā C. Veiksmi programmatūras apguves un izstrādes ceļojumā!