Izihlahla kanambambili ku-C: Umhlahlandlela Ophelele Wabaqalayo

Informatec Digital » Ama-algorithms » Izihlahla kanambambili ku-C: Umhlahlandlela Ophelele Wabaqalayo

Siyakwamukela kulo mhlahlandlela ophelele wezihlahla kanambambili ku-C. Kulesi sihloko, sizohlola izinto eziyisisekelo zezihlahla kanambambili nokuthi ungazisebenzisa kanjani ngolimi lokuhlela lwe-C Uma ungumqali ohlelweni noma nje ufuna ukuthuthukisa amakhono akho e-C, lo mhlahlandlela ungowakho.

Izihlahla ezimbili ziyizakhiwo zedatha eziyisisekelo kwisayensi yamakhompyutha futhi zisetshenziswa ezinhlobonhlobo zezinhlelo zokusebenza. Ukuqonda ukuthi zisebenza kanjani nokuthi ungazisebenzisa kanjani kuzokusiza ukuxazulula izinkinga eziyinkimbinkimbi ngempumelelo nangendlela ehlelekile.

Kuyo yonke le ndatshana, sizohlola izisekelo zezihlahla ezimbili, okuhlanganisa isakhiwo sazo, ukufakwa nokususwa kwama-node, ukuwela, kanye nokusesha izakhi. Sizophinde sinikeze izibonelo ezisebenzayo olimini lokuhlela lwe-C ukuze ubone ukuthi le mibono isetshenziswa kanjani ekusebenzeni.

Ngakho ake siqale!

Ziyini izihlahla kanambambili?

Izihlahla kanambambili ziyizakhiwo zedatha ezilandelanayo ezakhiwe ngamanodi axhumene. Inodi ngayinye ingaba namanodi ezingane angafinyelela kwamabili: eyodwa kwesokunxele nenye kwesokudla. Lesi sakhiwo esinamagatsha amabili yilokho okuhlukanisa izihlahla kanambambili kwezinye izakhiwo zedatha.

Esihlahleni kanambambili, indawo yokuqala ibizwa ngokuthi i-root node. Amanodi ezingane abizwa ngokuthi ama-child nodes, futhi ama-nodes angenabantwana abizwa ngokuthi ama-leaf nodes. Amanodi asezingeni elifanayo abizwa ngokuthi ama-sibling nodes.

Izinzuzo Binary Trees

Izihlahla kanambambili zinikeza izinzuzo eziningana mayelana nokugcinwa kwedatha okuphumelelayo nokusesha. Ezinye zezinzuzo ezibalulekile zifaka:

1. Usesho olusebenzayoIzihlahla kanambambili zivumela izici ukuthi ziseshwe ngesikhathi sokusebenza ngokushesha kunezinye izakhiwo zedatha, njengohlu oluxhunyiwe. Lokhu kungenxa yesakhiwo se-hierarchical yesihlahla kanye nekhono laso lokuhlukanisa ngokushesha isethi yedatha.
2. Ukufakwa okuguquguqukayo nokususwaIzihlahla kanambambili zivumelana nezimo kakhulu ekufakweni kwamanodi nemisebenzi yokususa. Ngokungafani nezakhiwo zedatha ezimile ezifana nemigqa, izihlahla kanambambili zingakhula futhi ziguqule isakhiwo sazo ngokushintshashintshayo.
3. Ukumelwa kobudlelwano besigabaIzihlahla kanambambili ziwusizo ikakhulukazi ekumeleleni ubudlelwano besigaba phakathi kwezinto. Isibonelo, esakhiweni senkomba yefayela, uhla lwemibhalo ngalunye lungamelwa njengenodi esihlahleni, oluneziqondiso ezingaphansi namafayela njengamanodi engane.

Isakhiwo somuthi kanambambili

Ngaphambi kokuthi singene ekusetshenzisweni kwezihlahla kanambambili ku-C, kubalulekile ukuqonda isakhiwo sazo esiyisisekelo. Inodi ngayinye esihlahleni kanambambili iqukethe inani nezinkomba kumanodi engane angakwesokunxele nakwesokudla, uma inawo.

