Binaire boom in C
In C, een binaire boom is een instantie van een boomgegevensstructuur met een bovenliggend knooppunt dat maximaal twee onderliggende knooppunten kan hebben; 0, 1 of 2 nakomelingen. Elk knooppunt in een binaire boom heeft een eigen waarde en twee wijzers naar zijn kinderen, een wijzer voor het linkerkind en de andere voor het rechterkind.
Verklaring van binaire boom
A binaire boom kan worden gedeclareerd in C met behulp van een object genaamd structuur dat een van de knooppunten in de boom weergeeft.
structuur knooppunt {
gegevenstype var_naam ;
structuur knooppunt * links ;
structuur knooppunt * rechts ;
} ;
Hierboven is een verklaring van een binaire boom knooppuntnaam als een knooppunt. Het bevat drie waarden; de ene is de gegevensopslagvariabele en de andere twee zijn de verwijzingen naar het kind. (linker en rechter kind van het bovenliggende knooppunt).
Feiten van binaire boom
Zelfs voor grote sets gegevens, met behulp van een binaire boom maakt het zoeken makkelijker en sneller. Het aantal boomtakken is niet beperkt. In tegenstelling tot een array kunnen alle soorten bomen worden gemaakt en vergroot op basis van wat van een individu wordt verlangd.
Binaire boomimplementatie in C
Het volgende is een stapsgewijze handleiding voor het implementeren van een Binaire boom in C.
Stap 1: Declareer een binaire zoekboom
Maak een struct-node die drie typen gegevens heeft, zoals data, *left_child en *right_child, waarbij gegevens van het type integer kunnen zijn, en zowel *left_child- als *right_child-nodes kunnen worden gedeclareerd als NULL of niet.
structuur knooppunt{
int gegevens ;
structuur knooppunt * rechts_kind ;
structuur knooppunt * linker_kind ;
} ;
Stap 2: maak nieuwe knooppunten in de binaire zoekboom
Maak een nieuw knooppunt door een functie te maken die een geheel getal als argument accepteert en de aanwijzer levert naar het nieuwe knooppunt dat met die waarde is gemaakt. Gebruik de functie malloc() in C voor dynamische geheugentoewijzing voor het gemaakte knooppunt. Initialiseer het linker en rechter kind naar NULL en geef de nodeName terug.
structuur knooppunt * creëren ( datatype gegevens )
{
structuur knooppunt * knooppuntNaam = malloc ( De grootte van ( structuur knooppunt ) ) ;
knooppuntNaam -> gegevens = waarde ;
knooppuntNaam -> linker_kind = knooppuntNaam -> rechts_kind = NUL ;
opbrengst knooppuntNaam ;
}
Stap 3: voeg de rechter- en linkerkinderen in de binaire boom in
Maak de functies insert_left en insert_right die twee invoer accepteren, namelijk de waarde die moet worden ingevoegd en de aanwijzer naar het knooppunt waarmee beide kinderen zullen worden verbonden. Roep de functie create aan om een nieuw knooppunt te maken en wijs de geretourneerde aanwijzer toe aan de linkeraanwijzer van het linkerkind of de rechteraanwijzer van het rechterkind van de hoofdouder.
structuur knooppunt * invoegen_links ( structuur knooppunt * wortel , datatype gegevens ) {wortel -> links = creëren ( gegevens ) ;
opbrengst wortel -> links ;
}
structuur knooppunt * invoegen_rechts ( structuur knooppunt * wortel , datatype gegevens ) {
wortel -> rechts = creëren ( gegevens ) ;
opbrengst wortel -> rechts ;
}
Stap 4: Toon knooppunten van binaire boom met behulp van traversal-methoden
We kunnen bomen weergeven door drie traversal-methoden te gebruiken in C. Deze traversal-methoden zijn:
1: Vooraf bestellen
Bij deze traversal-methode gaan we door de knooppunten in een richting van parent_node->left_child->right_child .
leegte voorafgaande bestelling ( knooppunt * wortel ) {als ( wortel ) {
printf ( '%D \N ' , wortel -> gegevens ) ;
toon_pre_order ( wortel -> links ) ;
toon_pre_order ( wortel -> rechts ) ;
}
}
2: Traversal na bestelling
Bij deze traversal-methode gaan we door de knooppunten in een richting van de left_child->right_child->parent_node-> .
leegte display_post_order ( knooppunt * wortel ) {als ( binaire_boom ) {
display_post_order ( wortel -> links ) ;
display_post_order ( wortel -> rechts ) ;
printf ( '%D \N ' , wortel -> gegevens ) ;
}
}
3: In-Order Traversal
Bij deze traversal-methode gaan we door de knooppunten in een richting van left_node->root_child->right_child .
leegte display_in_order ( knooppunt * wortel ) {als ( binaire_boom ) {
display_in_order ( wortel -> links ) ;
printf ( '%D \N ' , wortel -> gegevens ) ;
display_in_order ( wortel -> rechts ) ;
}
}
Stap 5: voer verwijdering uit in binaire boom
We kunnen het gemaakte verwijderen Binaire boom door beide kinderen met de bovenliggende knooppuntfunctie in C als volgt te verwijderen.
leegte delete_t ( knooppunt * wortel ) {als ( wortel ) {
delete_t ( wortel -> links ) ;
delete_t ( wortel -> rechts ) ;
vrij ( wortel ) ;
}
}
C Programma van binaire zoekboom
Het volgende is de volledige implementatie van de binaire zoekboom in C-programmering:
#include#include
structuur knooppunt {
int waarde ;
structuur knooppunt * links , * rechts ;
} ;
structuur knooppunt * knooppunt1 ( int gegevens ) {
structuur knooppunt * tmp = ( structuur knooppunt * ) malloc ( De grootte van ( structuur knooppunt ) ) ;
tmp -> waarde = gegevens ;
tmp -> links = tmp -> rechts = NUL ;
opbrengst tmp ;
}
leegte afdrukken ( structuur knooppunt * root_node ) // de knooppunten weergeven!
{
als ( root_node != NUL ) {
afdrukken ( root_node -> links ) ;
printf ( '%D \N ' , root_node -> waarde ) ;
afdrukken ( root_node -> rechts ) ;
}
}
structuur knooppunt * insert_node ( structuur knooppunt * knooppunt , int gegevens ) // knopen invoegen!
{
als ( knooppunt == NUL ) opbrengst knooppunt1 ( gegevens ) ;
als ( gegevens < knooppunt -> waarde ) {
knooppunt -> links = insert_node ( knooppunt -> links , gegevens ) ;
} anders als ( gegevens > knooppunt -> waarde ) {
knooppunt -> rechts = insert_node ( knooppunt -> rechts , gegevens ) ;
}
opbrengst knooppunt ;
}
int voornaamst ( ) {
printf ( 'C-implementatie van Binary Search Tree! \N \N ' ) ;
structuur knooppunt * ouder = NUL ;
ouder = insert_node ( ouder , 10 ) ;
insert_node ( ouder , 4 ) ;
insert_node ( ouder , 66 ) ;
insert_node ( ouder , Vier vijf ) ;
insert_node ( ouder , 9 ) ;
insert_node ( ouder , 7 ) ;
afdrukken ( ouder ) ;
opbrengst 0 ;
}
In de bovenstaande code declareren we eerst a knooppunt gebruik makend van structuur . Vervolgens initialiseren we een nieuw knooppunt als ' knooppunt1 ” en wijs geheugen dynamisch toe met behulp van malloc() in C met gegevens en twee aanwijzers type kinderen met behulp van het gedeclareerde knooppunt. Hierna tonen we het knooppunt door printf() functie en noem het in de voornaamst() functie. Dan de insertion_node() functie wordt gemaakt, waarbij als knooppuntgegevens NULL zijn, dan knooppunt1 is gepensioneerd, anders worden gegevens in de knooppunt (ouder) van het linker en rechter kind. Het programma start de uitvoering vanaf het voornaamst() functie, die een knooppunt genereert met behulp van een paar voorbeeldknooppunten als kinderen en vervolgens In-Order traversal-methoden gebruikt om de inhoud van het knooppunt af te drukken.
Uitgang
Conclusie
Bomen worden vaak gebruikt om gegevens in een niet-lineaire vorm te houden. Binaire bomen zijn soorten bomen waarbij elk knooppunt (ouder) twee nakomelingen heeft, het linkerkind en het rechterkind. A binaire boom is een veelzijdige methode voor het overdragen en opslaan van gegevens. Het is efficiënter in vergelijking met Linked-List in C. In het bovenstaande artikel hebben we het concept van a gezien Binaire boom met de stapsgewijze implementatie van a Binaire zoekboom in C.