Dvejetainis medis C
C, a dvejetainis medis yra medžio duomenų struktūros pavyzdys su pirminiu mazgu, kuris gali turėti ne daugiau kaip du antrinius mazgus; 0, 1 arba 2 palikuonių mazgai. Kiekvienas mazgas a dvejetainis medis turi savo vertę ir dvi nuorodas į savo vaikus: viena rodyklė kairiajam, o kita - dešiniajam.
Dvejetainio medžio deklaracija
A dvejetainis medis gali būti deklaruojamas C naudojant objektą, vadinamą struktūra kuri vaizduoja vieną iš medžio mazgų.
struktūra mazgas {
duomenų tipas var_name ;
struktūra mazgas * paliko ;
struktūra mazgas * teisingai ;
} ;
Aukščiau yra vieno pareiškimas dvejetainis medis mazgo pavadinimas kaip mazgas. Jis turi tris vertybes; vienas yra duomenų saugojimo kintamasis, o kiti du yra nuorodos į vaiką. (kairysis ir dešinysis pirminio mazgo antrinis).
Faktai apie dvejetainį medį
Net ir dideliems duomenų rinkiniams, naudojant a dvejetainis medis palengvina ir pagreitina paiešką. Medžių šakų skaičius neribojamas. Priešingai nei masyvas, bet kokios rūšies medžiai gali būti gaminami ir padidinami atsižvelgiant į tai, ko reikalaujama iš individo.
Dvejetainio medžio įgyvendinimas C
Toliau pateikiamas žingsnis po žingsnio vadovas, kaip įgyvendinti a Dvejetainis medis C.
1 veiksmas: paskelbkite dvejetainį paieškos medį
Sukurkite struktūros mazgą, kuriame yra trijų tipų duomenys, pvz., duomenys, *left_child ir *right_child, kur duomenys gali būti sveikojo skaičiaus tipo, o tiek *left_child, tiek *right_child mazgai gali būti paskelbti kaip NULL arba ne.
struktūra mazgas{
tarpt duomenis ;
struktūra mazgas * teisingas_vaikas ;
struktūra mazgas * kairysis_vaikas ;
} ;
2 veiksmas: sukurkite naujus mazgus dvejetainėje paieškos medyje
Sukurkite naują mazgą sukurdami funkciją, kuri priima sveikąjį skaičių kaip argumentą ir pateikia žymeklį į naują mazgą, sukurtą naudojant tą reikšmę. Naudokite malloc() funkciją C, kad sukurtumėte dinamišką atminties paskirstymą sukurtam mazgui. Inicijuokite kairįjį ir dešinįjį antrinius elementus į NULL ir grąžinkite nodeName.
struktūra mazgas * sukurti ( duomenų tipo duomenys )
{
struktūra mazgas * mazgoPavadinimas = malloc ( dydis ( struktūra mazgas ) ) ;
mazgoPavadinimas -> duomenis = vertė ;
mazgoPavadinimas -> kairysis_vaikas = mazgoPavadinimas -> teisingas_vaikas = NULL ;
grąžinti mazgoPavadinimas ;
}
3 veiksmas: į dvejetainį medį įdėkite dešinįjį ir kairįjį vaikus
Sukurkite funkcijas insert_left ir insert_right, kurios priims dvi įvestis, kurios yra įterpiama reikšmė ir žymeklis į mazgą, prie kurio bus prijungti abu vaikai. Iškvieskite kūrimo funkciją, kad sukurtumėte naują mazgą ir grąžintą žymeklį priskirtumėte kairiojo antrinio elemento kairiajam žymekliui arba dešiniajam pagrindinio pirminio elemento dešiniajam antriniam žymekliui.
struktūra mazgas * įterpti_kairėje ( struktūra mazgas * šaknis , duomenų tipo duomenys ) {šaknis -> paliko = sukurti ( duomenis ) ;
grąžinti šaknis -> paliko ;
}
struktūra mazgas * įterpti_dešinė ( struktūra mazgas * šaknis , duomenų tipo duomenys ) {
šaknis -> teisingai = sukurti ( duomenis ) ;
grąžinti šaknis -> teisingai ;
}
4 veiksmas: parodykite dvejetainio medžio mazgus naudodami perėjimo metodus
Mes galime rodyti medžius naudodami tris perėjimo būdus C. Šie perėjimo metodai yra:
1: Išankstinis užsakymas
Taikant šį perėjimo metodą, mes eisime per mazgus kryptimi nuo tėvų_mazgas->kairysis_vaikas->dešinysis_vaikas .
tuštuma išankstinis užsakymas ( mazgas * šaknis ) {jeigu ( šaknis ) {
printf ( „%d \n “ , šaknis -> duomenis ) ;
display_pre_order ( šaknis -> paliko ) ;
display_pre_order ( šaknis -> teisingai ) ;
}
}
2: apvažiavimas po užsakymo
Taikant šį perėjimo metodą, mes eisime per mazgus kryptimi nuo kairysis_vaikas->dešinysis_vaikas->parent_mazgas-> .
tuštuma display_post_order ( mazgas * šaknis ) {jeigu ( dvejetainis_medis ) {
display_post_order ( šaknis -> paliko ) ;
display_post_order ( šaknis -> teisingai ) ;
printf ( „%d \n “ , šaknis -> duomenis ) ;
}
}
3: važiavimas pagal užsakymą
Taikant šį perėjimo metodą, mes eisime per mazgus kryptimi nuo kairysis_mazgas->root_child->right_child .
tuštuma rodyti_tvarkoje ( mazgas * šaknis ) {jeigu ( dvejetainis_medis ) {
rodyti_tvarkoje ( šaknis -> paliko ) ;
printf ( „%d \n “ , šaknis -> duomenis ) ;
rodyti_tvarkoje ( šaknis -> teisingai ) ;
}
}
5 veiksmas: ištrinkite dvejetainiame medyje
Sukurtus galime ištrinti Dvejetainis medis ištrindami abu vaikus, turinčius pagrindinio mazgo funkciją C, kaip nurodyta toliau.
tuštuma ištrinti_t ( mazgas * šaknis ) {jeigu ( šaknis ) {
ištrinti_t ( šaknis -> paliko ) ;
ištrinti_t ( šaknis -> teisingai ) ;
Laisvas ( šaknis ) ;
}
}
C Dvejetainės paieškos medžio programa
Toliau pateikiamas visas dvejetainio paieškos medžio įgyvendinimas C programavimuose:
#include#include
struktūra mazgas {
tarpt vertė ;
struktūra mazgas * paliko , * teisingai ;
} ;
struktūra mazgas * mazgas1 ( tarpt duomenis ) {
struktūra mazgas * tmp = ( struktūra mazgas * ) malloc ( dydis ( struktūra mazgas ) ) ;
tmp -> vertė = duomenis ;
tmp -> paliko = tmp -> teisingai = NULL ;
grąžinti tmp ;
}
tuštuma spausdinti ( struktūra mazgas * šakninis_mazgas ) // rodomi mazgai!
{
jeigu ( šakninis_mazgas != NULL ) {
spausdinti ( šakninis_mazgas -> paliko ) ;
printf ( „%d \n “ , šakninis_mazgas -> vertė ) ;
spausdinti ( šakninis_mazgas -> teisingai ) ;
}
}
struktūra mazgas * įterpti_mazgas ( struktūra mazgas * mazgas , tarpt duomenis ) // įterpiant mazgus!
{
jeigu ( mazgas == NULL ) grąžinti mazgas1 ( duomenis ) ;
jeigu ( duomenis < mazgas -> vertė ) {
mazgas -> paliko = įterpti_mazgas ( mazgas -> paliko , duomenis ) ;
} Kitas jeigu ( duomenis > mazgas -> vertė ) {
mazgas -> teisingai = įterpti_mazgas ( mazgas -> teisingai , duomenis ) ;
}
grąžinti mazgas ;
}
tarpt pagrindinis ( ) {
printf ( Dvejetainės paieškos medžio C diegimas! \n \n “ ) ;
struktūra mazgas * tėvas = NULL ;
tėvas = įterpti_mazgas ( tėvas , 10 ) ;
įterpti_mazgas ( tėvas , 4 ) ;
įterpti_mazgas ( tėvas , 66 ) ;
įterpti_mazgas ( tėvas , Keturi. Penki ) ;
įterpti_mazgas ( tėvas , 9 ) ;
įterpti_mazgas ( tėvas , 7 ) ;
spausdinti ( tėvas ) ;
grąžinti 0 ;
}
Aukščiau pateiktame kode pirmiausia deklaruojame a mazgas naudojant struktūra . Tada inicijuojame naują mazgą kaip ' mazgas1 “ ir dinamiškai paskirstykite atmintį naudodami malloc () C su duomenimis ir dviem rodyklėmis įveskite vaikus naudodami deklaruotą mazgą. Po to rodome mazgą by printf() funkciją ir iškvieskite ją į pagrindinis () funkcija. Tada įterpimo_mazgas() sukuriama funkcija, kur jei mazgo duomenys yra NULL, tada mazgas1 yra pašalintas, kitu atveju duomenys patalpinami mazgas kairiojo ir dešiniojo vaiko (tėvas). Programa pradeda vykdyti nuo pagrindinis () funkcija, kuri sugeneruoja mazgą naudodama kelis pavyzdinius mazgus kaip vaikus, o tada naudoja In-Order traversal metodus, kad išspausdintų mazgo turinį.
Išvestis
Išvada
Medžiai dažnai naudojami duomenims nelinijinėje formoje laikyti. Dvejetainiai medžiai yra medžių tipai, kuriuose kiekvienas mazgas (tėvas) turi du palikuonis kairįjį vaiką ir dešinįjį vaiką. A dvejetainis medis yra universalus duomenų perdavimo ir saugojimo būdas. Jis yra efektyvesnis, palyginti su susietu sąrašu C. Pirmiau pateiktame straipsnyje mes matėme sąvoką Dvejetainis medis žingsnis po žingsnio įgyvendinant a Dvejetainis paieškos medis C.