Ithebula elilandelayo libonisa ukwakheka kwenodi esihlahleni kanambambili:

Inodi kanambambili
I-Valor
Inodi yesokunxele
Inodi yesokudla

Inodi ngayinye ingagcina noma yiluphi uhlobo lwedatha, njengezinombolo eziphelele, izinhlamvu, noma izakhiwo eziyinkimbinkimbi. I-root node iyindawo yokuqala yesihlahla, futhi ukusuka kuyo singakwazi ukufinyelela wonke amanye ama-node.

Ukusebenzisa izihlahla kanambambili ku-C

Manje njengoba sesinokuqonda okuyisisekelo ngezihlahla ze-binary, sekuyisikhathi sokuzisebenzisa ngolimi lokuhlela lwe-C . Okulandelayo, sizobona ukuthi singamemezela futhi sisebenzise kanjani isakhiwo sesihlahla se-binary ku-C.

Ukumemezela isakhiwo sesihlahla kanambambili

Ngo C, singamemezela ukwakheka kwesihlahla kanambambili sisebenzisa isakhiwo nezikhombi. Nasi isimemezelo esiyisisekelo sesakhiwo:

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

Kulesi sakhiwo, valor imele inani eligcinwe ku-node, futhi izquierdo y derecho ziyizikhombi zenodi yengane kwesokunxele nakwesokudla, ngokulandelana.

Ukudala i-node entsha

Ukwakha i-node entsha esihlahleni kanambambili, sidinga ukwaba inkumbulo yenodi bese sibeka amanani ayo. Nansi umsebenzi ka-C odala i-node entsha:

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

Umsebenzi malloc Isetshenziselwa ukwaba inkumbulo eguquguqukayo ku-node. Bese sibeka amanani e-node bese sibuyisela i-node edaliwe.

Ifaka amanodi

Ukufakwa kwenodi kuyinqubo eyisisekelo ezihlahleni kanambambili. Ikuvumela ukuthi ungeze izakhi ezintsha esihlahleni endaweni efanele ngokusekelwe kunani lenodi. Ngezansi kunomsebenzi ka-C wokufaka inodi esihlahleni kanambambili:

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

Lo msebenzi uthola i-pointer empandeni yesihlahla kanye nenani le-node okufanele ifakwe. Uma impande ingenalutho, kusho ukuthi isihlahla asinalutho futhi sakha inodi entsha empandeni. Uma kungenjalo, siqhathanisa inani le-node nenani lempande bese sinquma ukuthi sifake i-node kwesokunxele noma kwesokudla.

Isusa amanodi

Ukususa ama-node esihlahleni kanambambili kungaba nzima kakhulu. Kuya ezimweni ezimbalwa, njengokuthi i-node ezosuswa inabantwana noma cha. Ngezansi kunomsebenzi ka-C wokususa i-node esihlahleni kanambambili:

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

Kulo msebenzi, sihlola ukuthi ingabe inani le-node lingaphansi, likhulu kuno, noma lilingana nenani lempande yamanje. Kuye ngecala, senza lezi zinyathelo ezilandelayo:

• Uma inani lincane, siya kwesokunxele sesihlahla.
• Uma inani likhulu, siya kwesokudla sesihlahla.
• Uma inani lilingana, sithola umlandeli oseduze kakhulu wenodi (i-nodi encane esihlahleni esingezansi esingakwesokudla) bese siyishintsha ngenodi yamanje. Bese sisusa umlandeli kusihlahla esincane esilungile.

Izinqamuleli ezihlahleni kanambambili

I-Traversals iyimisebenzi esivumela ukuthi sivakashele wonke ama-nodes esihlahla kanambambili ngokulandelana okuthile. Kunezinhlobo ezintathu ezijwayelekile zokuvakasha:

