Pokok Binari dalam C
Dalam C, a pokok binari ialah contoh struktur data pokok dengan nod induk yang mungkin mempunyai bilangan maksimum dua nod anak; 0, 1, atau 2 nod anak. Setiap nod tunggal dalam a pokok binari mempunyai nilai tersendiri dan dua penunjuk kepada anak-anaknya, satu penunjuk untuk anak kiri dan satu lagi untuk anak kanan.
Pengisytiharan Pokok Binari
A pokok binari boleh diisytiharkan dalam C menggunakan objek yang dipanggil struct yang menggambarkan salah satu nod dalam pokok.
struct nod {
jenis data var_name ;
struct nod * dibiarkan ;
struct nod * betul ;
} ;
Di atas adalah pengisytiharan satu pokok binari nama nod sebagai nod. Ia memegang tiga nilai; satu ialah pembolehubah penyimpanan data dan dua lagi adalah penunjuk kepada kanak-kanak. (anak kiri dan kanan nod induk).
Fakta Pokok Binari
Walaupun untuk set data yang besar, menggunakan a pokok binari menjadikan carian lebih mudah dan cepat. Bilangan dahan pokok tidak terhad. Berbeza dengan tatasusunan, sebarang jenis pokok boleh dibuat dan ditambah berdasarkan apa yang diperlukan oleh seseorang individu.
Pelaksanaan Pokok Binari dalam C
Berikut adalah panduan langkah demi langkah untuk melaksanakan a Pokok Binari dalam C.
Langkah 1: Isytiharkan Pokok Carian Binari
Cipta nod struct yang mempunyai tiga jenis data, seperti data, *left_child, dan *right_child, di mana data boleh daripada jenis integer, dan kedua-dua *left_child dan *right_child nod boleh diisytiharkan sebagai NULL atau tidak.
struct nod{
int data ;
struct nod * anak_kanan ;
struct nod * anak_kiri ;
} ;
Langkah 2: Cipta Nod Baharu dalam Pokok Carian Binari
Cipta nod baharu dengan mencipta fungsi yang menerima integer sebagai hujah dan menyediakan penuding kepada nod baharu yang dibuat dengan nilai tersebut. Gunakan fungsi malloc() dalam C untuk peruntukan memori dinamik untuk nod yang dibuat. Mulakan anak kiri dan kanan kepada NULL dan kembalikan nodeName.
struct nod * cipta ( data jenis data )
{
struct nod * nodeName = malloc ( saiz ( struct nod ) ) ;
nodeName -> data = nilai ;
nodeName -> anak_kiri = nodeName -> anak_kanan = NULL ;
kembali nodeName ;
}
Langkah 3: Masukkan Anak Kanan dan Kiri dalam Pokok Binari
Cipta fungsi insert_left dan insert_right yang akan menerima dua input, iaitu nilai yang akan dimasukkan dan penunjuk ke nod yang kedua-dua kanak-kanak akan disambungkan. Panggil fungsi cipta untuk mencipta nod baharu dan tetapkan penuding yang dikembalikan kepada penuding kiri anak kiri atau penuding kanan anak kanan induk akar.
struct nod * sisip_kiri ( struct nod * akar , data jenis data ) {akar -> dibiarkan = cipta ( data ) ;
kembali akar -> dibiarkan ;
}
struct nod * sisip_kanan ( struct nod * akar , data jenis data ) {
akar -> betul = cipta ( data ) ;
kembali akar -> betul ;
}
Langkah 4: Paparkan Nod Pokok Binari Menggunakan Kaedah Traversal
Kita boleh memaparkan pokok dengan menggunakan tiga kaedah traversal dalam C. Kaedah traversal ini ialah:
1: Pre-Order Traversal
Dalam kaedah traversal ini, kita akan melalui nod dalam arah dari parent_node->left_child->right_child .
batal pra_pesanan ( nod * akar ) {jika ( akar ) {
printf ( '%d \n ' , akar -> data ) ;
paparan_pra_pesanan ( akar -> dibiarkan ) ;
paparan_pra_pesanan ( akar -> betul ) ;
}
}
2: Perjalanan Selepas Pesanan
Dalam kaedah traversal ini, kita akan melalui nod dalam arah dari left_child->right_child->parent_node-> .
batal paparan_pos_pesanan ( nod * akar ) {jika ( binary_tree ) {
paparan_pos_pesanan ( akar -> dibiarkan ) ;
paparan_pos_pesanan ( akar -> betul ) ;
printf ( '%d \n ' , akar -> data ) ;
}
}
3: Traversal Tertib
Dalam kaedah traversal ini, kita akan melalui nod dalam arah dari left_node->root_child->right_child .
batal paparan_dalam_tertib ( nod * akar ) {jika ( binary_tree ) {
paparan_dalam_tertib ( akar -> dibiarkan ) ;
printf ( '%d \n ' , akar -> data ) ;
paparan_dalam_tertib ( akar -> betul ) ;
}
}
Langkah 5: Lakukan Pemadaman dalam Pokok Binari
Kita boleh memadam yang dibuat Pokok Binari dengan memadam kedua-dua kanak-kanak dengan fungsi nod induk dalam C seperti berikut.
batal delete_t ( nod * akar ) {jika ( akar ) {
delete_t ( akar -> dibiarkan ) ;
delete_t ( akar -> betul ) ;
percuma ( akar ) ;
}
}
C Program Pokok Carian Binari
Berikut ialah pelaksanaan lengkap pepohon carian Binari dalam pengaturcaraan C:
#include#include
struct nod {
int nilai ;
struct nod * dibiarkan , * betul ;
} ;
struct nod * nod1 ( int data ) {
struct nod * tmp = ( struct nod * ) malloc ( saiz ( struct nod ) ) ;
tmp -> nilai = data ;
tmp -> dibiarkan = tmp -> betul = NULL ;
kembali tmp ;
}
batal cetak ( struct nod * nod_akar ) // memaparkan nod!
{
jika ( nod_akar != NULL ) {
cetak ( nod_akar -> dibiarkan ) ;
printf ( '%d \n ' , nod_akar -> nilai ) ;
cetak ( nod_akar -> betul ) ;
}
}
struct nod * insert_node ( struct nod * nod , int data ) // memasukkan nod!
{
jika ( nod == NULL ) kembali nod1 ( data ) ;
jika ( data < nod -> nilai ) {
nod -> dibiarkan = insert_node ( nod -> dibiarkan , data ) ;
} lain jika ( data > nod -> nilai ) {
nod -> betul = insert_node ( nod -> betul , data ) ;
}
kembali nod ;
}
int utama ( ) {
printf ( 'C pelaksanaan Pokok Carian Binari! \n \n ' ) ;
struct nod * ibu bapa = NULL ;
ibu bapa = insert_node ( ibu bapa , 10 ) ;
insert_node ( ibu bapa , 4 ) ;
insert_node ( ibu bapa , 66 ) ;
insert_node ( ibu bapa , Empat lima ) ;
insert_node ( ibu bapa , 9 ) ;
insert_node ( ibu bapa , 7 ) ;
cetak ( ibu bapa ) ;
kembali 0 ;
}
Dalam kod di atas, kami mula-mula mengisytiharkan a nod menggunakan struct . Kemudian kami memulakan nod baharu sebagai “ nod1 ” dan memperuntukkan memori secara dinamik menggunakan malloc() dalam C dengan data dan dua anak jenis penunjuk menggunakan nod yang diisytiharkan. Selepas ini, kami memaparkan nod oleh printf() berfungsi dan memanggilnya dalam utama() fungsi. Kemudian insertion_node() fungsi dicipta, di mana jika data nod adalah NULL maka nod1 adalah bersara, jika tidak data diletakkan dalam nod (ibu bapa) anak kiri dan kanan. Program ini memulakan pelaksanaan dari utama() fungsi, yang menjana nod menggunakan beberapa nod sampel sebagai kanak-kanak dan kemudian menggunakan kaedah traversal Dalam Pesanan untuk mencetak kandungan nod.
Pengeluaran
Kesimpulan
Pokok sering digunakan untuk menyimpan data dalam bentuk bukan linear. Pokok binari ialah jenis pokok di mana setiap nod (induk) mempunyai dua anak iaitu anak kiri dan anak kanan. A pokok binari adalah kaedah serba boleh untuk memindahkan dan menyimpan data. Ia lebih cekap berbanding dengan Linked-List dalam C. Dalam artikel di atas, kita telah melihat konsep a Pokok Binari dengan pelaksanaan langkah demi langkah a Pokok Carian Binari dalam C.