Binarno drevo v C
V C, a binarno drevo je primerek drevesne podatkovne strukture z nadrejenim vozliščem, ki ima lahko največ dve podrejeni vozlišči; 0, 1 ali 2 vozlišča potomcev. Vsako posamezno vozlišče v a binarno drevo ima lastno vrednost in dva kazalca na svoje otroke, enega kazalca za levega otroka in drugega za desnega otroka.
Deklaracija binarnega drevesa
A binarno drevo lahko deklarirate v C z uporabo objekta, imenovanega struct ki prikazuje eno od vozlišč v drevesu.
struct vozlišče {
podatkovni tip var_name ;
struct vozlišče * levo ;
struct vozlišče * prav ;
} ;
Zgoraj je izjava enega binarno drevo ime vozlišča kot vozlišče. Ima tri vrednosti; ena je spremenljivka za shranjevanje podatkov, druga dva pa sta kazalca na otroka. (levi in desni podrejeni element nadrejenega vozlišča).
Dejstva o binarnem drevesu
Tudi za velike nize podatkov z uporabo a binarno drevo omogoča lažje in hitrejše iskanje. Število drevesnih vej ni omejeno. V nasprotju z nizom je mogoče izdelati in povečati drevesa katere koli vrste glede na to, kar se od posameznika zahteva.
Implementacija binarnega drevesa v C
Sledi vodnik po korakih za izvajanje a Binarno drevo v C.
1. korak: Deklarirajte binarno iskalno drevo
Ustvarite strukturno vozlišče, ki ima tri vrste podatkov, kot so podatki, *left_child in *right_child, kjer so lahko podatki celoštevilskega tipa, obe vozlišči *left_child in *right_child pa sta lahko deklarirani kot NULL ali ne.
struct vozlišče{
int podatke ;
struct vozlišče * pravi_otrok ;
struct vozlišče * levi_otrok ;
} ;
2. korak: ustvarite nova vozlišča v binarnem iskalnem drevesu
Ustvarite novo vozlišče tako, da ustvarite funkcijo, ki sprejme celo število kot argument in zagotovi kazalec na novo vozlišče, ustvarjeno s to vrednostjo. Uporabite funkcijo malloc() v C za dinamično dodelitev pomnilnika za ustvarjeno vozlišče. Inicializirajte levega in desnega otroka na NULL in vrnite ime vozlišča.
struct vozlišče * ustvariti ( podatkovni tip podatkov )
{
struct vozlišče * imevozlišča = malloc ( sizeof ( struct vozlišče ) ) ;
imevozlišča -> podatke = vrednost ;
imevozlišča -> levi_otrok = imevozlišča -> pravi_otrok = NIČ ;
vrnitev imevozlišča ;
}
3. korak: V binarno drevo vstavite desnega in levega otroka
Ustvarite funkciji insert_left in insert_right, ki bosta sprejeli dva vhoda, ki sta vrednost, ki jo je treba vstaviti, in kazalec na vozlišče, s katerim bosta oba otroka povezana. Pokličite funkcijo create, da ustvarite novo vozlišče in vrnjeni kazalec dodelite levemu kazalcu levega podrejenega elementa ali desnemu kazalcu desnega podrejenega elementa korenskega nadrejenega.
struct vozlišče * vstavi_levo ( struct vozlišče * korenina , podatkovni tip podatkov ) {korenina -> levo = ustvariti ( podatke ) ;
vrnitev korenina -> levo ;
}
struct vozlišče * vstavi_desno ( struct vozlišče * korenina , podatkovni tip podatkov ) {
korenina -> prav = ustvariti ( podatke ) ;
vrnitev korenina -> prav ;
}
4. korak: Prikažite vozlišča binarnega drevesa z uporabo metod prehoda
Drevesa lahko prikažemo s tremi metodami prečkanja v C. Te metode prečkanja so:
1: Prehod pred naročilom
Pri tej metodi prečkanja bomo šli skozi vozlišča v smeri od nadrejeno_vozlišče->levi_podrejeni->desni_podrejeni .
praznina prednaročilo ( vozlišče * korenina ) {če ( korenina ) {
printf ( '%d \n ' , korenina -> podatke ) ;
prikaz_prednaročilo ( korenina -> levo ) ;
prikaz_prednaročilo ( korenina -> prav ) ;
}
}
2: Prehod po naročilu
Pri tej metodi prečkanja bomo šli skozi vozlišča v smeri od levi_podrejeni->desni_podrejeni->nadrejeno_vozlišče-> .
praznina display_post_order ( vozlišče * korenina ) {če ( binarno_drevo ) {
display_post_order ( korenina -> levo ) ;
display_post_order ( korenina -> prav ) ;
printf ( '%d \n ' , korenina -> podatke ) ;
}
}
3: Prehod po vrstnem redu
Pri tej metodi prečkanja bomo šli skozi vozlišča v smeri od levo_vozlišče->korenski_podrejeni->desni_podrejeni .
praznina display_in_order ( vozlišče * korenina ) {če ( binarno_drevo ) {
display_in_order ( korenina -> levo ) ;
printf ( '%d \n ' , korenina -> podatke ) ;
display_in_order ( korenina -> prav ) ;
}
}
5. korak: Izvedite brisanje v binarnem drevesu
Ustvarjeno lahko izbrišemo Binarno drevo z brisanjem obeh podrejenih s funkcijo nadrejenega vozlišča v C, kot sledi.
praznina delete_t ( vozlišče * korenina ) {če ( korenina ) {
delete_t ( korenina -> levo ) ;
delete_t ( korenina -> prav ) ;
prost ( korenina ) ;
}
}
C program za binarno iskalno drevo
Sledi popolna izvedba binarnega iskalnega drevesa v programiranju C:
#include#include
struct vozlišče {
int vrednost ;
struct vozlišče * levo , * prav ;
} ;
struct vozlišče * vozlišče1 ( int podatke ) {
struct vozlišče * tmp = ( struct vozlišče * ) malloc ( sizeof ( struct vozlišče ) ) ;
tmp -> vrednost = podatke ;
tmp -> levo = tmp -> prav = NIČ ;
vrnitev tmp ;
}
praznina tiskanje ( struct vozlišče * korensko_vozlišče ) // prikaz vozlišč!
{
če ( korensko_vozlišče != NIČ ) {
tiskanje ( korensko_vozlišče -> levo ) ;
printf ( '%d \n ' , korensko_vozlišče -> vrednost ) ;
tiskanje ( korensko_vozlišče -> prav ) ;
}
}
struct vozlišče * vstavi_vozlišče ( struct vozlišče * vozlišče , int podatke ) // vstavljanje vozlišč!
{
če ( vozlišče == NIČ ) vrnitev vozlišče1 ( podatke ) ;
če ( podatke < vozlišče -> vrednost ) {
vozlišče -> levo = vstavi_vozlišče ( vozlišče -> levo , podatke ) ;
} drugače če ( podatke > vozlišče -> vrednost ) {
vozlišče -> prav = vstavi_vozlišče ( vozlišče -> prav , podatke ) ;
}
vrnitev vozlišče ;
}
int glavni ( ) {
printf ( 'C implementacija binarnega iskalnega drevesa! \n \n ' ) ;
struct vozlišče * starš = NIČ ;
starš = vstavi_vozlišče ( starš , 10 ) ;
vstavi_vozlišče ( starš , 4 ) ;
vstavi_vozlišče ( starš , 66 ) ;
vstavi_vozlišče ( starš , Štiri, pet ) ;
vstavi_vozlišče ( starš , 9 ) ;
vstavi_vozlišče ( starš , 7 ) ;
tiskanje ( starš ) ;
vrnitev 0 ;
}
V zgornji kodi najprej deklariramo a vozlišče uporabo struct . Nato inicializiramo novo vozlišče kot ' vozlišče1 ” in dinamično dodeli pomnilnik z uporabo malloc() v C s podatki in dvema kazalcema vnesite otroke z uporabo deklariranega vozlišča. Po tem prikažemo vozlišče z printf() funkcijo in jo pokličite v glavni () funkcijo. Potem je vozlišče_vstavljanja() je ustvarjena funkcija, kjer je, če so podatki vozlišča NULL, potem vozlišče1 je upokojen, sicer se podatki nahajajo v vozlišče (starša) levega in desnega otroka. Program se začne izvajati od glavni () funkcijo, ki generira vozlišče z uporabo nekaj vzorčnih vozlišč kot podrejenih in nato uporablja metode prečkanja po vrstnem redu za tiskanje vsebine vozlišča.
Izhod
Zaključek
Drevesa se pogosto uporabljajo za shranjevanje podatkov v nelinearni obliki. Binarna drevesa so vrste dreves, kjer ima vsako vozlišče (starš) dva potomca, levega in desnega otroka. A binarno drevo je vsestranski način prenosa in shranjevanja podatkov. Je bolj učinkovit v primerjavi s povezanim seznamom v C. V zgornjem članku smo videli koncept Binarno drevo s postopnim izvajanjem a Binarno iskalno drevo v C.