Binääripuu C-muodossa
C:ssä a binäärinen puu on ilmentymä puutietorakenteesta, jossa on yläsolmu, jolla voi olla enintään kaksi alisolmua; 0, 1 tai 2 jälkeläissolmua. Jokainen solmu kohdassa a binäärinen puu on oma arvonsa ja kaksi osoitinta lapsilleen, yksi osoitin vasemmalle ja toinen oikealle lapselle.
Binaaripuun julistus
A binäärinen puu voidaan ilmoittaa C:ssä käyttämällä objektia nimeltä struct joka kuvaa yhtä puun solmuista.
struct solmu {
tietotyyppi var_nimi ;
struct solmu * vasemmalle ;
struct solmu * oikein ;
} ;
Yllä on ilmoitus yhdestä binäärinen puu solmun nimi solmuna. Siinä on kolme arvoa; yksi on tietojen tallennusmuuttuja ja kaksi muuta ovat osoittimia lapsiin. (emosolmun vasen ja oikea lapsi).
Faktat binaaripuusta
Jopa suurille tietojoukoille käyttämällä a binäärinen puu tekee etsimisestä helpompaa ja nopeampaa. Puun oksien määrää ei ole rajoitettu. Päinvastoin kuin matriisi, kaikenlaisia puita voidaan tehdä ja kasvattaa sen mukaan, mitä yksilöltä vaaditaan.
Binaaripuun toteutus C:ssä
Seuraavassa on vaiheittaiset ohjeet a Binääripuu in C.
Vaihe 1: Ilmoita binäärihakupuu
Luo rakennesolmu, jossa on kolmen tyyppisiä tietoja, kuten data, *vasen_lapsi ja *oikea_lapsi, jossa tiedot voivat olla kokonaislukutyyppisiä ja sekä *vasen_lapsi- että *oikea_lapsisolmut voidaan ilmoittaa NULL-arvoiksi tai ei.
struct solmu{
int tiedot ;
struct solmu * oikea_lapsi ;
struct solmu * vasen_lapsi ;
} ;
Vaihe 2: Luo uusia solmuja binäärihakupuussa
Luo uusi solmu luomalla funktio, joka hyväksyy kokonaisluvun argumenttina ja tarjoaa osoittimen tällä arvolla luotuun uuteen solmuun. Käytä malloc()-funktiota C:ssä luodun solmun dynaamiseen muistin varaamiseen. Alusta vasen ja oikea lapsi NULL-arvoon ja palauta solmunNimi.
struct solmu * luoda ( tietotyypin tiedot )
{
struct solmu * solmunNimi = malloc ( koko ( struct solmu ) ) ;
solmunNimi -> tiedot = arvo ;
solmunNimi -> vasen_lapsi = solmunNimi -> oikea_lapsi = TYHJÄ ;
palata solmunNimi ;
}
Vaihe 3: Lisää oikea ja vasen lapsi binaaripuuhun
Luo funktiot insert_left ja insert_right, jotka hyväksyvät kaksi syötettä, jotka ovat lisättävä arvo ja osoitin solmuun, johon molemmat lapset yhdistetään. Kutsu luomistoiminto luodaksesi uuden solmun ja määritä palautettu osoitin juurivanhemman vasemman alatason vasemmalle osoittimelle tai oikean alatason osoittimelle.
struct solmu * insert_left ( struct solmu * juuri , tietotyypin tiedot ) {juuri -> vasemmalle = luoda ( tiedot ) ;
palata juuri -> vasemmalle ;
}
struct solmu * insert_right ( struct solmu * juuri , tietotyypin tiedot ) {
juuri -> oikein = luoda ( tiedot ) ;
palata juuri -> oikein ;
}
Vaihe 4: Näytä binääripuun solmut käyttämällä läpikulkumenetelmiä
Voimme näyttää puita käyttämällä kolmea C:n läpikulkumenetelmää. Nämä läpikulkutavat ovat:
1: Ennakkotilauksen läpikäynti
Tässä läpikulkumenetelmässä käymme solmujen läpi suuntaan alkaen vanhempi_solmu->vasen_lapsi->oikea_lapsi .
mitätön ennakkotilaus ( solmu * juuri ) {jos ( juuri ) {
printf ( '%d \n ' , juuri -> tiedot ) ;
display_pre_order ( juuri -> vasemmalle ) ;
display_pre_order ( juuri -> oikein ) ;
}
}
2: Tilauksen jälkeinen läpikäynti
Tässä läpikulkumenetelmässä käymme solmujen läpi suuntaan alkaen vasen_lapsi->oikea_lapsi->vanhempi_solmu-> .
mitätön display_post_order ( solmu * juuri ) {jos ( binaarinen_puu ) {
display_post_order ( juuri -> vasemmalle ) ;
display_post_order ( juuri -> oikein ) ;
printf ( '%d \n ' , juuri -> tiedot ) ;
}
}
3: Tilauksen läpikulku
Tässä läpikulkumenetelmässä käymme solmujen läpi suuntaan alkaen vasen_solmu->juurilapsi->oikea_lapsi .
mitätön näyttö_järjestyksessä ( solmu * juuri ) {jos ( binaarinen_puu ) {
näyttö_järjestyksessä ( juuri -> vasemmalle ) ;
printf ( '%d \n ' , juuri -> tiedot ) ;
näyttö_järjestyksessä ( juuri -> oikein ) ;
}
}
Vaihe 5: Suorita poisto binääripuussa
Voimme poistaa luodut Binääripuu poistamalla molemmat alat, joilla on pääsolmufunktio C:stä seuraavasti.
mitätön delete_t ( solmu * juuri ) {jos ( juuri ) {
delete_t ( juuri -> vasemmalle ) ;
delete_t ( juuri -> oikein ) ;
vapaa ( juuri ) ;
}
}
C Binaarihakupuun ohjelma
Seuraava on binaarihakupuun täydellinen toteutus C-ohjelmoinnissa:
#include#include
struct solmu {
int arvo ;
struct solmu * vasemmalle , * oikein ;
} ;
struct solmu * solmu1 ( int tiedot ) {
struct solmu * tmp = ( struct solmu * ) malloc ( koko ( struct solmu ) ) ;
tmp -> arvo = tiedot ;
tmp -> vasemmalle = tmp -> oikein = TYHJÄ ;
palata tmp ;
}
mitätön Tulosta ( struct solmu * root_node ) // näyttää solmut!
{
jos ( root_node != TYHJÄ ) {
Tulosta ( root_node -> vasemmalle ) ;
printf ( '%d \n ' , root_node -> arvo ) ;
Tulosta ( root_node -> oikein ) ;
}
}
struct solmu * insert_node ( struct solmu * solmu , int tiedot ) // solmujen lisääminen!
{
jos ( solmu == TYHJÄ ) palata solmu1 ( tiedot ) ;
jos ( tiedot < solmu -> arvo ) {
solmu -> vasemmalle = insert_node ( solmu -> vasemmalle , tiedot ) ;
} muu jos ( tiedot > solmu -> arvo ) {
solmu -> oikein = insert_node ( solmu -> oikein , tiedot ) ;
}
palata solmu ;
}
int pää ( ) {
printf ( 'Binaarihakupuun C toteutus! \n \n ' ) ;
struct solmu * vanhempi = TYHJÄ ;
vanhempi = insert_node ( vanhempi , 10 ) ;
insert_node ( vanhempi , 4 ) ;
insert_node ( vanhempi , 66 ) ;
insert_node ( vanhempi , Neljä viisi ) ;
insert_node ( vanhempi , 9 ) ;
insert_node ( vanhempi , 7 ) ;
Tulosta ( vanhempi ) ;
palata 0 ;
}
Yllä olevassa koodissa julistamme ensin a solmu käyttämällä struct . Sitten alustamme uuden solmun muodossa ' solmu1 ” ja varaa muistia dynaamisesti käyttämällä malloc() C:ssä datalla ja kahdella osoittimella kirjoitetaan lapsia käyttämällä ilmoitettua solmua. Tämän jälkeen näytämme solmun by printf() toiminto ja kutsu se sisään pää() toiminto. Sitten insertion_node() funktio luodaan, missä jos solmutiedot on NULL, niin solmu1 on eläkkeellä, muuten tiedot sijoitetaan solmu vasemman ja oikean lapsen (vanhempi). Ohjelma aloittaa suorittamisen kohdasta pää() -funktio, joka luo solmun käyttämällä muutamia esimerkkisolmuja lapsina ja käyttää sitten In-Order-läpikulkumenetelmiä solmun sisällön tulostamiseen.
Lähtö
Johtopäätös
Puita käytetään usein pitämään tiedot epälineaarisessa muodossa. Binääripuut ovat puutyyppejä, joissa jokaisella solmulla (vanhemmalla) on kaksi jälkeläistä, vasen lapsi ja oikea lapsi. A binäärinen puu on monipuolinen tapa siirtää ja tallentaa tietoja. Se on tehokkaampi verrattuna linkitettyyn luetteloon C:ssä. Yllä olevassa artikkelissa olemme nähneet käsitteen Binääripuu vaiheittaisella toteutuksella a Binäärihakupuu in C.