Binary Trees sa C: Isang Kumpletong Gabay sa Baguhan

Informatec Digital » Mga algorithm » Binary Trees sa C: Isang Kumpletong Gabay sa Baguhan

Maligayang pagdating sa komprehensibong gabay na ito sa mga binary tree sa C. Sa artikulong ito, tutuklasin namin ang mga pangunahing kaalaman ng mga binary tree at kung paano ipatupad ang mga ito sa C programming language Kung ikaw ay isang baguhan sa programming o gusto lang pagbutihin ang iyong mga kasanayan sa C, ang gabay na ito ay para sa iyo.

Ang mga binary tree ay mga pangunahing istruktura ng datos sa agham pangkompyuter at ginagamit sa malawak na hanay ng mga aplikasyon. Ang pag-unawa kung paano sila gumagana at kung paano ipatupad ang mga ito ay makakatulong sa iyo na malutas ang mga kumplikadong problema nang mas mahusay at elegante.

Sa buong artikulong ito, susuriin natin ang mga pangunahing kaalaman sa mga binary tree, kabilang ang kanilang istruktura, paglalagay at pagbura ng node, traversal, at paghahanap ng elemento. Magbibigay din tayo ng mga praktikal na halimbawa sa wikang C programming upang makita mo kung paano inilalapat ang mga konseptong ito sa praktika.

Kaya simulan na natin!

Ano ang mga binary tree?

Ang mga binary tree ay mga hierarchical na istruktura ng data na binubuo ng magkakaugnay na mga node. Ang bawat node ay maaaring magkaroon ng hanggang dalawang child node: isa sa kaliwa at isa sa kanan. Ang istrukturang ito na may dalawang sangay ang siyang nagpapakilala sa mga binary tree mula sa iba pang istruktura ng data.

Sa isang binary tree, ang unang node ay tinatawag na root node. Ang mga child node ay tinatawag na child node, at ang mga node na walang mga bata ay tinatawag na leaf node. Ang mga node sa parehong antas ay tinatawag na mga kapatid na node.

Mga pakinabang ng binary tree

Nag-aalok ang mga binary tree ng ilang mga pakinabang sa mga tuntunin ng mahusay na pag-iimbak at paghahanap ng data. Ang ilan sa mga pangunahing benepisyo ay kinabibilangan ng:

1. Mahusay na paghahanapBinibigyang-daan ng mga binary tree ang mga elemento na maghanap sa runtime nang mas mabilis kaysa sa iba pang istruktura ng data, gaya ng mga naka-link na listahan. Ito ay dahil sa hierarchical na istraktura ng puno at ang kakayahang mabilis na hatiin ang set ng data.
2. Flexible na pagpasok at pagtanggalAng mga binary tree ay lubos na madaling ibagay sa mga operasyon ng pagpasok at pagtanggal ng node. Hindi tulad ng mga static na istruktura ng data tulad ng mga array, ang mga binary tree ay maaaring lumago at baguhin ang kanilang istraktura nang pabago-bago.
3. Representasyon ng mga hierarchical na relasyonAng mga binary tree ay lalong kapaki-pakinabang para sa kumakatawan sa mga hierarchical na relasyon sa pagitan ng mga elemento. Halimbawa, sa isang istraktura ng direktoryo ng file, ang bawat direktoryo ay maaaring katawanin bilang isang node sa puno, na may mga subdirectory at mga file bilang mga child node nito.

Istraktura ng isang binary tree

Bago tayo sumisid sa pagpapatupad ng mga binary tree sa C, mahalagang maunawaan ang kanilang pangunahing istraktura. Ang bawat node sa isang binary tree ay naglalaman ng isang value at mga reference sa kaliwa at kanang child node nito, kung mayroon man.

Ang sumusunod na talahanayan ay nagpapakita ng istraktura ng isang node sa isang binary tree:

Binary node
tapang
Kaliwang node
Kanang node

Ang bawat node ay maaaring mag-imbak ng anumang uri ng data, tulad ng mga integer, character, o mas kumplikadong istruktura. Ang root node ay ang panimulang punto ng puno, at mula dito maaari nating ma-access ang lahat ng iba pang mga node.

Ang pagpapatupad ng mga binary tree sa C

Ngayong mayroon na tayong pangunahing pag-unawa sa mga binary tree, oras na para ipatupad ang mga ito sa C programming language . Susunod, titingnan natin kung paano ideklara at gamitin ang binary tree structure sa C.

Pagdedeklara ng binary tree structure

Sa C, maaari nating ideklara ang istraktura ng isang binary tree gamit ang isang istraktura at mga pointer. Narito ang pangunahing deklarasyon ng istraktura:

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

Sa istrukturang ito, valor kumakatawan sa halagang nakaimbak sa node, at izquierdo y derecho ay mga pointer sa kaliwa at kanang child node, ayon sa pagkakabanggit.

Paglikha ng bagong node

