Binärt träd i C
I C, a binärt träd är en instans av en träddatastruktur med en överordnad nod som kan ha ett maximalt antal av två underordnade noder; 0, 1 eller 2 avkommor noder. Varje enskild nod i en binärt träd har ett eget värde och två pekare till sina barn, en pekare för det vänstra barnet och den andra för det högra barnet.
Deklaration av binärt träd
A binärt träd kan deklareras i C med hjälp av ett objekt som kallas struktur som visar en av noderna i trädet.
struktur nod {
datatyp var_namn ;
struktur nod * vänster ;
struktur nod * höger ;
} ;
Ovan är en deklaration av en binärt träd nodnamn som en nod. Den har tre värden; en är den datalagringsvariabel och de andra två är pekare till barnet. (vänster och höger underordnat av föräldernoden).
Fakta om binärt träd
Även för stora uppsättningar data kan du använda en binärt träd gör sökningen enklare och snabbare. Antalet trädgrenar är inte begränsat. Till skillnad från en array kan träd av alla slag göras och utökas utifrån vad som krävs av en individ.
Binär trädimplementering i C
Följande är en steg-för-steg-guide för att implementera en Binärt träd i C.
Steg 1: Deklarera ett binärt sökträd
Skapa en strukturnod som har tre typer av data, såsom data, *left_child och *right_child, där data kan vara av heltalstyp och både *left_child och *right_child noder kan deklareras som NULL eller inte.
struktur nod{
int data ;
struktur nod * höger_barn ;
struktur nod * vänster_barn ;
} ;
Steg 2: Skapa nya noder i binärt sökträd
Skapa en ny nod genom att skapa en funktion som accepterar ett heltal som ett argument och ger pekaren till den nya noden som skapats med det värdet. Använd malloc()-funktionen i C för dynamisk minnesallokering för den skapade noden. Initiera vänster och höger barn till NULL och returnera nodeName.
struktur nod * skapa ( datatypsdata )
{
struktur nod * nodnamn = malloc ( storlek av ( struktur nod ) ) ;
nodnamn -> data = värde ;
nodnamn -> vänster_barn = nodnamn -> höger_barn = NULL ;
lämna tillbaka nodnamn ;
}
Steg 3: Infoga höger och vänster barn i binärt träd
Skapa funktionerna insert_left och insert_right som accepterar två ingångar, som är värdet som ska infogas och pekaren till noden som båda barnen ska kopplas till. Anropa skapa-funktionen för att skapa en ny nod och tilldela den returnerade pekaren till vänster pekare på det vänstra barnet eller den högra pekaren på det högra underordnade underordet.
struktur nod * infoga_vänster ( struktur nod * rot , datatypsdata ) {rot -> vänster = skapa ( data ) ;
lämna tillbaka rot -> vänster ;
}
struktur nod * insert_right ( struktur nod * rot , datatypsdata ) {
rot -> höger = skapa ( data ) ;
lämna tillbaka rot -> höger ;
}
Steg 4: Visa noder för binärt träd med hjälp av genomgångsmetoder
Vi kan visa träd genom att använda tre metoder för traversering i C. Dessa traverseringsmetoder är:
1: Förbeställ genomgång
I denna traverseringsmetod kommer vi att gå igenom noderna i en riktning från föräldernod->vänster_barn->höger_barn .
tomhet förboka ( nod * rot ) {om ( rot ) {
printf ( '%d \n ' , rot -> data ) ;
display_pre_order ( rot -> vänster ) ;
display_pre_order ( rot -> höger ) ;
}
}
2: Genomgång efter beställning
I denna traverseringsmetod kommer vi att gå igenom noderna i en riktning från vänster_barn->höger_barn->föräldernod-> .
tomhet display_post_order ( nod * rot ) {om ( binärt_träd ) {
display_post_order ( rot -> vänster ) ;
display_post_order ( rot -> höger ) ;
printf ( '%d \n ' , rot -> data ) ;
}
}
3: Genomgång i order
I denna traverseringsmetod kommer vi att gå igenom noderna i en riktning från left_node->root_child->right_child .
tomhet display_in_order ( nod * rot ) {om ( binärt_träd ) {
display_in_order ( rot -> vänster ) ;
printf ( '%d \n ' , rot -> data ) ;
display_in_order ( rot -> höger ) ;
}
}
Steg 5: Utför radering i binärt träd
Vi kan ta bort det skapade Binärt träd genom att ta bort båda barnen med föräldranodfunktionen i C enligt följande.
tomhet delete_t ( nod * rot ) {om ( rot ) {
delete_t ( rot -> vänster ) ;
delete_t ( rot -> höger ) ;
fri ( rot ) ;
}
}
C Program för binärt sökträd
Följande är den fullständiga implementeringen av binärt sökträd i C-programmering:
#include#include
struktur nod {
int värde ;
struktur nod * vänster , * höger ;
} ;
struktur nod * nod1 ( int data ) {
struktur nod * tmp = ( struktur nod * ) malloc ( storlek av ( struktur nod ) ) ;
tmp -> värde = data ;
tmp -> vänster = tmp -> höger = NULL ;
lämna tillbaka tmp ;
}
tomhet skriva ut ( struktur nod * rotnod ) // visar noderna!
{
om ( rotnod != NULL ) {
skriva ut ( rotnod -> vänster ) ;
printf ( '%d \n ' , rotnod -> värde ) ;
skriva ut ( rotnod -> höger ) ;
}
}
struktur nod * insert_node ( struktur nod * nod , int data ) // infogar noder!
{
om ( nod == NULL ) lämna tillbaka nod1 ( data ) ;
om ( data < nod -> värde ) {
nod -> vänster = insert_node ( nod -> vänster , data ) ;
} annan om ( data > nod -> värde ) {
nod -> höger = infoga_nod ( nod -> höger , data ) ;
}
lämna tillbaka nod ;
}
int huvud ( ) {
printf ( 'C implementering av Binary Search Tree! \n \n ' ) ;
struktur nod * förälder = NULL ;
förälder = infoga_nod ( förälder , 10 ) ;
infoga_nod ( förälder , 4 ) ;
infoga_nod ( förälder , 66 ) ;
infoga_nod ( förälder , Fyra fem ) ;
infoga_nod ( förälder , 9 ) ;
infoga_nod ( förälder , 7 ) ;
skriva ut ( förälder ) ;
lämna tillbaka 0 ;
}
I ovanstående kod deklarerar vi först a nod använder sig av struktur . Sedan initierar vi en ny nod som ' nod1 ” och allokera minne dynamiskt med hjälp av malloc() i C med data och två pekare skriv barn med den deklarerade noden. Efter detta visar vi noden efter printf() funktion och anropa den i main() fungera. Sedan insättningsnod() funktion skapas, där om noddata är NULL då nod1 är pensionerad, annars placeras data i nod (förälder) till vänster och höger barn. Programmet börjar köras från main() funktion, som genererar en nod som använder några exempelnoder som underordnade och sedan använder In-Order-traversalmetoder för att skriva ut nodens innehåll.
Produktion
Slutsats
Träd används ofta för att hålla data i en icke-linjär form. Binära träd är typer av träd där varje nod (förälder) har två avkommor, det vänstra barnet och det högra barnet. A binärt träd är en mångsidig metod för att överföra och lagra data. Det är mer effektivt jämfört med Linked-List i C. I artikeln ovan har vi sett konceptet med en Binärt träd med den steg-för-steg-implementering av en Binärt sökträd i C.