Pohon Biner di C
Di C, a pohon biner adalah turunan dari struktur data pohon dengan simpul induk yang dapat memiliki jumlah maksimum dua simpul anak; 0, 1, atau 2 node keturunan. Setiap simpul dalam a pohon biner memiliki nilai tersendiri dan dua pointer untuk anak-anaknya, satu pointer untuk anak kiri dan yang lainnya untuk anak kanan.
Deklarasi Pohon Biner
A pohon biner dapat dideklarasikan dalam C menggunakan objek bernama struct yang menggambarkan salah satu node di pohon.
struct simpul {
tipe datavar_name ;
struct simpul * kiri ;
struct simpul * Kanan ;
} ;
Di atas adalah deklarasi satu pohon biner nama simpul sebagai simpul. Ini memegang tiga nilai; satu adalah variabel penyimpan data dan dua lainnya adalah penunjuk ke anak. (anak kiri dan kanan dari simpul induk).
Fakta Pohon Biner
Bahkan untuk kumpulan data yang besar, menggunakan a pohon biner membuat pencarian lebih mudah dan lebih cepat. Jumlah cabang pohon tidak dibatasi. Berbeda dengan larik, pohon apa pun dapat dibuat dan ditingkatkan berdasarkan apa yang dibutuhkan seseorang.
Implementasi Pohon Biner di C
Berikut ini adalah panduan langkah demi langkah untuk mengimplementasikan a Pohon Biner di C.
Langkah 1: Deklarasikan Pohon Pencarian Biner
Buat node struct yang memiliki tiga tipe data, seperti data, *left_child, dan *right_child, di mana data dapat bertipe integer, dan kedua node *left_child dan *right_child dapat dideklarasikan sebagai NULL atau tidak.
struct simpul{
int data ;
struct simpul * anak_kanan ;
struct simpul * anak_kiri ;
} ;
Langkah 2: Buat Node Baru di Binary Search Tree
Buat simpul baru dengan membuat fungsi yang menerima bilangan bulat sebagai argumen dan memberikan penunjuk ke simpul baru yang dibuat dengan nilai tersebut. Gunakan fungsi malloc() di C untuk alokasi memori dinamis untuk node yang dibuat. Inisialisasi anak kiri dan kanan ke NULL dan kembalikan nodeName.
struct simpul * membuat ( data tipe data )
{
struct simpul * nodeName = malloc ( ukuran dari ( struct simpul ) ) ;
nodeName -> data = nilai ;
nodeName -> anak_kiri = nodeName -> anak_kanan = BATAL ;
kembali nodeName ;
}
Langkah 3: Masukkan Anak Kanan dan Kiri di Pohon Biner
Buat fungsi insert_left dan insert_right yang akan menerima dua input, yaitu nilai yang akan disisipkan dan penunjuk ke node tempat kedua anak akan dihubungkan. Panggil fungsi buat untuk membuat simpul baru dan tetapkan penunjuk yang dikembalikan ke penunjuk kiri anak kiri atau penunjuk kanan anak kanan induk root.
struct simpul * masukkan_kiri ( struct simpul * akar , data tipe data ) {akar -> kiri = membuat ( data ) ;
kembali akar -> kiri ;
}
struct simpul * sisipkan_kanan ( struct simpul * akar , data tipe data ) {
akar -> Kanan = membuat ( data ) ;
kembali akar -> Kanan ;
}
Langkah 4: Tampilkan Node Pohon Biner Menggunakan Metode Traversal
Kita dapat menampilkan pohon dengan menggunakan tiga metode traversal di C. Metode traversal ini adalah:
1: Traversal Pre-Order
Dalam metode traversal ini, kita akan melewati node dengan arah dari parent_node->left_child->right_child .
ruang kosong pesan terlebih dahulu ( simpul * akar ) {jika ( akar ) {
printf ( '%D \N ' , akar -> data ) ;
display_pre_order ( akar -> kiri ) ;
display_pre_order ( akar -> Kanan ) ;
}
}
2: Traversal Pasca-Order
Dalam metode traversal ini, kita akan melewati node dengan arah dari left_child->right_child->parent_node-> .
ruang kosong display_post_order ( simpul * akar ) {jika ( binary_tree ) {
display_post_order ( akar -> kiri ) ;
display_post_order ( akar -> Kanan ) ;
printf ( '%D \N ' , akar -> data ) ;
}
}
3: Traversal In-Order
Dalam metode traversal ini, kita akan melewati node dengan arah dari left_node->root_child->right_child .
ruang kosong display_in_order ( simpul * akar ) {jika ( binary_tree ) {
display_in_order ( akar -> kiri ) ;
printf ( '%D \N ' , akar -> data ) ;
display_in_order ( akar -> Kanan ) ;
}
}
Langkah 5: Lakukan Penghapusan di Pohon Biner
Kami dapat menghapus yang dibuat Pohon Biner dengan menghapus kedua anak dengan fungsi simpul induk di C sebagai berikut.
ruang kosong hapus_t ( simpul * akar ) {jika ( akar ) {
hapus_t ( akar -> kiri ) ;
hapus_t ( akar -> Kanan ) ;
bebas ( akar ) ;
}
}
Program C Pohon Pencarian Biner
Berikut ini adalah implementasi lengkap pohon pencarian biner dalam pemrograman C:
#termasuk#termasuk
struct simpul {
int nilai ;
struct simpul * kiri , * Kanan ;
} ;
struct simpul * node1 ( int data ) {
struct simpul * tmp = ( struct simpul * ) malloc ( ukuran dari ( struct simpul ) ) ;
tmp -> nilai = data ;
tmp -> kiri = tmp -> Kanan = BATAL ;
kembali tmp ;
}
ruang kosong mencetak ( struct simpul * root_node ) // menampilkan node!
{
jika ( root_node != BATAL ) {
mencetak ( root_node -> kiri ) ;
printf ( '%D \N ' , root_node -> nilai ) ;
mencetak ( root_node -> Kanan ) ;
}
}
struct simpul * insert_node ( struct simpul * simpul , int data ) // menyisipkan node!
{
jika ( simpul == BATAL ) kembali node1 ( data ) ;
jika ( data < simpul -> nilai ) {
simpul -> kiri = insert_node ( simpul -> kiri , data ) ;
} kalau tidak jika ( data > simpul -> nilai ) {
simpul -> Kanan = insert_node ( simpul -> Kanan , data ) ;
}
kembali simpul ;
}
int utama ( ) {
printf ( 'Implementasi C Pohon Pencarian Biner! \N \N ' ) ;
struct simpul * induk = BATAL ;
induk = insert_node ( induk , 10 ) ;
insert_node ( induk , 4 ) ;
insert_node ( induk , 66 ) ;
insert_node ( induk , Empat.Lima ) ;
insert_node ( induk , 9 ) ;
insert_node ( induk , 7 ) ;
mencetak ( induk ) ;
kembali 0 ;
}
Pada kode di atas, pertama-tama kita mendeklarasikan a simpul menggunakan struct . Kemudian kami menginisialisasi node baru sebagai ' node1 ” dan mengalokasikan memori secara dinamis menggunakan malloc() di C dengan data dan dua pointer ketik anak-anak menggunakan node yang dideklarasikan. Setelah ini, kami menampilkan node dengan printf() fungsi dan memanggilnya di utama() fungsi. Kemudian insertion_node() fungsi dibuat, di mana jika data simpul adalah NULL maka node1 sudah pensiun, data lain ditempatkan di simpul (orang tua) dari anak kiri dan kanan. Program memulai eksekusi dari utama() fungsi, yang menghasilkan node menggunakan beberapa sampel node sebagai turunan dan kemudian menggunakan metode traversal In-Order untuk mencetak konten node.
Keluaran
Kesimpulan
Pohon sering digunakan untuk menyimpan data dalam bentuk non-linear. Pohon biner adalah jenis pohon dimana setiap simpul (induk) memiliki dua anak yaitu anak kiri dan anak kanan. A pohon biner adalah metode serbaguna untuk mentransfer dan menyimpan data. Ini lebih efisien dibandingkan dengan Linked-List di C. Pada artikel di atas, kita telah melihat konsep a Pohon Biner dengan implementasi langkah demi langkah dari a Pohon Pencarian Biner di C.