Binární strom v C
V C, a binární strom je instancí stromové datové struktury s nadřazeným uzlem, který může mít maximální počet dvou podřízených uzlů; 0, 1 nebo 2 potomkové uzly. Každý jednotlivý uzel v a binární strom má vlastní hodnotu a dva ukazatele na své potomky, jeden ukazatel pro levé dítě a druhý pro pravé dítě.
Deklarace binárního stromu
A binární strom lze deklarovat v C pomocí objektu nazvaného strukturovat který znázorňuje jeden z uzlů ve stromu.
strukturovat uzel {
datový typ var_name ;
strukturovat uzel * vlevo, odjet ;
strukturovat uzel * že jo ;
} ;
Výše je prohlášení jednoho binární strom název uzlu jako uzel. Drží tři hodnoty; jedna je proměnná pro ukládání dat a další dvě jsou ukazatele na potomka. (levý a pravý potomek nadřazeného uzlu).
Fakta binárního stromu
I pro velké soubory dat pomocí a binární strom usnadňuje a urychluje vyhledávání. Počet větví stromů není omezen. Na rozdíl od pole mohou být stromy jakéhokoli druhu vytvořeny a zvětšeny na základě toho, co je požadováno od jednotlivce.
Implementace binárního stromu v C
Následuje podrobný návod k implementaci a Binární strom v C.
Krok 1: Deklarujte binární vyhledávací strom
Vytvořte uzel struktury, který má tři typy dat, jako jsou data, *left_child a *right_child, kde data mohou být celočíselného typu a uzly *left_child a *right_child mohou být deklarovány jako NULL nebo ne.
strukturovat uzel{
int data ;
strukturovat uzel * pravé_dítě ;
strukturovat uzel * levé_dítě ;
} ;
Krok 2: Vytvořte nové uzly ve stromu binárního vyhledávání
Vytvořte nový uzel vytvořením funkce, která přijímá celé číslo jako argument a poskytuje ukazatel na nový uzel vytvořený s touto hodnotou. Použijte funkci malloc() v C pro dynamickou alokaci paměti pro vytvořený uzel. Inicializujte levý a pravý potomek na hodnotu NULL a vraťte název nodeName.
strukturovat uzel * vytvořit ( datového typu )
{
strukturovat uzel * nodeName = malloc ( velikost ( strukturovat uzel ) ) ;
nodeName -> data = hodnota ;
nodeName -> levé_dítě = nodeName -> pravé_dítě = NULA ;
vrátit se nodeName ;
}
Krok 3: Vložte pravé a levé dítě do binárního stromu
Vytvořte funkce insert_left a insert_right, které přijmou dva vstupy, kterými jsou vložená hodnota a ukazatel na uzel, ke kterému budou připojeny oba potomci. Voláním funkce create vytvořte nový uzel a přiřaďte vrácený ukazatel levému ukazateli levého potomka nebo pravému ukazateli pravého potomka kořenového rodiče.
strukturovat uzel * insert_left ( strukturovat uzel * vykořenit , datového typu ) {vykořenit -> vlevo, odjet = vytvořit ( data ) ;
vrátit se vykořenit -> vlevo, odjet ;
}
strukturovat uzel * insert_right ( strukturovat uzel * vykořenit , datového typu ) {
vykořenit -> že jo = vytvořit ( data ) ;
vrátit se vykořenit -> že jo ;
}
Krok 4: Zobrazení uzlů binárního stromu pomocí metod procházení
Stromy můžeme zobrazit pomocí tří metod procházení v C. Tyto metody procházení jsou:
1: Přechod předobjednávky
V této metodě procházení budeme procházet uzly ve směru od parent_uzel->left_child->right_child .
prázdnota předobjednávka ( uzel * vykořenit ) {-li ( vykořenit ) {
printf ( '%d \n ' , vykořenit -> data ) ;
display_pre_order ( vykořenit -> vlevo, odjet ) ;
display_pre_order ( vykořenit -> že jo ) ;
}
}
2: Přechod po objednávce
V této metodě procházení budeme procházet uzly ve směru od levé_dítě->pravé_dítě->rodičovský_uzel-> .
prázdnota display_post_order ( uzel * vykořenit ) {-li ( binární_strom ) {
display_post_order ( vykořenit -> vlevo, odjet ) ;
display_post_order ( vykořenit -> že jo ) ;
printf ( '%d \n ' , vykořenit -> data ) ;
}
}
3: Průběh v pořadí
V této metodě procházení budeme procházet uzly ve směru od levý_uzel->root_child->right_child .
prázdnota display_in_order ( uzel * vykořenit ) {-li ( binární_strom ) {
display_in_order ( vykořenit -> vlevo, odjet ) ;
printf ( '%d \n ' , vykořenit -> data ) ;
display_in_order ( vykořenit -> že jo ) ;
}
}
Krok 5: Proveďte odstranění v binárním stromu
Vytvořené můžeme smazat Binární strom odstraněním obou potomků s funkcí rodičovského uzlu v C následovně.
prázdnota delete_t ( uzel * vykořenit ) {-li ( vykořenit ) {
delete_t ( vykořenit -> vlevo, odjet ) ;
delete_t ( vykořenit -> že jo ) ;
volný, uvolnit ( vykořenit ) ;
}
}
C Program binárního vyhledávacího stromu
Následuje kompletní implementace binárního vyhledávacího stromu v programování C:
#include#include
strukturovat uzel {
int hodnota ;
strukturovat uzel * vlevo, odjet , * že jo ;
} ;
strukturovat uzel * uzel1 ( int data ) {
strukturovat uzel * tmp = ( strukturovat uzel * ) malloc ( velikost ( strukturovat uzel ) ) ;
tmp -> hodnota = data ;
tmp -> vlevo, odjet = tmp -> že jo = NULA ;
vrátit se tmp ;
}
prázdnota tisk ( strukturovat uzel * kořenový_uzel ) // zobrazení uzlů!
{
-li ( kořenový_uzel != NULA ) {
tisk ( kořenový_uzel -> vlevo, odjet ) ;
printf ( '%d \n ' , kořenový_uzel -> hodnota ) ;
tisk ( kořenový_uzel -> že jo ) ;
}
}
strukturovat uzel * vložit_uzel ( strukturovat uzel * uzel , int data ) // vkládání uzlů!
{
-li ( uzel == NULA ) vrátit se uzel1 ( data ) ;
-li ( data < uzel -> hodnota ) {
uzel -> vlevo, odjet = vložit_uzel ( uzel -> vlevo, odjet , data ) ;
} jiný -li ( data > uzel -> hodnota ) {
uzel -> že jo = vložit_uzel ( uzel -> že jo , data ) ;
}
vrátit se uzel ;
}
int hlavní ( ) {
printf ( 'Implementace binárního vyhledávacího stromu v jazyce C! \n \n ' ) ;
strukturovat uzel * rodič = NULA ;
rodič = vložit_uzel ( rodič , 10 ) ;
vložit_uzel ( rodič , 4 ) ;
vložit_uzel ( rodič , 66 ) ;
vložit_uzel ( rodič , Čtyři pět ) ;
vložit_uzel ( rodič , 9 ) ;
vložit_uzel ( rodič , 7 ) ;
tisk ( rodič ) ;
vrátit se 0 ;
}
Ve výše uvedeném kódu nejprve deklarujeme a uzel použitím strukturovat . Poté inicializujeme nový uzel jako „ uzel1 ” a dynamicky alokovat paměť pomocí malloc() v C s daty a dvěma ukazateli zadejte děti pomocí deklarovaného uzlu. Poté zobrazíme uzel pomocí printf() funkci a zavolejte ji v hlavní() funkce. Potom insertion_node() je vytvořena funkce, kde pokud jsou data uzlu NULL, pak uzel1 je vyřazena, jinak jsou data umístěna v uzel (rodič) levého a pravého dítěte. Program se spustí od hlavní() funkce, která generuje uzel pomocí několika ukázkových uzlů jako potomků a poté používá metody In-Order traversal k tisku obsahu uzlu.
Výstup
Závěr
Stromy se často používají k uchovávání dat v nelineární formě. Binární stromy jsou typy stromů, kde každý uzel (rodič) má dva potomky levé dítě a pravé dítě. A binární strom je všestranný způsob přenosu a ukládání dat. Je efektivnější ve srovnání s Linked-List v C. Ve výše uvedeném článku jsme viděli koncept a Binární strom s postupnou implementací a Binární vyhledávací strom v C.