Binært træ i C
I C, a binært træ er en forekomst af en trædatastruktur med en overordnet node, der kan have et maksimalt antal på to underordnede noder; 0, 1 eller 2 afkom noder. Hver enkelt node i en binært træ har sin egen værdi og to pointer til sine børn, den ene til det venstre barn og den anden til det højre barn.
Erklæring om binært træ
EN binært træ kan erklæres i C ved hjælp af et objekt kaldet struktur der viser en af knudepunkterne i træet.
struktur node {
datatype var_navn ;
struktur node * venstre ;
struktur node * højre ;
} ;
Ovenfor er en erklæring af en binært træ nodenavn som en node. Den rummer tre værdier; den ene er den datalagringsvariabel, og de to andre er pejlemærkerne til barnet. (venstre og højre underordnede af forældreknudepunktet).
Fakta om binært træ
Selv for store datasæt, ved hjælp af en binært træ gør søgning lettere og hurtigere. Antallet af grene er ikke begrænset. I modsætning til et array kan træer af enhver art laves og øges baseret på, hvad der kræves af en person.
Binær træimplementering i C
Det følgende er en trin-for-trin guide til implementering af en Binært træ i C.
Trin 1: Erklær et binært søgetræ
Opret en strukturknude, der har tre typer data, såsom data, *left_child og *right_child, hvor data kan være af heltalstype, og både *left_child og *right_child noder kan erklæres som NULL eller ej.
struktur node{
int data ;
struktur node * højre_barn ;
struktur node * venstre_barn ;
} ;
Trin 2: Opret nye noder i binært søgetræ
Opret en ny node ved at oprette en funktion, der accepterer et heltal som et argument og giver markøren til den nye node, der er oprettet med denne værdi. Brug malloc()-funktionen i C til dynamisk hukommelsesallokering for den oprettede node. Initialiser venstre og højre underordnede til NULL og returner nodeName.
struktur node * skab ( datatype data )
{
struktur node * nodenavn = malloc ( størrelse på ( struktur node ) ) ;
nodenavn -> data = værdi ;
nodenavn -> venstre_barn = nodenavn -> højre_barn = NUL ;
Vend tilbage nodenavn ;
}
Trin 3: Indsæt højre og venstre børn i binært træ
Opret funktionerne insert_left og insert_right, der vil acceptere to input, som er den værdi, der skal indsættes, og markøren til den node, som begge børn vil blive forbundet til. Kald oprettelsesfunktionen for at oprette en ny node og tildele den returnerede markør til venstre markør til venstre underordnede eller højre markør til højre underordnede af rodforælderen.
struktur node * indsæt_venstre ( struktur node * rod , datatype data ) {rod -> venstre = skab ( data ) ;
Vend tilbage rod -> venstre ;
}
struktur node * indsæt_højre ( struktur node * rod , datatype data ) {
rod -> højre = skab ( data ) ;
Vend tilbage rod -> højre ;
}
Trin 4: Vis knudepunkter for binært træ ved hjælp af gennemgangsmetoder
Vi kan vise træer ved at bruge tre traverseringsmetoder i C. Disse traverseringsmetoder er:
1: Forudbestil gennemkørsel
I denne gennemløbsmetode vil vi gå gennem knudepunkterne i en retning fra parent_node->venstre_barn->højre_barn .
ugyldig forudbestille ( node * rod ) {hvis ( rod ) {
printf ( '%d \n ' , rod -> data ) ;
display_pre_order ( rod -> venstre ) ;
display_pre_order ( rod -> højre ) ;
}
}
2: Efterbestilling gennemkørsel
I denne gennemløbsmetode vil vi gå gennem noderne i en retning fra left_child->right_child->parent_node-> .
ugyldig display_post_order ( node * rod ) {hvis ( binært_træ ) {
display_post_order ( rod -> venstre ) ;
display_post_order ( rod -> højre ) ;
printf ( '%d \n ' , rod -> data ) ;
}
}
3: Gennemkørsel i ordre
I denne gennemløbsmetode vil vi gå gennem knudepunkterne i en retning fra left_node->root_child->right_child .
ugyldig display_in_order ( node * rod ) {hvis ( binært_træ ) {
display_in_order ( rod -> venstre ) ;
printf ( '%d \n ' , rod -> data ) ;
display_in_order ( rod -> højre ) ;
}
}
Trin 5: Udfør sletning i binært træ
Vi kan slette det oprettede Binært træ ved at slette begge børnene med forældreknudefunktionen i C som følger.
ugyldig delete_t ( node * rod ) {hvis ( rod ) {
delete_t ( rod -> venstre ) ;
delete_t ( rod -> højre ) ;
gratis ( rod ) ;
}
}
C Program for binært søgetræ
Følgende er den komplette implementering af binært søgetræ i C-programmering:
#include#include
struktur node {
int værdi ;
struktur node * venstre , * højre ;
} ;
struktur node * node 1 ( int data ) {
struktur node * tmp = ( struktur node * ) malloc ( størrelse på ( struktur node ) ) ;
tmp -> værdi = data ;
tmp -> venstre = tmp -> højre = NUL ;
Vend tilbage tmp ;
}
ugyldig Print ( struktur node * root_node ) // viser noderne!
{
hvis ( root_node != NUL ) {
Print ( root_node -> venstre ) ;
printf ( '%d \n ' , root_node -> værdi ) ;
Print ( root_node -> højre ) ;
}
}
struktur node * indsæt_node ( struktur node * node , int data ) // indsættelse af noder!
{
hvis ( node == NUL ) Vend tilbage node 1 ( data ) ;
hvis ( data < node -> værdi ) {
node -> venstre = indsæt_node ( node -> venstre , data ) ;
} andet hvis ( data > node -> værdi ) {
node -> højre = indsæt_node ( node -> højre , data ) ;
}
Vend tilbage node ;
}
int vigtigste ( ) {
printf ( 'C implementering af binært søgetræ! \n \n ' ) ;
struktur node * forælder = NUL ;
forælder = indsæt_node ( forælder , 10 ) ;
indsæt_node ( forælder , 4 ) ;
indsæt_node ( forælder , 66 ) ;
indsæt_node ( forælder , Fire, fem ) ;
indsæt_node ( forælder , 9 ) ;
indsæt_node ( forælder , 7 ) ;
Print ( forælder ) ;
Vend tilbage 0 ;
}
I ovenstående kode erklærer vi først en node ved brug af struktur . Så initialiserer vi en ny node som ' node 1 ” og allokere hukommelse dynamisk vha malloc() i C med data og to pointere skriv børn ved hjælp af den erklærede node. Herefter viser vi noden ved printf() funktion og kalde det i hoved() fungere. Derefter insertion_node() funktion oprettes, hvor hvis nodedata er NULL så node 1 er pensioneret, ellers placeres data i node (forælder) til venstre og højre barn. Programmet starter udførelse fra hoved() funktion, som genererer en node ved hjælp af nogle få prøveknuder som børn og derefter bruger In-Order traversal metoder til at udskrive nodeindholdet.
Produktion
Konklusion
Træer bruges ofte til at holde data i en ikke-lineær form. Binære træer er typer af træer, hvor hver knude (forælder) har to afkom, venstre barn og højre barn. EN binært træ er en alsidig metode til overførsel og lagring af data. Det er mere effektivt sammenlignet med Linked-List i C. I ovenstående artikel har vi set konceptet med en Binært træ med den trinvise implementering af en Binært søgetræ i C.