Upang lumikha ng bagong node sa binary tree, kailangan nating maglaan ng memorya para sa node at itakda ang mga halaga nito. Narito ang isang C function na lumilikha ng bagong node:

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

Ang pag-andar malloc Ito ay ginagamit upang maglaan ng dynamic na memorya sa node. Pagkatapos ay itinakda namin ang mga halaga ng node at ibalik ang nilikha na node.

Pagpasok ng mga node

Ang pagpasok ng node ay isang pangunahing proseso sa mga binary tree. Binibigyang-daan kang magdagdag ng mga bagong elemento sa puno sa tamang posisyon batay sa halaga ng node. Nasa ibaba ang isang C function upang magpasok ng isang node sa isang binary tree:

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

Ang function na ito ay tumatanggap ng pointer sa ugat ng puno at ang halaga ng node na ilalagay. Kung null ang ugat, nangangahulugan ito na walang laman ang puno at gumagawa kami ng bagong node sa ugat. Kung hindi, inihahambing namin ang halaga ng node sa halaga ng ugat at magpapasya kung ipasok ang node sa kaliwa o kanan.

Pagtanggal ng mga node

Ang pagtanggal ng mga node sa isang binary tree ay maaaring maging mas kumplikado. Depende ito sa ilang mga kaso, tulad ng kung ang node na tatanggalin ay may mga anak o wala. Nasa ibaba ang isang C function para magtanggal ng node sa isang binary tree:

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

Sa function na ito, sinusuri namin kung ang halaga ng node ay mas mababa sa, mas malaki kaysa, o katumbas ng halaga ng kasalukuyang ugat. Depende sa kaso, isinasagawa namin ang mga sumusunod na aksyon:

• Kung ang halaga ay mas maliit, pumunta kami sa kaliwa ng puno.
• Kung mas malaki ang halaga, pumunta kami sa kanan ng puno.
• Kung pantay ang halaga, makikita natin ang pinakamalapit na kahalili ng node (ang pinakamaliit na node sa kanang subtree) at palitan ito ng kasalukuyang node. Pagkatapos ay tinanggal namin ang kahalili mula sa kanang subtree.

Traversals sa binary puno

Ang mga traversal ay mga operasyon na nagpapahintulot sa amin na bisitahin ang lahat ng mga node ng isang binary tree sa isang tiyak na pagkakasunud-sunod. Mayroong tatlong karaniwang uri ng mga paglilibot:

In-order traversal : Binibisita muna ang kaliwang subtree, pagkatapos ay ang kasalukuyang node, at sa huli ay ang kanang subtree. Narito ang isang C function na nagsasagawa ng in-order traversal ng isang binary tree:

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

Pre-order traversal : Binibisita muna ang kasalukuyang node, pagkatapos ay ang kaliwang subtree, at panghuli ang kanang subtree. Narito ang isang C function na nagsasagawa ng pre-order traversal ng isang binary tree:

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

Post-order traversal : Binibisita muna ang kaliwang subtree, pagkatapos ay ang kanang subtree, at sa huli ay ang kasalukuyang node. Narito ang isang C function na nagsasagawa ng post-order traversal ng isang binary tree:

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

Maghanap ng mga elemento

Ang paghahanap ng mga elemento sa isang binary tree ay nagbibigay-daan sa amin na mabilis na makahanap ng isang partikular na halaga sa loob ng istraktura ng data. Narito ang isang C function upang maghanap ng isang elemento sa isang binary tree:

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

Ang function na ito ay nagsasagawa ng recursive na paghahanap sa binary tree. Kung ang halaga ng kasalukuyang node ay katumbas ng hinanap na halaga, ibabalik ang node. Kung hindi, hahanapin ang kaliwa o kanang subtree batay sa halaga at paulit-ulit ang proseso hanggang matagpuan ang halaga o maabot ang isang null node.

Mga halimbawa ng pagpapatupad ng mga binary tree sa C

Ngayon na nasaklaw na natin ang mga pangunahing kaalaman ng mga binary tree at kung paano ipatupad ang mga ito sa C, tingnan natin ang ilang praktikal na halimbawa.

Halimbawa 1: Paglikha ng binary tree

Ipagpalagay na gusto nating lumikha ng isang binary tree na may mga sumusunod na halaga: 10, 5, 15, 3, 7, 13, 18. Narito kung paano natin ito magagawa sa 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;
}

Sa halimbawang ito, lumikha kami ng isang pointer sa ugat ng puno at pagkatapos ay gamitin ang function insertarNodo upang idagdag ang mga halaga sa puno.

Halimbawa 2: In-order traversal ng binary tree

Upang i-print ang mga halaga ng binary tree sa pagkakasunud-sunod, maaari naming tawagan ang function inOrden tulad ng sumusunod:

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

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

    return 0;
}

Ang halimbawang ito ay magpi-print ng mga halaga sa puno sa pataas na pagkakasunud-sunod.

Mga madalas itanong

1. Ano ang pagkakaiba ng binary tree at binary search tree?

