Binarno stablo u C
U C, a binarno stablo je instanca podatkovne strukture stabla s nadređenim čvorom koji može imati maksimalan broj od dva podređena čvora; 0, 1 ili 2 čvora potomka. Svaki pojedini čvor u a binarno stablo ima vlastitu vrijednost i dva pokazivača na svoju djecu, jedan pokazivač za lijevo dijete, a drugi za desno dijete.
Deklaracija binarnog stabla
A binarno stablo može se deklarirati u C-u pomoću objekta tzv strukturirati koji prikazuje jedan od čvorova u stablu.
strukturirati čvor {
tip podataka var_name ;
strukturirati čvor * lijevo ;
strukturirati čvor * pravo ;
} ;
Iznad je izjava jednog binarno stablo naziv čvora kao čvor. Ima tri vrijednosti; jedna je varijabla za pohranu podataka, a druga dva su pokazivači na dijete. (lijevo i desno dijete nadređenog čvora).
Činjenice binarnog stabla
Čak i za velike skupove podataka, koristeći a binarno stablo olakšava i ubrzava pretraživanje. Broj grana stabla nije ograničen. Za razliku od niza, stabla bilo koje vrste mogu se napraviti i povećati na temelju onoga što se od pojedinca traži.
Implementacija binarnog stabla u C
Slijedi vodič korak po korak za implementaciju a Binarno stablo u C.
Korak 1: Deklarirajte stablo binarnog pretraživanja
Napravite strukturni čvor koji ima tri tipa podataka, kao što su podaci, *left_child i *right_child, gdje podaci mogu biti cjelobrojnog tipa, a oba čvora *left_child i *right_child mogu se deklarirati kao NULL ili ne.
strukturirati čvor{
int podaci ;
strukturirati čvor * desno_dijete ;
strukturirati čvor * lijevo_dijete ;
} ;
Korak 2: Stvorite nove čvorove u stablu binarnog pretraživanja
Stvorite novi čvor stvaranjem funkcije koja prihvaća cijeli broj kao argument i daje pokazivač na novi čvor stvoren s tom vrijednošću. Koristite funkciju malloc() u C-u za dinamičku dodjelu memorije za kreirani čvor. Inicijalizirajte lijevo i desno dijete na NULL i vratite nodeName.
strukturirati čvor * stvoriti ( podaci tipa podataka )
{
strukturirati čvor * naziv čvora = malloc ( veličina ( strukturirati čvor ) ) ;
naziv čvora -> podaci = vrijednost ;
naziv čvora -> lijevo_dijete = naziv čvora -> desno_dijete = NULL ;
povratak naziv čvora ;
}
Korak 3: Umetnite desnu i lijevu djecu u binarno stablo
Napravite funkcije insert_left i insert_right koje će prihvatiti dva ulaza, a to su vrijednost koju treba umetnuti i pokazivač na čvor na koji će oba djeteta biti povezana. Pozovite funkciju create za kreiranje novog čvora i dodijelite vraćeni pokazivač lijevom pokazivaču lijevog djeteta ili desnom pokazivaču desnog djeteta korijenskog roditelja.
strukturirati čvor * umetni_lijevo ( strukturirati čvor * korijen , podaci tipa podataka ) {korijen -> lijevo = stvoriti ( podaci ) ;
povratak korijen -> lijevo ;
}
strukturirati čvor * umetni_desno ( strukturirati čvor * korijen , podaci tipa podataka ) {
korijen -> pravo = stvoriti ( podaci ) ;
povratak korijen -> pravo ;
}
Korak 4: Prikažite čvorove binarnog stabla pomoću metoda obilaska
Možemo prikazati stabla koristeći tri metode obilaska u C-u. Te metode obilaska su:
1: Prolazak prije narudžbe
U ovoj metodi obilaska, proći ćemo kroz čvorove u smjeru od nadređeni_čvor->lijevo_dijete->desno_dijete .
poništiti prednarudžba ( čvor * korijen ) {ako ( korijen ) {
printf ( '%d \n ' , korijen -> podaci ) ;
prikazati_prednarudžbu ( korijen -> lijevo ) ;
prikazati_prednarudžbu ( korijen -> pravo ) ;
}
}
2: Prolaz nakon narudžbe
U ovoj metodi obilaska, proći ćemo kroz čvorove u smjeru od lijevo_dijete->desno_dijete->roditeljski_čvor-> .
poništiti prikaz_post_narudžbe ( čvor * korijen ) {ako ( binarno_stablo ) {
prikaz_post_narudžbe ( korijen -> lijevo ) ;
prikaz_post_narudžbe ( korijen -> pravo ) ;
printf ( '%d \n ' , korijen -> podaci ) ;
}
}
3: Prolazak po redoslijedu
U ovoj metodi obilaska, proći ćemo kroz čvorove u smjeru od lijevi_čvor->korijensko_dijete->desno_dijete .
poništiti prikaz_po_redu ( čvor * korijen ) {ako ( binarno_stablo ) {
prikaz_po_redu ( korijen -> lijevo ) ;
printf ( '%d \n ' , korijen -> podaci ) ;
prikaz_po_redu ( korijen -> pravo ) ;
}
}
Korak 5: Izvršite brisanje u binarnom stablu
Stvoreno možemo izbrisati Binarno stablo brisanjem oba djeteta s funkcijom nadređenog čvora u C-u kako slijedi.
poništiti delete_t ( čvor * korijen ) {ako ( korijen ) {
delete_t ( korijen -> lijevo ) ;
delete_t ( korijen -> pravo ) ;
besplatno ( korijen ) ;
}
}
C program stabla binarnog pretraživanja
Slijedi potpuna implementacija stabla binarnog pretraživanja u C programiranju:
#include#include
strukturirati čvor {
int vrijednost ;
strukturirati čvor * lijevo , * pravo ;
} ;
strukturirati čvor * čvor1 ( int podaci ) {
strukturirati čvor * tmp = ( strukturirati čvor * ) malloc ( veličina ( strukturirati čvor ) ) ;
tmp -> vrijednost = podaci ;
tmp -> lijevo = tmp -> pravo = NULL ;
povratak tmp ;
}
poništiti ispisati ( strukturirati čvor * root_node ) // prikazivanje čvorova!
{
ako ( root_node != NULL ) {
ispisati ( root_node -> lijevo ) ;
printf ( '%d \n ' , root_node -> vrijednost ) ;
ispisati ( root_node -> pravo ) ;
}
}
strukturirati čvor * umetnuti_čvor ( strukturirati čvor * čvor , int podaci ) // umetanje čvorova!
{
ako ( čvor == NULL ) povratak čvor1 ( podaci ) ;
ako ( podaci < čvor -> vrijednost ) {
čvor -> lijevo = umetnuti_čvor ( čvor -> lijevo , podaci ) ;
} drugo ako ( podaci > čvor -> vrijednost ) {
čvor -> pravo = umetnuti_čvor ( čvor -> pravo , podaci ) ;
}
povratak čvor ;
}
int glavni ( ) {
printf ( 'C implementacija stabla binarnog pretraživanja! \n \n ' ) ;
strukturirati čvor * roditelj = NULL ;
roditelj = umetnuti_čvor ( roditelj , 10 ) ;
umetnuti_čvor ( roditelj , 4 ) ;
umetnuti_čvor ( roditelj , 66 ) ;
umetnuti_čvor ( roditelj , Četiri pet ) ;
umetnuti_čvor ( roditelj , 9 ) ;
umetnuti_čvor ( roditelj , 7 ) ;
ispisati ( roditelj ) ;
povratak 0 ;
}
U gornjem kodu, prvo deklariramo a čvor korištenjem strukturirati . Zatim inicijaliziramo novi čvor kao ' čvor1 ” i dinamički dodijeliti memoriju pomoću malloc() u C s podacima i dva pokazivača tipa djeca koristeći deklarirani čvor. Nakon toga prikazujemo čvor prema printf() funkciju i nazovite je u glavni() funkcija. Onda čvor_umetanja() kreirana je funkcija, gdje ako su podaci čvora NULL, onda čvor1 je u mirovini, inače se podaci stavljaju u čvor (roditelj) lijevog i desnog djeteta. Program počinje izvršavanje od glavni() funkcija, koja generira čvor koristeći nekoliko uzoraka čvorova kao djecu, a zatim koristi In-Order metode obilaska za ispis sadržaja čvora.
Izlaz
Zaključak
Stabla se često koriste za čuvanje podataka u nelinearnom obliku. Binarna stabla su vrste stabala gdje svaki čvor (roditelj) ima dva potomka, lijevo dijete i desno dijete. A binarno stablo je svestrana metoda prijenosa i pohrane podataka. Učinkovitiji je u usporedbi s povezanim popisom u C-u. U gornjem članku vidjeli smo koncept Binarno stablo s implementacijom korak po korak a Stablo binarnog pretraživanja u C.