Arborele binar în C
În C, a arbore binar este o instanță a unei structuri de date arborescente cu un nod părinte care poate avea un număr maxim de două noduri copil; 0, 1 sau 2 noduri descendenți. Fiecare nod într-un arbore binar are o valoare proprie și două indicatoare către copiii săi, un indicator pentru copilul stâng și celălalt pentru copilul drept.
Declarația de arbore binar
A arbore binar poate fi declarat în C folosind un obiect numit struct care înfățișează unul dintre nodurile din arbore.
struct nodul {
tipul de date var_name ;
struct nodul * stânga ;
struct nodul * dreapta ;
} ;
Mai sus este o declarație a unuia arbore binar numele nodului ca nod. Are trei valori; una este variabila de stocare a datelor, iar celelalte două sunt indicatorii către copil. (copilul din stânga și din dreapta al nodului părinte).
Fapte ale arborelui binar
Chiar și pentru seturi mari de date, folosind a arbore binar face căutarea mai ușoară și mai rapidă. Numărul de ramuri de copac nu este limitat. Spre deosebire de o matrice, copacii de orice fel pot fi creați și măriți în funcție de ceea ce este cerut de la un individ.
Implementarea arborelui binar în C
Următorul este un ghid pas cu pas pentru implementarea a Arborele binar în C.
Pasul 1: Declarați un arbore binar de căutare
Creați un nod struct care are trei tipuri de date, cum ar fi data, *left_child și *right_child, unde datele pot fi de tip întreg și ambele nodurile *left_child și *right_child pot fi declarate ca NULL sau nu.
struct nodul{
int date ;
struct nodul * copil_drept ;
struct nodul * copil_stâng ;
} ;
Pasul 2: Creați noduri noi în arborele de căutare binar
Creați un nou nod creând o funcție care acceptă un număr întreg ca argument și oferă pointerul către noul nod creat cu acea valoare. Utilizați funcția malloc() în C pentru alocarea dinamică a memoriei pentru nodul creat. Inițializați copilul din stânga și din dreapta la NULL și returnați nodeName.
struct nodul * crea ( date tip de date )
{
struct nodul * nodeName = malloc ( dimensiunea ( struct nodul ) ) ;
nodeName -> date = valoare ;
nodeName -> copil_stâng = nodeName -> copil_drept = NUL ;
întoarcere nodeName ;
}
Pasul 3: Inserați copii din dreapta și din stânga în arborele binar
Creați funcțiile insert_left și insert_right care vor accepta două intrări, care sunt valoarea de inserat și pointerul către nodul la care vor fi conectați ambii copii. Apelați funcția de creare pentru a crea un nou nod și alocați pointerul returnat indicatorului din stânga al copilului din stânga sau indicatorului din dreapta al copilului din dreapta al părintelui rădăcină.
struct nodul * insert_left ( struct nodul * rădăcină , date tip de date ) {rădăcină -> stânga = crea ( date ) ;
întoarcere rădăcină -> stânga ;
}
struct nodul * insert_right ( struct nodul * rădăcină , date tip de date ) {
rădăcină -> dreapta = crea ( date ) ;
întoarcere rădăcină -> dreapta ;
}
Pasul 4: Afișați nodurile arborelui binar folosind metode de traversare
Putem afișa arbori folosind trei metode de traversare în C. Aceste metode de traversare sunt:
1: Precomandă Traversal
În această metodă de traversare, vom trece prin noduri într-o direcție de la parent_node->left_child->right_child .
gol pre-comanda ( nodul * rădăcină ) {dacă ( rădăcină ) {
printf ( „%d \n ' , rădăcină -> date ) ;
display_pre_order ( rădăcină -> stânga ) ;
display_pre_order ( rădăcină -> dreapta ) ;
}
}
2: Traversare post-comandă
În această metodă de traversare, vom trece prin noduri într-o direcție de la stânga_copil->right_child->parent_node-> .
gol display_post_order ( nodul * rădăcină ) {dacă ( arbore_binar ) {
display_post_order ( rădăcină -> stânga ) ;
display_post_order ( rădăcină -> dreapta ) ;
printf ( „%d \n ' , rădăcină -> date ) ;
}
}
3: Traversare în ordine
În această metodă de traversare, vom trece prin noduri într-o direcție de la nod_stâng->copil_rădăcină->copil_dreaptă .
gol afișare_în_ordine ( nodul * rădăcină ) {dacă ( arbore_binar ) {
afișare_în_ordine ( rădăcină -> stânga ) ;
printf ( „%d \n ' , rădăcină -> date ) ;
afișare_în_ordine ( rădăcină -> dreapta ) ;
}
}
Pasul 5: Efectuați ștergerea în arbore binar
Putem șterge cele create Arborele binar prin ștergerea ambilor copii cu funcția de nod părinte în C, după cum urmează.
gol şterge_t ( nodul * rădăcină ) {dacă ( rădăcină ) {
şterge_t ( rădăcină -> stânga ) ;
şterge_t ( rădăcină -> dreapta ) ;
gratuit ( rădăcină ) ;
}
}
Programul C al arborelui de căutare binar
Următoarea este implementarea completă a arborelui de căutare binar în programarea C:
#include#include
struct nodul {
int valoare ;
struct nodul * stânga , * dreapta ;
} ;
struct nodul * nodul 1 ( int date ) {
struct nodul * tmp = ( struct nodul * ) malloc ( dimensiunea ( struct nodul ) ) ;
tmp -> valoare = date ;
tmp -> stânga = tmp -> dreapta = NUL ;
întoarcere tmp ;
}
gol imprimare ( struct nodul * nodul_rădăcină ) // afișează nodurile!
{
dacă ( nodul_rădăcină != NUL ) {
imprimare ( nodul_rădăcină -> stânga ) ;
printf ( „%d \n ' , nodul_rădăcină -> valoare ) ;
imprimare ( nodul_rădăcină -> dreapta ) ;
}
}
struct nodul * insert_node ( struct nodul * nodul , int date ) // inserarea nodurilor!
{
dacă ( nodul == NUL ) întoarcere nodul 1 ( date ) ;
dacă ( date < nodul -> valoare ) {
nodul -> stânga = insert_node ( nodul -> stânga , date ) ;
} altfel dacă ( date > nodul -> valoare ) {
nodul -> dreapta = insert_node ( nodul -> dreapta , date ) ;
}
întoarcere nodul ;
}
int principal ( ) {
printf ( „Implementarea C a arborelui de căutare binar! \n \n ' ) ;
struct nodul * mamă = NUL ;
mamă = insert_node ( mamă , 10 ) ;
insert_node ( mamă , 4 ) ;
insert_node ( mamă , 66 ) ;
insert_node ( mamă , Patru cinci ) ;
insert_node ( mamă , 9 ) ;
insert_node ( mamă , 7 ) ;
imprimare ( mamă ) ;
întoarcere 0 ;
}
În codul de mai sus, declarăm mai întâi a nodul folosind struct . Apoi inițializam un nou nod ca „ nodul 1 ” și alocați memoria dinamic folosind malloc() în C cu date și doi pointeri tip copii folosind nodul declarat. După aceasta, afișăm nodul by printf() funcția și numiți-o în principal() funcţie. Apoi insert_node() este creată funcția, unde dacă datele nodului sunt NULL, atunci nodul 1 este retras, altfel datele sunt plasate în nodul (părinte) copilului stâng și drept. Programul începe execuția de la principal() funcția, care generează un nod folosind câteva noduri eșantion ca copii și apoi utilizează metode de traversare în ordine pentru a imprima conținutul nodului.
Ieșire
Concluzie
Arborii sunt folosiți frecvent pentru a păstra datele într-o formă neliniară. Arbori binari sunt tipuri de arbori în care fiecare nod (părinte) are doi descendenți copilul stâng și copilul drept. A arbore binar este o metodă versatilă de transfer și stocare a datelor. Este mai eficient în comparație cu Linked-List în C. În articolul de mai sus, am văzut conceptul de Arborele binar cu implementarea pas cu pas a a Arborele de căutare binar în C.