Ang binary search tree (BST) ay isang espesyal na uri ng binary tree kung saan ang mga elemento ay nakaayos upang ang mas maliliit na halaga ay nasa kaliwa at ang mas malalaking halaga ay nasa kanan. Nagbibigay-daan ito para sa mas mahusay na paghahanap ng mga elemento kumpara sa isang regular na binary tree.

2. Maaari ba akong magkaroon ng mga node na may mga dobleng halaga sa isang binary tree?

Oo, posible na magkaroon ng mga node na may mga dobleng halaga sa isang binary tree. Gayunpaman, depende sa pagpapatupad at sa mga partikular na panuntunan ng binary tree, maaaring may iba't ibang paraan upang makitungo sa mga duplicate na node. Maaaring payagan ng ilang pagpapatupad ang mga duplicate at iimbak ang mga ito sa anumang pagkakasunud-sunod, habang ang iba ay maaaring mangailangan na ang mga duplicate na halaga ay espesyal na pangasiwaan o itapon.

3. Paano ko maaalis ang isang partikular na node mula sa isang binary tree?

Upang alisin ang isang partikular na node mula sa isang binary tree, kailangan mong sundin ang mga hakbang na ito:

1. Hanapin ang node na gusto mong tanggalin gamit ang tree search.
2. Isaalang-alang ang iba't ibang mga kaso ng pag-aalis:
   • Kung ang node ay walang mga anak, maaari mo lamang itong tanggalin at palayain ang memorya nito.
   • Kung ang node ay may isang anak lamang, maaari mong palitan ang node ng anak nito.
   • Kung ang node ay may dalawang anak, dapat mong hanapin ang pinakamalapit na kahalili (ang pinakamaliit na node sa kanang subtree) at palitan ang halaga ng node na tatanggalin ng halaga ng kahalili. Pagkatapos ay alisin ang kahalili mula sa puno.
3. Inaayos ang mga link at pointer kung kinakailangan upang mapanatili ang tamang istraktura ng puno.

4. Ano ang full binary tree?

Ang full binary tree ay isang espesyal na uri ng binary tree kung saan ang lahat ng antas, maliban sa posibleng huli, ay ganap na napuno, at ang mga node ng huling antas ay matatagpuan sa kaliwa hangga't maaari. Nangangahulugan ito na ang lahat ng node ay may dalawang anak, maliban sa posibleng mga node sa huling antas, na maaaring magkaroon ng isa o walang anak.

5. Ano ang taas ng binary tree?

Ang taas ng isang binary tree ay ang haba ng pinakamahabang landas mula sa ugat hanggang sa isang dahon. Sa madaling salita, ito ang pinakamataas na bilang ng mga gilid sa pagitan ng ugat at anumang dahon sa puno. Ang taas ay sinusukat sa bilang ng mga antas, kaya ang isang puno na may isang node lamang ay may taas na 0, at ang isang walang laman na puno ay walang taas.

6. Kailan ako dapat gumamit ng binary tree sa aking mga programa?

Ang mga binary tree ay kapaki-pakinabang sa iba't ibang sitwasyon. Ang ilang karaniwang mga kaso kung saan maaari kang gumamit ng mga binary tree ay kinabibilangan ng:

• Mahusay na paghahanap ng elemento: Kung kailangan mong mabilis na maghanap ng mga elemento sa isang istraktura ng data, ang isang binary tree ay maaaring magbigay ng mahusay na pag-access sa data.
• Kinakatawan ang mga hierarchical na relasyon: Ang mga binary tree ay perpekto para sa kumakatawan sa mga hierarchical na relasyon, tulad ng istraktura ng direktoryo sa isang file system.
• Pag-uuri ng Data: Maaari kang gumamit ng mga binary na puno ng paghahanap upang mahusay na pag-uri-uriin ang data at magsagawa ng mga paghahanap, pagpapasok, at pagtanggal sa oras ng logarithmic.

Tandaan na suriin ang iyong mga kinakailangan at isaalang-alang ang pagiging kumplikado ng mga operasyon sa mga binary tree bago magpasyang gamitin ang mga ito sa iyong mga programa.

Konklusyon

Sa komprehensibong gabay na ito, na-explore namin ang mga pangunahing konsepto ng mga binary tree sa C. Natutunan namin ang tungkol sa kanilang istraktura, kung paano magpasok at mag-alis ng mga node, magsagawa ng mga traversal, at maghanap ng mga elemento sa isang binary tree.

Umaasa kami na ang gabay na ito ay nagbigay sa iyo ng matibay na pag-unawa sa mga binary tree at kung paano ipatupad ang mga ito sa C. Ang mga binary tree ay maraming nalalaman at makapangyarihang mga istruktura ng data na makakatulong sa iyong lutasin ang malawak na hanay ng mga problema sa programming.

Tandaan na magsanay at mag-eksperimento sa mga ibinigay na halimbawa upang palakasin ang iyong pag-unawa sa mga binary tree sa C. Good luck sa iyong paglalakbay sa pag-aaral at pag-develop ng software!