Binárny strom v C
V C, a binárny strom je inštanciou stromovej dátovej štruktúry s nadradeným uzlom, ktorý môže vlastniť maximálny počet dvoch dcérskych uzlov; 0, 1 alebo 2 uzly potomkov. Každý jeden uzol v a binárny strom má vlastnú hodnotu a dva ukazovatele na svoje deti, jeden ukazovateľ pre ľavé dieťa a druhý pre pravé dieťa.
Deklarácia binárneho stromu
A binárny strom možno deklarovať v C pomocou objektu s názvom štrukturovať ktorý zobrazuje jeden z uzlov v strome.
štrukturovať uzol {
dátový typ var_name ;
štrukturovať uzol * vľavo ;
štrukturovať uzol * správny ;
} ;
Vyššie je uvedené vyhlásenie jedného binárny strom názov uzla ako uzol. Má tri hodnoty; jedna je premenná na ukladanie údajov a ďalšie dve sú ukazovatele na dieťa. (ľavý a pravý potomok nadradeného uzla).
Fakty binárneho stromu
Dokonca aj pre veľké súbory údajov pomocou a binárny strom uľahčuje a zrýchľuje vyhľadávanie. Počet vetiev stromu nie je obmedzený. Na rozdiel od poľa môžu byť stromy akéhokoľvek druhu vyrobené a zväčšené na základe toho, čo sa od jednotlivca vyžaduje.
Implementácia binárneho stromu v C
Nasleduje podrobný návod na implementáciu a Binárny strom v C.
Krok 1: Deklarujte binárny vyhľadávací strom
Vytvorte štruktúrny uzol, ktorý má tri typy údajov, ako sú údaje, *left_child a *right_child, pričom údaje môžu byť celočíselného typu a uzly *left_child a *right_child môžu byť deklarované ako NULL alebo nie.
štrukturovať uzol{
int údajov ;
štrukturovať uzol * pravé_dieťa ;
štrukturovať uzol * ľavé_dieťa ;
} ;
Krok 2: Vytvorte nové uzly v strome binárneho vyhľadávania
Vytvorte nový uzol vytvorením funkcie, ktorá akceptuje celé číslo ako argument a poskytne ukazovateľ na nový uzol vytvorený s touto hodnotou. Na dynamickú alokáciu pamäte pre vytvorený uzol použite funkciu malloc() v jazyku C. Inicializujte ľavý a pravý potomok na hodnotu NULL a vráťte nodeName.
štrukturovať uzol * vytvoriť ( dátový typ údajov )
{
štrukturovať uzol * nodeName = malloc ( veľkosť ( štrukturovať uzol ) ) ;
nodeName -> údajov = hodnotu ;
nodeName -> ľavé_dieťa = nodeName -> pravé_dieťa = NULOVÝ ;
vrátiť nodeName ;
}
Krok 3: Vložte pravé a ľavé dieťa do binárneho stromu
Vytvorte funkcie insert_left a insert_right, ktoré budú akceptovať dva vstupy, ktorými sú hodnota, ktorá sa má vložiť, a ukazovateľ na uzol, ku ktorému budú pripojené obe deti. Zavolaním funkcie create vytvorte nový uzol a priraďte vrátený ukazovateľ ľavému ukazovateľu ľavého potomka alebo pravému ukazovateľu pravého potomka koreňového rodiča.
štrukturovať uzol * vložiť_vľavo ( štrukturovať uzol * koreň , dátový typ údajov ) {koreň -> vľavo = vytvoriť ( údajov ) ;
vrátiť koreň -> vľavo ;
}
štrukturovať uzol * vložiť_vpravo ( štrukturovať uzol * koreň , dátový typ údajov ) {
koreň -> správny = vytvoriť ( údajov ) ;
vrátiť koreň -> správny ;
}
Krok 4: Zobrazte uzly binárneho stromu pomocou metód prechodu
Stromy môžeme zobraziť pomocou troch metód prechodu v jazyku C. Tieto metódy prechodu sú:
1: Prechod predobjednávky
Pri tejto metóde prechodu prejdeme uzlami v smere od parent_node->left_child->right_child .
neplatné predobjednať ( uzol * koreň ) {ak ( koreň ) {
printf ( '%d \n ' , koreň -> údajov ) ;
display_pre_order ( koreň -> vľavo ) ;
display_pre_order ( koreň -> správny ) ;
}
}
2: Prechod po objednávke
Pri tejto metóde prechodu prejdeme uzlami v smere od ľavé_dieťa->pravé_dieťa->rodičovský_uzol-> .
neplatné display_post_order ( uzol * koreň ) {ak ( binárny_strom ) {
display_post_order ( koreň -> vľavo ) ;
display_post_order ( koreň -> správny ) ;
printf ( '%d \n ' , koreň -> údajov ) ;
}
}
3: Priebeh v poradí
Pri tejto metóde prechodu prejdeme uzlami v smere od ľavý_uzol->root_child->right_child .
neplatné display_in_order ( uzol * koreň ) {ak ( binárny_strom ) {
display_in_order ( koreň -> vľavo ) ;
printf ( '%d \n ' , koreň -> údajov ) ;
display_in_order ( koreň -> správny ) ;
}
}
Krok 5: Vykonajte vymazanie v binárnom strome
Vytvorené môžeme vymazať Binárny strom odstránením oboch potomkov s funkciou nadradeného uzla v C nasledovne.
neplatné delete_t ( uzol * koreň ) {ak ( koreň ) {
delete_t ( koreň -> vľavo ) ;
delete_t ( koreň -> správny ) ;
zadarmo ( koreň ) ;
}
}
C Program binárneho vyhľadávacieho stromu
Nasleduje úplná implementácia binárneho vyhľadávacieho stromu v programovaní C:
#include#include
štrukturovať uzol {
int hodnotu ;
štrukturovať uzol * vľavo , * správny ;
} ;
štrukturovať uzol * uzol1 ( int údajov ) {
štrukturovať uzol * tmp = ( štrukturovať uzol * ) malloc ( veľkosť ( štrukturovať uzol ) ) ;
tmp -> hodnotu = údajov ;
tmp -> vľavo = tmp -> správny = NULOVÝ ;
vrátiť tmp ;
}
neplatné vytlačiť ( štrukturovať uzol * root_node ) // zobrazenie uzlov!
{
ak ( root_node != NULOVÝ ) {
vytlačiť ( root_node -> vľavo ) ;
printf ( '%d \n ' , root_node -> hodnotu ) ;
vytlačiť ( root_node -> správny ) ;
}
}
štrukturovať uzol * insert_node ( štrukturovať uzol * uzol , int údajov ) // vkladanie uzlov!
{
ak ( uzol == NULOVÝ ) vrátiť uzol1 ( údajov ) ;
ak ( údajov < uzol -> hodnotu ) {
uzol -> vľavo = insert_node ( uzol -> vľavo , údajov ) ;
} inak ak ( údajov > uzol -> hodnotu ) {
uzol -> správny = insert_node ( uzol -> správny , údajov ) ;
}
vrátiť uzol ;
}
int Hlavná ( ) {
printf ( 'Implementácia binárneho vyhľadávacieho stromu v jazyku C! \n \n ' ) ;
štrukturovať uzol * rodič = NULOVÝ ;
rodič = insert_node ( rodič , 10 ) ;
insert_node ( rodič , 4 ) ;
insert_node ( rodič , 66 ) ;
insert_node ( rodič , Štyri, päť ) ;
insert_node ( rodič , 9 ) ;
insert_node ( rodič , 7 ) ;
vytlačiť ( rodič ) ;
vrátiť 0 ;
}
Vo vyššie uvedenom kóde najprv deklarujeme a uzol použitím štrukturovať . Potom inicializujeme nový uzol ako „ uzol1 “ a dynamicky alokovať pamäť pomocou malloc() v C s údajmi a dvoma ukazovateľmi typu deti pomocou deklarovaného uzla. Potom zobrazíme uzol podľa printf() funkciu a zavolajte ju v Hlavná() funkciu. Potom insertion_node() je vytvorená funkcia, kde ak sú údaje uzla NULL, potom uzol1 je vyradený, inak sa údaje umiestnia do uzol (rodič) ľavého a pravého dieťaťa. Program sa spustí od Hlavná() funkcia, ktorá generuje uzol pomocou niekoľkých vzorových uzlov ako deti a potom používa metódy In-Order traversal na tlač obsahu uzla.
Výkon
Záver
Stromy sa často používajú na uchovávanie údajov v nelineárnej forme. Binárne stromy sú typy stromov, kde každý uzol (rodič) má dvoch potomkov ľavé dieťa a pravé dieťa. A binárny strom je všestranný spôsob prenosu a ukladania údajov. Je efektívnejší v porovnaní s Linked-List v C. Vo vyššie uvedenom článku sme videli koncept a Binárny strom s postupnou implementáciou a Binárny vyhľadávací strom v C.