Ukuzulazula ngokulandelana : Kuqala ngokuvakashela isihlahla esingaphansi kwesobunxele, bese kuba i-node yamanje, bese ekugcineni kube isihlahla esingaphansi kwesokudla. Nasi umsebenzi we-C owenza ukuzulazula ngokulandelana kwesihlahla esingaphansi kwesibili:

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

Ukudlula ku-oda langaphambilini : Kuvakashela i-node yamanje kuqala, bese kuba i-subtree yesobunxele, bese kuba i-subtree yesokudla. Nasi umsebenzi we-C owenza ukudlula ku-oda langaphambilini kwesihlahla esinobubili:

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

Ukudlula ngemva kwe-oda : Kuqala ngokuvakashela isihlahla esingaphansi kwesobunxele, bese kuba isihlahla esingaphansi kwesokudla, bese ekugcineni kube i-node yamanje. Nasi umsebenzi we-C owenza ukudlula ngemva kwe-oda kwesihlahla esi-binary:

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

Sesha izici

Ukusesha izakhi emthini kanambambili kusivumela ukuthi sithole ngokushesha inani elithile ngaphakathi kwesakhiwo sedatha. Nawu umsebenzi ka-C wokusesha into esihlahleni kanambambili:

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

Lo msebenzi wenza usesho oluphindaphindayo esihlahleni kanambambili. Uma inani lenodi yamanje lilingana nenani eliseshiwe, inodi iyabuyiselwa. Uma kungenjalo, umucu ongezansi wesokunxele noma kwesokudla uyaseshwa ngokusekelwe kunani futhi inqubo iyaphindwa kuze kutholakale inani noma kufinyelelwe ku-null node.

Izibonelo zokusebenzisa izihlahla kanambambili ku-C

Manje njengoba sesihlanganise izinto eziyisisekelo zezihlahla kanambambili nokuthi zingazisebenzisa kanjani ku-C, ake sibheke izibonelo ezithile ezisebenzayo.

Isibonelo 1: Ukudala isihlahla kanambambili

Ake sithi sifuna ukwakha isihlahla kanambambili esinamanani alandelayo: 10, 5, 15, 3, 7, 13, 18. Nansi indlela esingakwenza ngayo ku-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;
}

Kulesi sibonelo, sakha i-pointer empandeni yesihlahla bese sisebenzisa umsebenzi insertarNodo ukwengeza amanani esihlahleni.

Isibonelo sesi-2: Ukunqamula ngokulandelana kwesihlahla kanambambili

Ukuphrinta amanani esihlahla kanambambili ngokulandelana, singabiza umsebenzi inOrden Ngokulandelayo:

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

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

    return 0;
}

Lesi sibonelo sizophrinta amanani esihlahleni ngokulandelana okukhuphukayo.

Imibuzo ebuzwa njalo

1. Uyini umehluko phakathi kwesihlahla kanambambili kanye nomuthi wokusesha kanambambili?

Isihlahla sokusesha esinambambili (BST) siwuhlobo olukhethekile lwesihlahla kanambambili lapho izakhi zihlelwa khona ukuze amanani amancane abe kwesokunxele futhi amanani amakhulu abe kwesokudla. Lokhu kuvumela ukuseshwa okuphumelelayo kwezakhi uma kuqhathaniswa nesihlahla esivamile kanambambili.

2. Ngingaba namanodi anamanani ayimpinda esihlahleni kanambambili?

Yebo, kungenzeka ukuba namanodi anamanani ayimpinda esihlahleni kanambambili. Kodwa-ke, kuye ngokuqaliswa kanye nemithetho ethile yesihlahla kanambambili, kungase kube nezindlela ezahlukene zokubhekana nama-node ayimpinda. Okunye ukusetshenziswa kungase kuvumele izimpinda futhi kugcinwe nganoma iyiphi i-oda, kuyilapho okunye kungase kudinge ukuthi amanani ayimpinda aphathwe ngokukhethekile noma alahlwe.

3. Ngingayisusa kanjani i-node ethile esihlahleni kanambambili?

Ukuze ususe i-node ethile esihlahleni kanambambili, udinga ukulandela lezi zinyathelo:

