Binārais koks C
C, a binārais koks ir koka datu struktūras gadījums ar vecāku mezglu, kuram var būt ne vairāk kā divi pakārtotie mezgli; 0, 1 vai 2 pēcnācēju mezgli. Katrs mezgls a binārais koks ir sava vērtība un divas norādes uz saviem bērniem, viena norāde uz kreiso bērnu, bet otra uz labo bērnu.
Binārā koka deklarācija
A binārais koks var deklarēt C, izmantojot objektu, ko sauc struktūra kas attēlo vienu no koka mezgliem.
struktūra mezgls {
datu tips var_nosaukums ;
struktūra mezgls * pa kreisi ;
struktūra mezgls * pa labi ;
} ;
Iepriekš ir viena deklarācija binārais koks mezgla nosaukums kā mezgls. Tam ir trīs vērtības; viens ir datu glabāšanas mainīgais, bet pārējie divi ir norādes uz bērnu. (vecākmezgla kreisais un labais atvasinātais).
Fakti par bināro koku
Pat lielām datu kopām, izmantojot a binārais koks padara meklēšanu vienkāršāku un ātrāku. Koku zaru skaits nav ierobežots. Atšķirībā no masīva, jebkura veida kokus var izgatavot un palielināt, pamatojoties uz to, kas tiek prasīts no indivīda.
Binārā koka ieviešana C valodā
Tālāk ir sniegta detalizēta rokasgrāmata, kā ieviest a Binārais koks C.
1. darbība: deklarējiet bināro meklēšanas koku
Izveidojiet struktūras mezglu, kurā ir trīs veidu dati, piemēram, dati, *kreisais_bērns un *labais_bērns, kur dati var būt vesela skaitļa tipa, un gan *kreisais_bērns, gan *labais_bērns mezglus var deklarēt kā NULL vai ne.
struktūra mezgls{
starpt datus ;
struktūra mezgls * pareizais_bērns ;
struktūra mezgls * kreisais_bērns ;
} ;
2. darbība: izveidojiet jaunus mezglus binārajā meklēšanas kokā
Izveidojiet jaunu mezglu, izveidojot funkciju, kas pieņem veselu skaitli kā argumentu un nodrošina rādītāju uz jauno mezglu, kas izveidots ar šo vērtību. Izmantojiet malloc() funkciju programmā C, lai izveidotu dinamisku atmiņas piešķiršanu izveidotajam mezglam. Inicializējiet kreiso un labo bērnu uz NULL un atgrieziet nodeName.
struktūra mezgls * izveidot ( datu tipa dati )
{
struktūra mezgls * nodeName = malloc ( izmērs ( struktūra mezgls ) ) ;
nodeName -> datus = vērtību ;
nodeName -> kreisais_bērns = nodeName -> pareizais_bērns = NULL ;
atgriezties nodeName ;
}
3. darbība: ievietojiet labo un kreiso bērnu binārajā kokā
Izveidojiet funkcijas insert_left un insert_right, kas pieņems divus ievades datus, kas ir ievietojamā vērtība un rādītājs uz mezglu, kuram tiks pievienoti abi bērni. Izsauciet izveides funkciju, lai izveidotu jaunu mezglu un piešķirtu atgriezto rādītāju kreisās atvases kreisajam rādītājam vai saknes vecāka labās atvases labajam rādītājam.
struktūra mezgls * ievietot_pa kreisi ( struktūra mezgls * sakne , datu tipa dati ) {sakne -> pa kreisi = izveidot ( datus ) ;
atgriezties sakne -> pa kreisi ;
}
struktūra mezgls * ievietot_pa labi ( struktūra mezgls * sakne , datu tipa dati ) {
sakne -> pa labi = izveidot ( datus ) ;
atgriezties sakne -> pa labi ;
}
4. darbība: parādiet binārā koka mezglus, izmantojot šķērsošanas metodes
Mēs varam parādīt kokus, izmantojot trīs šķērsošanas metodes C. Šīs šķērsošanas metodes ir:
1: Iepriekšēja pasūtījuma izbraukšana
Izmantojot šo šķērsošanas metodi, mēs ejam cauri mezgliem virzienā no vecāku_mezgls->kreisais_bērns->labais_bērns .
nederīgs Iepriekšpasūtījums ( mezgls * sakne ) {ja ( sakne ) {
printf ( '%d \n ' , sakne -> datus ) ;
Display_pre_order ( sakne -> pa kreisi ) ;
Display_pre_order ( sakne -> pa labi ) ;
}
}
2: Pasūtījuma izbraukšana
Izmantojot šo šķērsošanas metodi, mēs ejam cauri mezgliem virzienā no kreisais_bērns->labais_bērns->vecāks_mezgls-> .
nederīgs display_post_order ( mezgls * sakne ) {ja ( binārais_koks ) {
display_post_order ( sakne -> pa kreisi ) ;
display_post_order ( sakne -> pa labi ) ;
printf ( '%d \n ' , sakne -> datus ) ;
}
}
3: Pasūtījuma šķērsošana
Izmantojot šo šķērsošanas metodi, mēs ejam cauri mezgliem virzienā no kreisais_mezgls->saknes_bērns->labais_bērns .
nederīgs Display_in_order ( mezgls * sakne ) {ja ( binārais_koks ) {
Display_in_order ( sakne -> pa kreisi ) ;
printf ( '%d \n ' , sakne -> datus ) ;
Display_in_order ( sakne -> pa labi ) ;
}
}
5. darbība: veiciet dzēšanu binārajā kokā
Mēs varam izdzēst izveidoto Binārais koks dzēšot abus bērnus ar vecāku mezgla funkciju C, kā norādīts tālāk.
nederīgs delete_t ( mezgls * sakne ) {ja ( sakne ) {
delete_t ( sakne -> pa kreisi ) ;
delete_t ( sakne -> pa labi ) ;
bezmaksas ( sakne ) ;
}
}
C Binārā meklēšanas koka programma
Tālāk ir sniegta pilnīga binārā meklēšanas koka ieviešana C programmēšanā:
#include#include
struktūra mezgls {
starpt vērtību ;
struktūra mezgls * pa kreisi , * pa labi ;
} ;
struktūra mezgls * mezgls1 ( starpt datus ) {
struktūra mezgls * tmp = ( struktūra mezgls * ) malloc ( izmērs ( struktūra mezgls ) ) ;
tmp -> vērtību = datus ;
tmp -> pa kreisi = tmp -> pa labi = NULL ;
atgriezties tmp ;
}
nederīgs drukāt ( struktūra mezgls * saknes_mezgls ) // mezglu parādīšana!
{
ja ( saknes_mezgls != NULL ) {
drukāt ( saknes_mezgls -> pa kreisi ) ;
printf ( '%d \n ' , saknes_mezgls -> vērtību ) ;
drukāt ( saknes_mezgls -> pa labi ) ;
}
}
struktūra mezgls * insert_node ( struktūra mezgls * mezgls , starpt datus ) // ievietojot mezglus!
{
ja ( mezgls == NULL ) atgriezties mezgls1 ( datus ) ;
ja ( datus < mezgls -> vērtību ) {
mezgls -> pa kreisi = insert_node ( mezgls -> pa kreisi , datus ) ;
} cits ja ( datus > mezgls -> vērtību ) {
mezgls -> pa labi = insert_node ( mezgls -> pa labi , datus ) ;
}
atgriezties mezgls ;
}
starpt galvenais ( ) {
printf ( Binārā meklēšanas koka C ieviešana! \n \n ' ) ;
struktūra mezgls * vecāks = NULL ;
vecāks = insert_node ( vecāks , 10 ) ;
insert_node ( vecāks , 4 ) ;
insert_node ( vecāks , 66 ) ;
insert_node ( vecāks , Četri, pieci ) ;
insert_node ( vecāks , 9 ) ;
insert_node ( vecāks , 7 ) ;
drukāt ( vecāks ) ;
atgriezties 0 ;
}
Iepriekš minētajā kodā mēs vispirms deklarējam a mezgls izmantojot struktūra . Pēc tam mēs inicializējam jaunu mezglu kā ' mezgls1 ” un dinamiski piešķirt atmiņu, izmantojot malloc () C formātā ar datiem un diviem rādītājiem ierakstiet bērnus, izmantojot deklarēto mezglu. Pēc tam mēs parādām mezglu ar printf() funkciju un izsauciet to galvenais () funkciju. Tad insertion_node() tiek izveidota funkcija, kur, ja mezgla dati ir NULL, tad mezgls1 ir pārtraukta, pretējā gadījumā dati tiek ievietoti mezgls kreisā un labā bērna (vecāks). Programma sāk izpildi no galvenais () funkcija, kas ģenerē mezglu, izmantojot dažus paraugmezglus kā bērnus, un pēc tam izmanto In-Order šķērsošanas metodes, lai drukātu mezgla saturu.
Izvade
Secinājums
Lai saglabātu datus nelineārā formā, bieži izmanto kokus. Binārie koki ir koku veidi, kur katram mezglam (vecākam) ir divi pēcnācēji – kreisais bērns un labais bērns. A binārais koks ir daudzpusīga datu pārsūtīšanas un uzglabāšanas metode. Tas ir efektīvāks, salīdzinot ar saistīto sarakstu programmā C. Iepriekš minētajā rakstā mēs esam redzējuši jēdzienu Binārais koks ar soli pa solim ieviešanu a Binārā meklēšanas koks C.