Binary Tree sa C
Sa C, a binary tree ay isang halimbawa ng istraktura ng data ng puno na may parent node na maaaring magkaroon ng maximum na bilang ng dalawang child node; 0, 1, o 2 offspring node. Ang bawat solong node sa a binary tree ay may sariling halaga at dalawang pointer sa mga anak nito, isang pointer para sa kaliwang bata at ang isa para sa kanang bata.
Deklarasyon ng Binary Tree
A binary tree ay maaaring ipahayag sa C gamit ang isang bagay na tinatawag struct na naglalarawan ng isa sa mga node sa puno.
struct node {
datatype var_name ;
struct node * umalis ;
struct node * tama ;
} ;
Sa itaas ay isang deklarasyon ng isa binary tree pangalan ng node bilang isang node. Ito ay nagtataglay ng tatlong halaga; ang isa ay ang data-storing variable at ang dalawa pa ay ang mga pointer sa bata. (kaliwa at kanang anak ng parent node).
Mga Katotohanan ng Binary Tree
Kahit na para sa malalaking set ng data, gamit ang a binary tree ginagawang mas madali at mas mabilis ang paghahanap. Ang bilang ng mga sanga ng puno ay hindi limitado. Sa kaibahan sa isang array, ang mga puno ng anumang uri ay maaaring gawin at dagdagan batay sa kung ano ang kinakailangan ng isang indibidwal.
Pagpapatupad ng Binary Tree sa C
Ang sumusunod ay isang hakbang-hakbang na gabay sa pagpapatupad ng a Binary Tree sa C.
Hakbang 1: Magdeklara ng Binary Search Tree
Gumawa ng struct node na may tatlong uri ng data, gaya ng data, *left_child, at *right_child, kung saan ang data ay maaaring integer type, at parehong *left_child at *right_child node ay maaaring ideklara bilang NULL o hindi.
struct node{
int datos ;
struct node * right_child ;
struct node * left_child ;
} ;
Hakbang 2: Gumawa ng Mga Bagong Node sa Binary Search Tree
Gumawa ng bagong node sa pamamagitan ng paggawa ng function na tumatanggap ng integer bilang argument at nagbibigay ng pointer sa bagong node na ginawa gamit ang value na iyon. Gamitin ang function na malloc() sa C para sa dynamic na paglalaan ng memorya para sa nilikhang node. I-initialize ang kaliwa at kanang bata sa NULL at ibalik ang nodeName.
struct node * lumikha ( datatype ng data )
{
struct node * nodeName = malloc ( sukat ng ( struct node ) ) ;
nodeName -> datos = halaga ;
nodeName -> left_child = nodeName -> right_child = WALA ;
bumalik nodeName ;
}
Hakbang 3: Ipasok ang Kanan at Kaliwang Bata sa Binary Tree
Lumikha ng mga function na insert_left at insert_right na tatanggap ng dalawang input, na kung saan ay ang halaga na ilalagay at ang pointer sa node kung saan ang parehong mga bata ay konektado. Tawagan ang create function upang lumikha ng bagong node at italaga ang ibinalik na pointer sa kaliwang pointer ng kaliwang anak o ang kanang pointer ng kanang anak ng root parent.
struct node * insert_left ( struct node * ugat , datatype ng data ) {ugat -> umalis = lumikha ( datos ) ;
bumalik ugat -> umalis ;
}
struct node * insert_right ( struct node * ugat , datatype ng data ) {
ugat -> tama = lumikha ( datos ) ;
bumalik ugat -> tama ;
}
Hakbang 4: Ipakita ang mga Node ng Binary Tree Gamit ang Traversal Methods
Maaari tayong magpakita ng mga puno sa pamamagitan ng paggamit ng tatlong paraan ng traversal sa C. Ang mga paraan ng traversal na ito ay:
1: Pre-Order Traversal
Sa pamamaraang ito ng traversal, dadaan tayo sa mga node sa direksyon mula sa parent_node->left_child->right_child .
walang bisa pre_order ( node * ugat ) {kung ( ugat ) {
printf ( '%d \n ' , ugat -> datos ) ;
display_pre_order ( ugat -> umalis ) ;
display_pre_order ( ugat -> tama ) ;
}
}
2: Post-Order Traversal
Sa ganitong paraan ng traversal, dadaan tayo sa mga node sa direksyon mula sa left_child->right_child->parent_node-> .
walang bisa display_post_order ( node * ugat ) {kung ( binary_tree ) {
display_post_order ( ugat -> umalis ) ;
display_post_order ( ugat -> tama ) ;
printf ( '%d \n ' , ugat -> datos ) ;
}
}
3: In-Order Traversal
Sa pamamaraang ito ng traversal, dadaan tayo sa mga node sa direksyon mula sa left_node->root_child->right_child .
walang bisa display_in_order ( node * ugat ) {kung ( binary_tree ) {
display_in_order ( ugat -> umalis ) ;
printf ( '%d \n ' , ugat -> datos ) ;
display_in_order ( ugat -> tama ) ;
}
}
Hakbang 5: Magsagawa ng Pagtanggal sa Binary Tree
Maaari naming tanggalin ang nilikha Binary Tree sa pamamagitan ng pagtanggal sa parehong mga bata na may parent node function sa C bilang mga sumusunod.
walang bisa delete_t ( node * ugat ) {kung ( ugat ) {
delete_t ( ugat -> umalis ) ;
delete_t ( ugat -> tama ) ;
libre ( ugat ) ;
}
}
C Program ng Binary Search Tree
Ang sumusunod ay ang kumpletong pagpapatupad ng Binary search tree sa C programming:
#include#include
struct node {
int halaga ;
struct node * umalis , * tama ;
} ;
struct node * node1 ( int datos ) {
struct node * tmp = ( struct node * ) malloc ( sukat ng ( struct node ) ) ;
tmp -> halaga = datos ;
tmp -> umalis = tmp -> tama = WALA ;
bumalik tmp ;
}
walang bisa print ( struct node * root_node ) // ipinapakita ang mga node!
{
kung ( root_node != WALA ) {
print ( root_node -> umalis ) ;
printf ( '%d \n ' , root_node -> halaga ) ;
print ( root_node -> tama ) ;
}
}
struct node * insert_node ( struct node * node , int datos ) // pagpasok ng mga node!
{
kung ( node == WALA ) bumalik node1 ( datos ) ;
kung ( datos < node -> halaga ) {
node -> umalis = insert_node ( node -> umalis , datos ) ;
} iba pa kung ( datos > node -> halaga ) {
node -> tama = insert_node ( node -> tama , datos ) ;
}
bumalik node ;
}
int pangunahing ( ) {
printf ( 'C pagpapatupad ng Binary Search Tree! \n \n ' ) ;
struct node * magulang = WALA ;
magulang = insert_node ( magulang , 10 ) ;
insert_node ( magulang , 4 ) ;
insert_node ( magulang , 66 ) ;
insert_node ( magulang , Apat. Lima ) ;
insert_node ( magulang , 9 ) ;
insert_node ( magulang , 7 ) ;
print ( magulang ) ;
bumalik 0 ;
}
Sa code sa itaas, una naming idineklara ang a node gamit struct . Pagkatapos ay sinisimulan namin ang isang bagong node bilang ' node1 ” at maglaan ng memorya sa pabago-bagong paggamit malloc() sa C na may data at dalawang pointer i-type ang mga bata gamit ang ipinahayag na node. Pagkatapos nito, ipinapakita namin ang node sa pamamagitan ng printf() function at tawagan ito sa pangunahing() function. Pagkatapos ay ang insertion_node() Ang function ay nilikha, kung saan kung ang data ng node ay NULL pagkatapos node1 ay nagretiro, kung hindi, ang data ay inilalagay sa node (magulang) ng kaliwa at kanang anak. Ang programa ay nagsisimula sa pagpapatupad mula sa pangunahing() function, na bumubuo ng node gamit ang ilang sample na node bilang mga bata at pagkatapos ay gumagamit ng In-Order traversal na pamamaraan upang i-print ang mga nilalaman ng node.
Output
Konklusyon
Ang mga puno ay madalas na ginagamit upang panatilihin ang data sa isang non-linear na anyo. Binary na mga puno ay mga uri ng puno kung saan ang bawat node (magulang) ay may dalawang supling ang kaliwang anak at ang kanang anak. A binary tree ay isang maraming nalalaman na paraan ng paglilipat at pag-iimbak ng data. Ito ay mas mahusay kumpara sa Linked-List sa C. Sa artikulo sa itaas, nakita natin ang konsepto ng a Binary Tree sa hakbang-hakbang na pagpapatupad ng a Binary Search Tree sa C.