1. Thola i-node ofuna ukuyisusa usebenzisa usesho lwesihlahla.
2. Cabangela izimo ezihlukahlukene zokuqeda:
   • Uma i-node ingenazo izingane, ungavele uyisuse futhi ukhulule inkumbulo yayo.
   • Uma i-node inengane eyodwa kuphela, ungashintsha i-node ngengane yayo.
   • Uma i-node inezingane ezimbili, kufanele uthole umlandeli oseduze (i-node encane kakhulu esihlahleni esingezansi esingakwesokudla) bese ubuyisela inani lenodi ezosuswa ngenani lomlandeli. Bese ususa owalandela esihlahleni.
3. Ilungisa izixhumanisi nezinkomba njengoba kudingeka ukuze kugcinwe ukwakheka kwesihlahla esifanele.

4. Yini isihlahla esigcwele kanambambili?

Isihlahla esigcwele kanambambili siwuhlobo olukhethekile lomuthi kanambambili lapho wonke amazinga, ngaphandle kwalapho kungenzeka khona okugcina, agcwaliswe ngokuphelele, futhi ama-node ezinga lokugcina atholakala kude kwesokunxele ngangokunokwenzeka. Lokhu kusho ukuthi wonke ama-node anezingane ezimbili, ngaphandle kwama-node asezingeni lokugcina, angase abe nengane eyodwa noma angabi nayo.

5. Kungakanani ukuphakama kwesihlahla kanambambili?

Ukuphakama kwesihlahla kanambambili ubude bendlela ende ukusuka empandeni kuya eqabungeni. Ngamanye amazwi, inani eliphezulu lemiphetho phakathi kwempande nanoma yiliphi iqabunga esihlahleni. Ukuphakama kukalwa ngokwenani lamazinga, ngakho-ke isihlahla esinenodi eyodwa kuphela sinobude obungu-0, futhi isihlahla esingenalutho asinakho ukuphakama.

6. Kufanele ngisebenzise nini isihlahla kanambambili ezinhlelweni zami?

Izihlahla kanambambili ziwusizo ezimweni ezihlukahlukene. Ezinye izimo ezivamile lapho ungasebenzisa khona izihlahla kanambambili zihlanganisa:

• Ukubheka izinto eziphumelelayo: Uma udinga ukubheka ngokushesha izici esakhiweni sedatha, isihlahla kanambambili singanikeza ukufinyelela okusebenzayo kudatha.
• Ukumelela ubudlelwano besigaba: Izihlahla kanambambili zilungele ukumela ubudlelwano besigaba, njengesakhiwo sohla lwemibhalo ku uhlelo lwefayela.
• Ukuhlunga Idatha: Ungasebenzisa izihlahla zokusesha kanambambili ukuze uhlunge idatha ngempumelelo futhi wenze ukusesha, ukufaka, nokususa ngesikhathi se-logarithmic.

Khumbula ukuhlola izidingo zakho futhi ucabangele inkimbinkimbi yokusebenza kwezihlahla kanambambili ngaphambi kokunquma ukuzisebenzisa ezinhlelweni zakho.

Isiphetho

Kulo mhlahlandlela obanzi, sihlole imiqondo eyisisekelo yezihlahla kanambambili ku-C. Sifundile ngesakhiwo sazo, indlela yokufaka nokukhipha ama-node, ukwenza ukunqamula, kanye nokusesha izakhi emthini kanambambili.

Sithemba ukuthi lo mhlahlandlela ukunikeze ukuqonda okuqinile kwezihlahla kanambambili nokuthi ungazisebenzisa kanjani ku-C. Izihlahla kanambambili ziyizakhiwo zedatha eziguquguqukayo nezinamandla ezingakusiza ukuxazulula izinkinga eziningi ezinhlelweni.

Khumbula ukuzilolonga futhi uzame izibonelo ezinikeziwe ukuze uqinise ukuqonda kwakho izihlahla kanambambili ku-C. Sikufisela inhlanhla ohambweni lwakho lokufunda nokuthuthukisa isofthiwe!